已知某带权图G的邻接表如下所示,其中表结点的结构为: 则图G是( )。A.

练习题库2022-08-02  37

问题 已知某带权图G的邻接表如下所示,其中表结点的结构为:则图G是( )。A.无向图B.完全图C.有向图D.强连通图

选项 A.无向图
B.完全图
C.有向图
D.强连通图

答案 C

解析 本题考查数据结构基础知识。从题中的邻接表中可知,该图的边为<v1,v3>、<v1,v2>、<v2,v5>、<v2,v6>、<v3,v6>、<v3,v2>、<v5,v4>、<v6,v4>、<v6,v5>,如下图所示,显然,这是个有向图。在无向图中,若存在边(vi,vj),则它同时为vj和vi之间的边。在上面的邻接表中,存在边<v1,v3>,而不存在<v3,v1>,因此该图不是无向图。对于无向图,其边数e和顶点数n的关系为e=n×(n-1)/2。对于有向图,其边数e和顶点数n的关系为e = n×(n-1),因此该图不是完全图。若有向图为强连通图,则任意两个顶点间要存在路径。在该有向图中,由于顶点v4没有出边,因此,不存在v4到其他顶点的路径,因此该图不是强连通图。
转载请注明原文地址:https://tihaiku.com/congyezige/2407224.html

最新回复(0)