图的深度与广度遍历比较

红太狼 2022-03-16 14:29 194阅读 0赞

**图的深度与广度遍历总结如下：**

\#include <queue>//引用队列结构  
\#include <stack>//引用栈结构  
using namespace std;

\#define  MAX\_VERTEXS 5//结点总数

queue<int> q;  //声明队列变量  
stack<int> s; //声明栈变量

bool visited\[MAX\_VERTEXS\] ;//声明结点是否被访问数组,初始值为false

int path\[MAX\_VERTEXS\];//声明存储遍历的路径，初始值为-1，按照逆序输出。

int Graph\[MAX\_VERTEXS\]\[MAX\_VERTEXS\];//声明图的存储矩阵,0表示无边，非0表示有边

//顶点编号从0开始

**1、图的深度遍历（DFS）**

算法描述：给定图Graph的初态是所有顶点均未曾访问过。在Graph中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：

step1：首先访问出发点v，并将其标记为已访问过；

step2：依次从v出发搜索v的未被访问过的邻接点w。然后以w为新的出发点继续搜索其未访问过的邻接点，

step3：直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

存储结构：栈

源程序：

void DFS(int v)  
    {    
        visited[v] = true ;
        cout<<"v"<< v ; 
        s.push(v);
        while (!s.empty())  
        {  
            v = s.top();
            for (int i = 0 ; i < MAX_VERTEXS; i++)  
            {  
              if (Graph[v][i] == 1 &&!visited[i]) //找到未被访问过的邻接顶点 
               {  
                    cout << " v" << i ;  
                    visited[i] = true ;  
                    s.push(i);
                    path[i]=v;
                    break ;  
             }  
            }  
            if( i == MAX_VERTEXS)//未找到未被访问过的邻接顶点  
                s.pop();
      }        
    }

**2、图的广度遍历（BFS）**

算法描述：给定图Graph的初态是所有顶点均未曾访问过。在Graph中任选一顶点v为初始出发点(源点)，则广度优先遍历可定义如下：

step1：首先访问出发点v，并将其标记为已访问过；

step2：依次从v出发搜索v的未被访问的邻接点w1，w2，w3，...wk，然后依次从w1，w2，w3，...wk出发访问各自未被访问的邻接点。

step3：重复step2，直到所有顶点全部被访问为止。

存储结构：队列

源程序：

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_VERTEXS; i++ )  
           {  
              if ( Graph[node][i] == 1 && !visited[i])//找到未被访问的结点，同时将其加入到队列中
                {  
                   visited[i] = true;  
                   q.push(i); 
    	      path[i]=node;
              }  
          }  
          cout <<" v" << node;  
          q.pop();  //弹出队头元素
       }   
    }