图的广度优先遍历

一、介绍

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

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

1. 无权图的最短路径
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];}
};