遍历操作是图算法的基本操作，对于图的遍历，主要有两种，一种是深度遍历，一种是广度遍历。虽然这种操作很基本，但是稍微加一些其他的元素进去就能形成很有用的算法，比如加一些限制就可以变成深度或者广度搜索。

 

图遍历算法的特点是需要用一个visit数组保存各个节点是否已经被访问过的信息，对于深度遍历，一般都是递归操作，对于广度遍历，一般是用先入先出队列实现。下面是相应的代码，其他需要的头文件在之前的几篇随笔中有提到，整个工程的源文件我托管在了github上：

头文件：

/*     author: areslipan@163.com     filename : graph_traversal.h     date : 2013.10.1 */ #ifndef GRAPH_TRAVERSAL_ #define GRAPH_TRAVERSAL_ #include "graph.h" #include 
         
           using namespace std; //邻接矩阵的深度遍历 void dfs_matrix(vector
          
           
            > & g, int start, int numNodes); void _dfs_matrix(vector
            
             
               > & g, vector
              
                & visit, int start, int numNodes); //邻接表的深度遍历 void dfs_adjlist(GraphAdjList * g, int start); void _dfs_adjlist(GraphAdjList * g, vector
               
                 &visit, int start); //邻接矩阵的广度遍历 void bfs_matrix(vector
                
                 
                  > &g, int start, int numNodes); void _bfs_matrix(vector
                  
                   
                    > &g, vector
                    
                      & visit, int start ,int numNodes); //邻接表的广度遍历 void bfs_adjlist(GraphAdjList *g, int start); void _bfs_adjlist(GraphAdjList *g, vector
                     
                       & visit, int start); #endif
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         

 

实现文件：

/*     author: areslipan@163.com     filename : graph_traversal.cpp     date: 2013.10.1 */ #include "graph_traversal.h" using namespace std; void dfs_matrix(vector
         
          
           > & g, int start, int numNodes) {
           vector
           
             visit(numNodes,false);     cout<<"邻接矩阵方式存储的图的dfs：";     _dfs_matrix(g, visit, start ,numNodes);     cout<
            

> & g, vector

& visit, int start, int numNodes) {

cout<

<<" "; visit[start] = true; for(int i=0;i

=MYINF)continue; _dfs_matrix(g,visit,i,numNodes); } } void dfs_adjlist(GraphAdjList * g, int start) { vector

visit(g->numNodes, false); cout<<"邻接表方式存储的图的dfs："; _dfs_adjlist(g,visit,start); cout<

&visit, int start) { cout<

<<" "; visit[start] = true; EdgeNode * cur = g->adjList[start].firstedge; while(cur != NULL) { if(!visit[cur->adjvex])_dfs_adjlist(g, visit, cur->adjvex); cur = cur->next; } } void bfs_matrix(vector

> &g, int start, int numNodes) { cout<<"以邻接矩阵方式存储的图的bfs遍历： "; vector

visit(numNodes, false); _bfs_matrix(g, visit, start ,numNodes); cout<

> &g, vector

& visit, int start ,int numNodes) { queue

myQueue; myQueue.push(start); while(!myQueue.empty()) { int cur = myQueue.front(); myQueue.pop(); if(visit[cur])continue; cout<

<<" "; visit[cur] = true; for(int i=0;i

= MYINF)continue; myQueue.push(i); } } } void bfs_adjlist(GraphAdjList *g, int start) { cout<<"以邻接表方式存储的图的bfs遍历： "; vector

visit(g->numNodes, false); _bfs_adjlist(g,visit,start); cout<

& visit, int start) { queue

myQueue; myQueue.push(start); while(!myQueue.empty()) { int cur = myQueue.front(); myQueue.pop(); if(visit[cur])continue; cout<

<<" "; visit[cur] = true; EdgeNode * en = g->adjList[cur].firstedge; while(en!=NULL) { if(!visit[en->adjvex])myQueue.push(en->adjvex); en = en->next; } } }

测试文件：

/*     author: areslipan@163.com     filename: testTraversal.cpp     date: 2013.10.1     示例输入： 0 1 4 1000 1000 1000 1 0 2 7 5 1000 4 2 0 1000 1 1000 1000 7 1000 0 3 2 1000 5 1 3 0 6 1000 1000 1000 2 6 0 6 18 0 1 2 3 4 5 0 1 1 1 0 1 0 2 4 2 0 4 1 2 2 2 1 2 1 4 5 4 1 5 1 3 7 3 1 7 2 4 1 4 2 1 3 4 3 4 3 3 3 5 2 5 3 2 4 5 6 5 4 6 */ #include "graph.h" using namespace std; int main() {
           vector
         
          
            > gm;     create_an_graph_from_stdin(gm,6);     GraphAdjList ga;     create_adjlist_graph(&ga);     show_graph(gm,6);     show_adjlist_graph(&ga);     dfs_matrix(gm, 2, 6);     bfs_matrix(gm, 2, 6);     dfs_adjlist(&ga,2);     bfs_adjlist(&ga,2);     destroy_adjlist_graph(&ga); }
          
         

测试输出：