图论系列之「广度优先遍历及无权图的最短路径(ShortPath)」

图的广度优先遍历

一、介绍

  1. 广度优先遍历
    广度优先遍历从某个顶点 v 出发,首先访问这个结点,并将其标记为已访问过,然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ,并将其标记为已访问过,然后将 {vi,…,vj} 中的每一个节点重复节点v的访问方法,直到所有结点都被访问完为止。分为三个步骤:
  • 使用一个辅助队列,首先将第一个节点v放入队列,并标记也被访问,然后检测队列是否为空
  • 如果队列不为空时,将队列的第一个元素取出,并将与该节点相连且未被访问的节点加入队列,并将这些节点进行标记
  • 当队列为空时,就完成了图的广度优先遍历
  1. 无权图的最短路径
    无权图的最短路劲,是基于图的广度优先遍历而来的,是指图中两节点间最短的路径,通过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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!