算法设计深度优先遍历和广度优先遍历.docx

1、算法设计深度优先遍历和广度优先遍历深度优先遍历过程1、图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶 点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有 向图均适用。以下假定遍历过程中访问顶点的操作是简单地输出顶点。2、布尔向量 visited0 n-1 的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回 路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为 此，可设一布尔向量 visited0 n-1 ，其初值为假，一旦访问了顶点 Vi

2、 之后，便将 visitedi 置为真。深度优先遍历 (Depth-First Traversal)1图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。在 G中任选一顶点V为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点 V ,并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点W。若W未曾访问过，则以 W为新的出发点继 续进行深度优先遍历，直至图中所有和源点 V 有路径相通的顶点 (亦称为从源点可达的 顶点 )均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作 为新的源点重复上述过程，直至图中所有顶点均已被访问为止。图的深度优先遍历类似

3、于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深 方向进行搜索。这种搜索方法称为深度优先搜索 (Depth-First Search) 。相应地，用此 方法遍历图就很自然地称之为图的深度优先遍历。2、深度优先搜索的过程设 x 是当前被访问顶点，在对 x 做过访问标记后，选择一条从 x 出发的未检测过的边(X , y)。若发现顶点y已访问过，则重新选择另一条从 X出发的未检测过的边，否则沿边(X，y)到达未曾访问过的y ,对y访问并将其标记为已访问过；然后从 y开始搜索, 直到搜索完从y出发的所有路径，即访问完所有从 y出发可达的顶点之后，才回溯到顶点X,并且再选择一条从 X出发的未检测过的

4、边。上述过程直至从 X出发的所有边都已检测过为止。此时，若 X不是源点，则回溯到在 X之前被访问过的顶点；否则图中所有和源点有路径相通的顶点 (即从源点可达的所有顶点 )都已被访问过，若图 G 是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的 搜索过程。3、深度优先遍历的递归算法(1)深度优先遍历算法typedef enumFALSE ， TRUEBoolean ； /FALSE 为 0， TRUE 为 1Boolean visitedMaXVerteXNum ； / 访问标志向量是全局量void DFSTraverse(ALGraph *G) /深度优先遍历以邻

5、接表表示的图 G,而以邻接矩阵表示 G时，算法完全与此相同int i ；for(i=0;in;i+)visitedi=FALSE ； / 标志向量初始化for(i=0;in ； i+)if(!visitedi) /vi 未访问过DFS(G，i) ； Il以Vi为源点开始DFS搜索/DFSTraverse(2)邻接表表示的深度优先搜索算法Void DFS(ALGraph *G ， int i)Il以Vi为出发点对邻接表表示的图 G进行深度优先搜索EdgeNode *p ；printf(Visit VerteX ： c， G-adjlisti.VerteX) ； II 访问顶点 ViVisited

6、i=TRUE ； II 标记 Vi 已访问p=G-adjlisti.firstedge ； II 取 Vi 边表的头指针While(P)/ 依次搜索Vi的邻接点Vj ,这里j=p-adjvexif (!Visitedp-adjVeX)II 若 Vi 尚未被访问DFS(G ， p-adjVeX);/ 则以 Vj 为出发点向纵深搜索p=p-neXt ； / 找 Vi 的下一邻接点/DFS3)邻接矩阵表示的深度优先搜索算法void DFSM(MGraph *G ，int i) Zz以Vi为出发点对邻接矩阵表示的图 G进行DFS搜索，设邻接矩阵是 0,1矩阵int j ；Printf(visit Ve

7、rteX :% c, G-vexsi) ; ZZ 访问顶点 ViVisitedi=TRUE ；for(j=0 ； jn ； j+) ZZ 依次搜索 vi 的邻接点 if(G-edgesij=1&!visitedj)DFSM(G , j)ZZ(vi , Vj) E,且Vj未访问过，故 Vj为新出发点ZZDFSM遍历操作不会修改图 G的内容，故上述算法中可将 G定义为ALGraPh或MGraPh 类型的参数,而不一定要定义为 ALGraPh 和 MGraPh 的指针类型。但基于效率上的考 虑,选择指针类型的参数为宜。4、 深度优先遍历序列 对图进行深度优先遍历时,按访问顶点的先后次序得到的顶点序列

