问题
单项选择题
已知某带权图G的邻接表如下所示,其中表结点的结构为:则图G是()。
A.无向图
B.完全图
C.有向图
D.强连通图
答案
参考答案:C
解析:
本题考查数据结构基础知识。
从题中的邻接表中可知,该图的边为、、、、、、、、,如下图所示,显然,这是个有向图。
在无向图中,若存在边(vi,vj),则它同时为vj和vi之间的边。在上面的邻接表中,存在边,而不存在,因此该图不是无向图。
对于无向图,其边数e和顶点数n的关系为e=n×(n-1)/2。对于有向图,其边数e和顶点数n的关系为e=n×(n-1),因此该图不是完全图。
若有向图为强连通图,则任意两个顶点间要存在路径。在该有向图中,由于顶点v4没有出边,因此,不存在v4到其他顶点的路径,因此该图不是强连通图。