Question

用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法

Answer 1

使用栈来实现算法。

用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度遍历使用队列。

扩展材料：

深度优先遍历：类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到

注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。

广度优先遍历：类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

参考资料来源：

知网论文-数据结构中图的遍历算法研究

Answer 2

用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法。

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

邻接表相似类：

图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。

Answer 3

邻接表图的深度优先，思想是以深度因素为优先遍历，（因此可以检测是否图为连通图），可以想像成你从上往下走迷宫，走不动了就从根再换条路走，算法实现方式就与这种思想匹配，使用递归（栈）来完成遍历。具体为:
void DfsTra(graph t,bool visit［n］){
int i;//n为图的顶点个数，visit数组最好全局化
for(i=0;i<n;i++)visit[i]=false;
//访问数组
for(i=0;i<n;i++)
if(!visit[i])DFS（G,i）;
}//对每个未访问顶点调用DFS
邻接表结构
头结点为data和firstarc（指向第一个相连结点）
表结点为adjvex（出度顶点序号）和info和nextarc（指向下一个与头结点相连结点）

void DFS（graph G,int i）{
visit［i］=true;//visit（i）;
for（w=firstarcadjvex（G,i）;w>=0;w=nextarcadjvex（G,i,w））//重点代码，w等于第一个相连结点的adjvex，一直往后到最后一个相连结点的adjvex
if（！visit［w］）DFS（G,w）;
//递归思想，不停调用自身，但是始终是以深度为优先
}

Answer 4

用邻接表表示图进行深度优先遍历时，通常采用（栈 ）来实现算法