一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。

题目
一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。

相似考题

1.阅读下列函数说明和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的下一个邻接点*/}}

2.● 对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问） ，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问） ，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40） 是下图的深度优先遍历序列。（40）A. 1 2 3 4 6 5B. 1 2 6 3 4 5C. 1 6 2 5 4 3D. 1 2 3 4 5 6

3.● 具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为 （63） 。

4.阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。1. 【说明】实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。【算法】第一步：首先访问连通图G的指定起始顶点v；第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。

更多“一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。 ”相关问题

  • 第1题：

    已知图的邻接表如图所示, 请分别写出顶点v0出发的深度优先遍历结果和广度优先遍历结果。


    v3v0v1v2, v3v0v2v1

  • 第2题：

    假设图采用邻接矩阵表示。设计一个从顶点v出发的深度优先遍历算法输出一个深度优先遍历序列。


    n 2

  • 第3题：

    【单选题】下列有关图遍历的说法中不正确的是（)。

    A．连通图的深度优先搜索是一个递归过程

    B．图的广度优先搜索中邻接点的寻找具有“先进先出”特征

    C．非连通图不能用深度优先搜索法

    D．图的遍历要求每一顶点仅被访问一次


    图的遍历要求每一顶点仅被访问一次

  • 第4题：

    16、下列关于图遍历的说法不正确的是（）。

    A．连通图的深度优先搜索是一个递归过程

    B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

    C．非连通图不能用深度优先搜索法

    D．图的遍历要求每一顶点仅被访问一次


    D

  • 第5题：

    4、下列关于一个有 n 个顶点 e条边的图的表述中，正确的是（）。

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

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

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

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

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

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

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

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


    BCG

相关内容