8、称为该图的深度优先遍历序列，或简称为 DFS序列。（1） 一个图的DFS序列不一定惟一当从某顶点X出发搜索时，若X的邻接点有多个尚未访问过，则我们可任选一个访 问之。（2） 源点和存储结构的内容均已确定的图的 DFS序列惟一1邻接矩阵表示的图确定源点后， DFS序列惟一DFSM算法中，当从Vi出发搜索时，是在邻接矩阵的第 i行上从左至右选择下一个 未曾访问过的邻接点作为新的出发点,若这样的邻接点多于一个,则选中的总是序号 较小的那一个。2只有给出了邻接表的内容及初始出发点，才能惟一确定其 DFS序列邻接表作为给定图的存储结构时,其表示不惟一。因为邻接表上边表里的邻接点域 的内容与建表时的输入次

9、序相关。因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其 DFS序列。3）栈在深度优先遍历算法中的作用深度优先遍历过程中,后访问的顶点其邻接点被先访问,故在递归调用过程中使用 栈（系统运行时刻栈）来保存已访问的顶点。5、 算法分析对于具有 n 个顶点和 e 条边的无向图或有向图,遍历算法 DFSTraVerse 对图中每顶 点至多调用一次 DFS或DFSMO从DFSTraVerSe中调用DFS（或DFSM）及DFS（或DFSM) 内部递归调用自己的总次数为 n当访问某顶点Vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻 接点上。用邻接矩阵表示图时，其搜索时间为 O

10、(n) ；用邻接表表示图时，需搜索第 i个边表上的所有结点。因此，对所有 n个顶点访问，在邻接矩阵上共需检查 n2个矩阵元素，在邻接表上需将边表中所有 O(e) 个结点检查一遍。所以，DFSTraVerSe的时间复杂度为 0(n2)(调用DFSM)或0(n+e)(调用DFS)1、 广度优先遍历的递归定义设图G的初态是所有顶点均未访问过。在 G中任选一顶点V为源点，则广度优先遍历可以定义为：首先访问出发点 V,接着依次访问V的所有邻接点 w1 , w2 ,，Wt ,然后再依次访问与 wl, w2 ,，Wt邻接的所有未曾访问过的顶点。依此类推，直至图 中所有和源点V有路径相通的顶点都已访问到为止。

11、此时从 V开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图 C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至 G中所有顶点均已被访问为止。广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进 行搜索,故称其为广度优先搜索 (Breadth-FirstSearch) 。相应的遍历也就自然地称为广 度优先遍历。2、 广度优先搜索过程在广度优先搜索过程中，设 X和y是两个相继要被访问的未访问过的顶点。它们的 邻接点分别记为 x1 , x2, , xs 和 y1 , y2, , yt。为确保先访问的顶点其邻接点亦先被访问,在搜索过程中使用 FIFO 队列来保存已

12、 访问过的顶点。当访问 X和y时，这两个顶点相继入队。此后，当 X和y相继出队时，我们分别从X和y出发搜索其邻接点x1 , x2,，XS和y1 , y2,，yt ,对其中未访 者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至 多只有一次人队。3、 广度优先搜索算法(1) 邻接表表示图的广度优先搜索算法Void BFS(ALGraph*G ，int k)/以Vk为源点对用邻接表表示的图 G进行广度优先搜索int i ；CirQueue Q ； / 须将队列定义中 DataType 改为 intEdgeNode *p ；InitQueue(&Q) ； / 队列初始化/ 访

