图的广度优先遍历

一、介绍

1. 广度优先遍历
   广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,…,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。分为三个步骤：

• 使用一个辅助队列，首先将第一个节点v放入队列，并标记也被访问，然后检测队列是否为空
• 如果队列不为空时，将队列的第一个元素取出，并将与该节点相连且未被访问的节点加入队列，并将这些节点进行标记
• 当队列为空时，就完成了图的广度优先遍历

2. 无权图的最短路径
   无权图的最短路劲，是基于图的广度优先遍历而来的，是指图中两节点间最短的路径，通过ord[i]数组用来记录上一个节点到i节点的路径

二、遍历过程

下面直接来看看具体的例子：
对下图进行广度优先遍历

从节点0开始
将0放入队列中，并对节点0进行标记

当队列不为空时，就从队列中拿出首元素，即节点0；然后将和节点0两连并未被访问过的节点依次放入队列中，并进行标记，如下图：

同理，此时队列不为空，就拿出队列中的首元素节点1，此时没有和节点1相连且未被访问过的节点，就没有节点进入队列，然后进入下一轮的遍历。

队列不为空，取出队列首元素节点2，同理(参考节点1的出队列)，进入下一轮遍历

队列不为空，取出队列首元素节点5，并将和5相连且未被访问的节点放入队列，并标记，如下图：

队列不为空，拿出队列首元素节点6，此时节点6相连的且未被访问过的节点就为空了，进入下一轮遍历

同理，遍历节点3：

同理，遍历节点4；此时队列为空，遍历已就完成了

三、代码实现

编写一个类，成员变量及其初始化：

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cassert>

using namespace std;

//寻找无权图的最短路径
template <typename Graph>   //封装为统一接口
class ShortestPath{

private:
    Graph &G; //图是引用
    int s; //起始点
    bool *visited; //记录dfs的过程中节点是否被标记
    int *from; //记录路径，from[i]表示查询的路径上i的上一个节点
    int *ord; //记录路径中节点的次序，ord[i]表示i节点在路径中的次序

public:
    //构造函数
  ShortestPath(Graph &graph, int s):G(graph){

       //算法初始化
       assert( s >= 0 && s < graph.V() );
       this->s = s;
       visited = new bool[graph.v()];
       from = new int[graph.v()];
       ord = new int[graph.v()];
       for(int i = 0; i < graph.v(); i++){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
  }

广度优先遍历算法：

// 无向图最短路径算法, 从s开始广度优先遍历整张图
  queue<int> q;    //q为辅助队列

  q.push( s );
  visited[s] = true;
  ord[s] = 0;
  while( !q.empty() ){
        //将队列中的首元素赋值给v
        int v = q.front();
        q.pop(); //将第一个元素取出队列

        typename Graph::adjIterator adj(G, v);
        for( int i = adj.begin(); !adj.end(); i = adj.next() ){
                if( !visited[i] ){    //判断节点是否被访问过
                    q.push(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i]  = ord[v] + 1;      //记录最短路径
                }
         }
    }
}

析构函数及其成员函数

//析构函数
  ~ShortestPath(){
        delete[] visited;
        delete[] from;
        delete[] ord;
  }
    // 查询从s点到w点是否有路径
  bool hasPath(int w) {
        assert(w >= 0 && w < G.V());
        return visited[w];
  }

   // 查询从s点到w点的路径, 存放在vec中
  void path(int w,vector<int> vec){
        assert(w >= 0 && w < G.V());
        stack<int> s;
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while(p != -1){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
       vec.clear();
       while( !s.empty() ){
                vec.push_back( s.top());
                s.pop();
       }
    }

    // 打印出从s点到w点的路径
  void showPath(int w){

        assert( w >= 0 && w < G.V() );

        vector<int> vec;
        path(w, vec);
        for( int i = 0 ; i < vec.size() ; i ++ ){
                cout<<vec[i];
              if( i == vec.size()-1 )
                    cout<<endl;
              else  cout<<" -> ";
       }
    }

    // 查看从s点到w点的最短路径长度
  int length(int w){
        assert( w >= 0 && w < G.V() );
        return ord[w];
  }
};

本作品采用《CC 协议》，转载必须注明作者和本文链接