(转载)图的深度优先遍历非递归算法

纠结图的深度优先搜索算法好久，非递归算法需要用到栈来记录上一次访问的结果，但是大脑中反应不出来。这里做一个记录：

栈的用处：在这一步执行完成之后，下一步需要用到上一步执行的结果，用栈来实现往往是最有效的。

以下是转载的内容：

深度优先遍历算法的非递归实现需要了解深度优先遍历的执行过程，设计一个栈来模拟递归实现中系统设置的工作栈，算法的伪代码描述为：

 

假设图采用邻接矩阵作为存储结构，具体算法如下：

 

 

[cpp] view plain copy print ?

　深度优先遍历算法的非递归实现需要了解深度优先遍历的执行过程，设计一个栈来模拟递归实现中系统设置的工作栈，算法的伪代码描述为：          　　假设图采用邻接矩阵作为存储结构，具体算法如下：         <PRE  class =cpp name= "code" >#include<iostream>   #include <queue>    using   namespace  std;   #define  MAX_NODE 12    bool  visited[MAX_NODE] ;   int  stack[ MAX_NODE] ;   queue< int > q;   int  Matric[MAX_NODE][MAX_NODE] =   {       {-1,1,1,0,0,0,0,0,0,0,0,0},       {1,-1,1,0,1,1,0,0,0,0,0,0},       {1,1,-1,1,0,0,0,0,0,0,0,0},       {0,0,1,-1,1,0,0,0,0,0,1,1},       {0,1,0,1,-1,0,0,0,0,0,0,0},       {0,1,0,0,0,-1,0,0,0,0,1,0},       {0,0,0,0,0,0,-1,1,1,1,0,0},       {0,0,0,0,0,0,1,-1,0,0,0,0},       {0,0,0,0,0,0,1,0,-1,1,1,0},       {0,0,0,0,0,0,1,0,1,-1,0,1},       {0,0,0,1,0,1,0,0,1,0,-1,0},       {0,0,0,1,0,0,0,0,0,1,0,-1},    };   void  DFS(  int  v)   {       cout <<  " v" << v ;        int  top = -1 ;       visited[v] =  true  ;       stack[++top] = v ;        while  ( top != -1)       {           v = stack[top] ;            for  ( int  i = 0 ; i < MAX_NODE ; i++)           {                if  (Matric[v][i] == 1 &&!visited[i])               {                   cout <<  " v"  << i ;                   visited[i] =  true  ;                   stack[ ++top ] = i ;                    break  ;               }           }            if ( i == MAX_NODE)           {               top -- ;           }       }          }         void  BFS(  int  v)   {        int  node = 0;       q.push(v);       visited[v] =  true ;        while ( !q.empty())       {                  node = q.front();            for  (  int  i = 0; i < MAX_NODE; i++ )           {                if  ( Matric[node][i] == 1 && !visited[i])               {                   visited[i] =  true ;                   q.push(i);               }           }           cout << " v"  << node;           q.pop();       }                 }   void  Init()   {               int  i = 0;        for  ( i = 0; i < MAX_NODE; i++)       {           visited[i] =  false ;       }   }   int  main()   {       Init();       DFS( 1 ) ;       cout << endl ;       Init();       BFS( 1 );       cout << endl;       Init();       DFS( 6 );       cout <<endl;        return  0 ;   }</PRE>   <PRE></PRE>   <PRE  class =cpp name= "code" ></PRE>  

　深度优先遍历算法的非递归实现需要了解深度优先遍历的执行过程，设计一个栈来模拟递归实现中系统设置的工作栈，算法的伪代码描述为： 


　　假设图采用邻接矩阵作为存储结构，具体算法如下：

[cpp] view plain copy print ?

#include<iostream>    #include <queue>    using   namespace  std;   #define  MAX_NODE 12    bool  visited[MAX_NODE] ;   int  stack[ MAX_NODE] ;   queue< int > q;   int  Matric[MAX_NODE][MAX_NODE] =   {       {-1,1,1,0,0,0,0,0,0,0,0,0},       {1,-1,1,0,1,1,0,0,0,0,0,0},       {1,1,-1,1,0,0,0,0,0,0,0,0},       {0,0,1,-1,1,0,0,0,0,0,1,1},       {0,1,0,1,-1,0,0,0,0,0,0,0},       {0,1,0,0,0,-1,0,0,0,0,1,0},       {0,0,0,0,0,0,-1,1,1,1,0,0},       {0,0,0,0,0,0,1,-1,0,0,0,0},       {0,0,0,0,0,0,1,0,-1,1,1,0},       {0,0,0,0,0,0,1,0,1,-1,0,1},       {0,0,0,1,0,1,0,0,1,0,-1,0},       {0,0,0,1,0,0,0,0,0,1,0,-1},    };   void  DFS(  int  v)   {       cout <<  " v" << v ;        int  top = -1 ;       visited[v] =  true  ;       stack[++top] = v ;        while  ( top != -1)       {           v = stack[top] ;            for  ( int  i = 0 ; i < MAX_NODE ; i++)           {                if  (Matric[v][i] == 1 &&!visited[i])               {                   cout <<  " v"  << i ;                   visited[i] =  true  ;                   stack[ ++top ] = i ;                    break  ;               }           }            if ( i == MAX_NODE)           {               top -- ;           }       }          }         void  BFS(  int  v)   {        int  node = 0;       q.push(v);       visited[v] =  true ;        while ( !q.empty())       {                  node = q.front();            for  (  int  i = 0; i < MAX_NODE; i++ )           {                if  ( Matric[node][i] == 1 && !visited[i])               {                   visited[i] =  true ;                   q.push(i);               }           }           cout << " v"  << node;           q.pop();       }                 }   void  Init()   {               int  i = 0;        for  ( i = 0; i < MAX_NODE; i++)       {           visited[i] =  false ;       }   }   int  main()   {       Init();       DFS( 1 ) ;       cout << endl ;       Init();       BFS( 1 );       cout << endl;       Init();       DFS( 6 );       cout <<endl;        return  0 ;   }  

 

查看更多关于(转载)图的深度优先遍历非递归算法的详细内容...