13、问源点 vkprintf(visit vertex ： e， G-adjlistk.vertex) ；visitedk=TRUE ；EnQueue(&Q ， k)；/vk 已访问，将其人队。(实际上是将其序号人队) while(!QueueEmpty(&Q)/ 队非空则执行i=DeQueue(&Q) ； / 相当于 vi 出队 p=G-adjlisti.firstedge ； / 取 vi 的边表头指针 while(p)/ 依次搜索 vi 的邻接点 vj( 令 p-adjvex=j) if(!visitedp-adivex) / 若 vj 未访问过printf(visitvertex ： c

14、，C-adjlistlp-adjvex.vertex) ； / 访问 vjvisitedp-adjvex=TRUE ；EnQueue(&Q ， p-adjvex) ； / 访问过的 vj 人队 /endif p=p-next ； / 找 vi 的下一邻接点/endwhile/endwhile/end of BFS2)邻接矩阵表示的图的广度优先搜索算法 void BFSM(MGraph *G ，int k)以Vk为源点对用邻接矩阵表示的图 G进行广度优先搜索int i ， j； CirQueue Q ；InitQueue(&Q) ；printf(Visit Vertex ：c， G-Vexsk)

15、 ； / 访问源点 Vk Visitedk=TRUE ；EnQueue(&Q ， k) ； while(!QueueEmpty(&Q) i=DeQueue(&Q) ； /Vi 出队 for(j=0;jn;j+)/ 依次搜索 Vi 的邻接点 Vj if(G-edgesij=1&!Visitedj)/Vi 未访问printf(Visit Vertex ： c，G-Vexsj) ； / 访问 ViVisitedj=TRUE ；EnQueue(&Q ，j) ； /访问过的Vi人队/endwhile/BFSM(3)广度优先遍历算法类似于 DFSTraverse 。4、图的广度优先遍历序列 广度优先遍历图

16、所得的顶点序列，定义为图的广度优先遍历序列，简称 BFS 序列。(1)一个图的 BFS 序列不是惟一的(2)给定了源点及图的存储结构时，算法 BFS和BFSM所给出BFS序列就是惟一的。5、算法分析对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次。广度优先遍历(BFSTraVerSe)图的时间复杂度和 DFSTraVerSe算法相同。当图是连通图时，BFSTraVerSe算法只需调用一次 BFS或BFSM即可完成遍历操作,此时BFS和BFSM的时间复杂度分别为 0(n+e)和0(n2)。来源：(http:/blog.S - 深度优先搜索遍历与广度 优先搜索遍历 _chriStina

17、_ 新浪博客/ 深度优先遍历算法实现：/ 返回顶点 V 在顶点向量中的位置int LocateVex(ALGraph G, char V) int i;for(i = 0; V != G.VerticeSi.data & i = G.Vexnum)return -1; return i;/ 构造邻接链表StatuS CreateDN(ALGraph &G) int i,j;ArcNode *S;printf( 输入有向图顶点数 : );Scanf(%d, &G.Vexnum);printf( 输入有向图边数 : );scanf(%d, &G.arcnum); getchar();for(i =

18、 0; i G.vexnum; i+)printf( 输入第 %d 个顶点信息 :, i+1);scanf(%c, &G.verticesi); / 构造顶点向量 G.verticesi.firstarc = NULL; getchar();char v1, v2;for(int k = 0; k adjvex = j; / 该边所指向的顶点的位置为 j s-nextarc = G.verticesi.firstarc; G.verticesi.firstarc =s;return OK;Status PrintAdjList(ALGraph &G)int i;ArcNode *p;print

19、f(%4s%6s%12sn, 编号 , 顶点 , 相邻边编号 );for(i = 0; i nextarc)printf(%4d, p-adjvex);printf(n);return OK;void DFS(ALGraph G, int v, int *visited) int w;ArcNode *s;visitedv = 1;printf(%c -, G.verticesv.data); s = G.verticesv.firstarc;while(s != NULL)w = s-adjvex; if(visitedw = 0)DFS(G, w, visited);s = s-nexta

20、rc;Zz对图G做深度优先遍历Status DFSTraverse(ALGraph G)int v;int visitedMAX_VERTEX_NUM;for(v = 0; v G.vexnum; +v) visitedv = 0; ZZ 初始化 visitedvfor(v = 0; v G.vexnum; +v)if(visitedv = 0)DFS()DFS(G, v, visited); ZZ 对未访问的顶点调用printf( 完成 n);return OK;广度优先遍历算法实现。ZZ 返回顶点 v 在顶点向量中的位置 int LocateVex(ALGraph G, char v) i

21、nt i;for(i = 0; v != G.verticesi.data & i = G.vexnum) return -1;return i;/ 构造无向图邻接链表Status CreateUDN(ALGraph &G)int i, j;ArcNode *s, *t; printf( 输入有向图顶点数 : ); scanf(%d, &G.vexnum); printf( 输入有向图边数 : ); scanf(%d, &G.arcnum);getchar();for(int i = 0; i G.vexnum; i+) printf( 输入第 %d 个顶点信息 :, i+1); scanf(

22、%c, &G.verticesi); / 构造顶点向量 G.verticesi.firstarc = NULL;getchar();char v1, v2;for(int k = 0; k adjvex = j; / 该边所指向的顶点的位置为 j s-nextarc = G.verticesi.firstarc;G.verticesi.firstarc =s;t-adjvex = i; / 该边所指向的顶点的位置为 jt-nextarc = G.verticesj.firstarc;G.verticesj.firstarc =t; return OK;Status InitQueue(SqQu

23、eue &Q) sizeof(QElemType);队列已满Q.base = (QElemType *) malloc (MAXQSIZE if(!Q.base)printf( 分配地址失败！ ); return 0; Q.front = Q.rear = 0; return OK;/ 已访问图顶点入队Status EnQueue(SqQueue &Q, QElemType e) if(Q.rear+1) % MAXQSIZE = Q.front) / printf( 队列已满 !); return 0; Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXQS

24、IZE; return OK;/ 判断队列是否为空 Status QueueEmpty(SqQueue Q) if(Q.front = Q.rear) return OK;else return 0;/ 辅助队列队头顶点出队 char DeQueue(SqQueue &Q) QElemType e; if(Q.front = Q.rear) / 队列为空 printf( 队列为空 !); return 0;e = Q.baseQ.front;Q.front = (Q.front+1) % MAXQSIZE; return e;Status PrintAdjList(ALGraph &G) in

25、t i;编号, 顶点, 相邻边编号 );ArcNode *p; printf(%4s%6s%12sn, for(int i = 0; i nextarc) printf(%4d, p-adjvex);printf(n);return OK;void DFS(ALGraph G, int v, int *visited) int w;ArcNode *s;visitedv = 1;printf(%c -, G.verticesv.data); s = G.verticesv.firstarc;while(s != NULL)w = s-adjvex; if(visitedw = 0)DFS(G,

26、 w, visited);s = s-nextarc;Zz对图G做广度优先遍历Status BFSTraverse(ALGraph G)int v, u, w;int visitedMAX_VERTEX_NUM;ArcNode *s;char e;SqQueue Q; ZZ 辅助队列for(v = 0; v G.vexnum; +v) visitedv = 0; ZZ 初始化 visitedvInitQueue(Q);for(v = 0; v , G.verticesv.data);EnQueue(Q, G.verticesv.data); ZZ 已访问顶点入队while(!QueueEmpty(Q) ZZ 辅助队列非空 u = LocateVex(G, e);s = (ArcNode *) malloc (sizeof(ArcNode);s = G.verticesu.firstarc;while(s != NULL) /* 顶点 e 还有邻接顶点 w = s-adjvex; if(visitedw = 0) visitedw = 1; printf(%c -, G.verticesw.data); EnQueue(Q, G.verticesw