圖 - 圖的遍歷 - 深度優先遍歷（二）

　　深度優先遍歷的遞歸算法

　　()深度優先遍歷算法

　　typedef enum{FALSETRUE}Boolean;//FALSE為TRUE為

　　Boolean visited[MaxVertexNum]; //訪問標志向量是全局量

　　void DFSTraverse(ALGraph *G)

　　{ //深度優先遍歷以鄰接表表示的圖G而以鄰接矩陣表示G時算法完全與此相同

　　int i;

　　for(i=;in;i++)

　　visited[i]=FALSE; //標志向量初始化

　　for(i=;in;i++)

　　if(!visited[i]) //v i 未訪問過

　　DFS(Gi); //以v i 為源點開始DFS搜索

　　}//DFSTraverse

　　()鄰接表表示的深度優先搜索算法

　　void DFS(ALGraph *Gint i){

　　//以v i 為出發點對鄰接表表示的圖G進行深度優先搜索

　　EdgeNode *p;

　　printf(visit vertex%cG>adjlist[i]vertex);//訪問頂點v i

　　visited[i]=TRUE; //標記v i 已訪問

　　p=G>adjlist[i]firstedge; //取v i 邊表的頭指針

　　while(p){//依次搜索v i 的鄰接點v j 這裡j=p>adjvex

　　if (!visited[p>adjvex])//若v i 尚未被訪問

　　DFS(Gp>adjvex);//則以V j 為出發點向縱深搜索

　　p=p>next; //找v i 的下一鄰接點

　　}

　　}//DFS

　　()鄰接矩陣表示的深度優先搜索算法

　　void DFSM(MGraph *Gint i)

　　{ //以vi為出發點對鄰接矩陣表示的圖G進行DFS搜索設鄰接矩陣是l矩陣

　　int j;

　　printf(visit vertex%cG>vexs[i]);//訪問頂點v i

　　visited[i]=TRUE;

　　for(j=;jn;j++) //依次搜索v i 的鄰接點

　　if(G>edges[i][j]==&&!visited[j])

　　DFSM(Gj)//(v i v j )∈E且v j 未訪問過故v j 為新出發點

　　}//DFSM

　　注意

　　遍歷操作不會修改圖G的內容故上述算法中可將G定義為ALGraph或MGraph類型的參數而不一定要定義為ALGraph和MGraph的

　　指針類型但基於效率上的考慮選擇指針類型的參數為宜

From:http://tw.wingwit.com/Article/program/sjjg/201311/23838.html