算法设计：深度优先遍历和广度优先遍历实现深度优先遍历过程1、图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
它们对无向图和有向图均适用。
以下假定遍历过程中访问顶点的操作是简单地输出顶点。
2、布尔向量visited[0 ．．n-1] 的设置图中任一顶点都可能和其它顶点相邻接。
在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。
为了避免重复访问同一个顶点，必须记住每个已访问的顶点。
为此，可设一布尔向量visited[0 ．．n-1] ，其初值为假，一旦访问了顶点Vi 之后，便将visited[i] 置为真。
深度优先遍历(Depth-First Traversal)1．图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。
在G中任选一顶点V为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点V ,并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点W。
若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V 有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。
采用的搜索方法的特点是尽可能先对纵深方向进行搜索。
这种搜索方法称为深度优先搜索(Depth-First Search) 。
相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
2、深度优先搜索的过程设x 是当前被访问顶点，在对x 做过访问标记后，选择一条从x 出发的未检测过的边(X , y)。
若发现顶点y已访问过，则重新选择另一条从X出发的未检测过的边，否则沿边(X，y)到达未曾访问过的y ,对y访问并将其标记为已访问过；然后从y开始搜索, 直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点X,并且再选择一条从X出发的未检测过的边。
上述过程直至从X出发的所有边都已检测过为止。
此时，若X不是源点，则回溯到在X之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G 是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
3、深度优先遍历的递归算法(1)深度优先遍历算法typedef enum{FALSE ，TRUE}Boolean ；//FALSE 为0，TRUE 为1Boolean visited[MaXVerteXNum] ；// 访问标志向量是全局量void DFSTraverse(ALGraph *G){ //深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时，算法完全与此相同int i ；for(i=0;i<G->n;i++)visited[i]=FALSE ；// 标志向量初始化for(i=0;i<G->n ；i++)if(!visited[i]) //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->adjlist[i].VerteX) ；II 访问顶点ViVisited[i]=TRUE ；II 标记Vi 已访问p=G->adjlist[i].firstedge ；II 取Vi 边表的头指针While(P){// 依次搜索Vi的邻接点Vj ,这里j=p->adjvexif (!Visited[p->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 VerteX :% c", G->vexs[i]) ; ZZ 访问顶点ViVisited[i]=TRUE ；for(j=0 ；j<G->n ；j++) ZZ 依次搜索vi 的邻接点if(G->edges[i][j]==1&&!visited[j])DFSM(G , j)ZZ(vi , Vj) ∈E,且Vj未访问过，故Vj为新出发点}ZZDFSM遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraPh或MGraPh 类型的参数,而不一定要定义为ALGraPh 和MGraPh 的指针类型。
但基于效率上的考虑,选择指针类型的参数为宜。
4、深度优先遍历序列对图进行深度优先遍历时,按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。
（1）一个图的DFS序列不一定惟一当从某顶点X出发搜索时，若X的邻接点有多个尚未访问过，则我们可任选一个访问之。
（2）源点和存储结构的内容均已确定的图的DFS序列惟一①邻接矩阵表示的图确定源点后，DFS序列惟一DFSM算法中，当从Vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点,若这样的邻接点多于一个,则选中的总是序号较小的那一个。
②只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列邻接表作为给定图的存储结构时,其表示不惟一。
因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。
因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列。
3）栈在深度优先遍历算法中的作用深度优先遍历过程中,后访问的顶点其邻接点被先访问,故在递归调用过程中使用栈（系统运行时刻栈）来保存已访问的顶点。
5、算法分析对于具有n 个顶点和 e 条边的无向图或有向图,遍历算法DFSTraVerse 对图中每顶点至多调用一次DFS或DFSM O从DFSTraVerSe中调用DFS（或DFSM）及DFS（或DFSM) 内部递归调用自己的总次数为n当访问某顶点Vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。
用邻接矩阵表示图时，其搜索时间为O(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有路径相通的顶点都已访问到为止。
此时从V开始的搜索过程结束。
若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。
广度优先遍历类似于树的按层次遍历。
采用的搜索方法的特点是尽可能先对横向进行搜索,故称其为广度优先搜索(Breadth-FirstSearch) 。
相应的遍历也就自然地称为广度优先遍历。
2、广度优先搜索过程在广度优先搜索过程中，设X和y是两个相继要被访问的未访问过的顶点。
它们的邻接点分别记为x1 , x2, …, xs 和y1 , y2, …, yt。
为确保先访问的顶点其邻接点亦先被访问,在搜索过程中使用FIFO 队列来保存已访问过的顶点。
当访问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) ；// 队列初始化// 访问源点vkprintf("visit vertex ：％e"，G->adjlist[k].vertex) ；visited[k]=TRUE ；EnQueue(&Q ，k)；//vk 已访问，将其人队。
(实际上是将其序号人队)while(!QueueEmpty(&Q)){// 队非空则执行i=DeQueue(&Q) ；// 相当于vi 出队p=G->adjlist[i].firstedge ；// 取vi 的边表头指针while(p){// 依次搜索vi 的邻接点vj( 令p->adjvex=j) if(!visited[p->adivex]){ // 若vj 未访问过printf("visitvertex ：％c" ，C->adjlistlp->adjvex].vertex) ；// 访问vjvisited[p->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->Vexs[k]) ；// 访问源点Vk Visited[k]=TRUE ；EnQueue(&Q ，k) ；while(!QueueEmpty(&Q)){ i=DeQueue(&Q) ；//Vi 出队for(j=0;j<G->n;j++)// 依次搜索Vi 的邻接点Vj if(G->edges[i][j]==1&&!Visited[j]){//Vi 未访问printf("Visit Vertex ：％c"，G->Vexs[j]) ；// 访问ViVisited[j]=TRUE ；EnQueue(&Q ，j) ；//访问过的Vi人队}}//endwhile}//BFSM(3)广度优先遍历算法类似于DFSTraverse 。