用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：

用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：

A、

B、

C、

D、

用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：

A、

B、

C、

D、

用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：

A、

B、

C、

D、

对一个有n个顶点e条边的图采用邻接表表示时，进行DFS遍历的时间复杂度为（ ），空间复杂度为（ ）：进行BFS遍历的时间复杂度为（ ），空间复杂度为（ ）。

A．O(n)

B．O(e)

C．O(n+e)

D．O(1)

● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。

（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关

B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关

C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)

D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)

A、其深度优先遍历必须采用最大递归深度为n的递归算法。

B、采用邻接矩阵表示时，其广度优先遍历算法的时间复杂度与 e 无关。

C、其广度优先遍历和深度优先遍历算法的空间复杂度均为 O(n)。

D、其广度优先生成树的树高可能大于其深度优先生成树的树高。

E、图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程。

F、图的深度优先遍历方法不适用于无向图。

G、使用队列对图进行广度优先遍历

H、图中有回路时则无法进行遍历

A、有向图的邻接表中，第i个顶点的度为第i个链表中结点数的2倍。

B、求有向图结点的度，必须遍历整个邻接表。

C、邻接表的表示是唯一的。

D、邻接表法只能用于有向图的存储。

A. 求一个顶点的邻接点

B. 求一个顶点的度

C. 深度优先遍历

D. 广度优先遍历

【题目描述】

● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关

B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关

C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)

D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n²)

【我提交的答案】： C

【参考答案与解析】： 正确答案：D

答案分析：

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]

邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图G中的每个顶点 vi，将所有邻接于vi的顶点vj连成一个单链表，这个单链表就称为顶点vi的邻接表，其中表头称作顶点表结点VertexNode，其余结点称作边表结点EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： define MaxVerNum 100 /*最大顶点数为100*/

typedef struct node{ /*边表结点*/

int adjvex; /*邻接点域*/

struct node *next; /*指向下一个边表结点的指针域*/ }EdgeNode;

typedef struct vnode{ /*顶点表结点*/

int vertex; /*顶点域*/

EdgeNode *firstedge; /*边表头指针*/

}VertexNode;

typedef VertexNode AdjList[MaxVerNum]; /*AdjList是邻接表类型*/

typedef struct{

AdjList adjlist; /*邻接表*/

int n; /*顶点数*/

}ALGraph; /*ALGraph是以邻接表方式存储的图类型*/

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。

下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是图中所有顶点未曾被访问，算法从某顶点v出发，访问此顶点，然后依次从v的邻接点出发进行搜索，直至所有与v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的搜索完成。程序中的整型数组visited[]的作用是标记顶点i是否已被访问。

[函数]

void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图G*/

{ int i;

for(i=0;i＜(1);i++) visited[i]=0;

for(i=0;i＜(1);i++)if((2)) DFSAL(G,i);

}

void DFSAL(ALGraph *G,int i) /*从Vi出发对邻接表存储的图G进行搜索*/

{ EdgeNode *p;

(3);

p=(4);

while(p!=NULL) /*依次搜索Vi的邻接点Vj*/

{ if(! visited[(5)]) DFSAL(G,(5));

p=p-＞next; /*找Vi的下一个邻接点*/

}

}