图论系列之「基于深度优先遍历的寻路算法 (Path) 」

基于深度优先遍历的寻路算法

一、介绍

寻路算法是用来获取两节点之间的路劲问题,它是基于图的深度优先遍历而来的,在图的遍历过程中,每当遍历到一个节点是,会使用一个from数组用来记录该节点的上一个节点,与此同时我们会使用一个栈(先进后出),将from数组记录的节点依次放入栈中,然后依次再从栈中取出栈顶元素将其放入一个队列中,最后对队列中元素依次索引出就可得到相应节点遍历的路径了。
例如:
我们要获取节点0到节点6之间遍历的路径
使用from数组:
使用深度优先遍历后就会得到
from[6] = 4
from[4] = 3
from[3] = 5
from[5] = 0
from[0] = 0
图论系列之「基于深度优先遍历的寻路算法 (Path) 」
然后使用栈,将其from[i]依次放入栈中,在依次取栈顶元素放入队列中,就可得到:0,5,3,4,6

二、代码实现

深度优先遍历逻辑不变

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

using namespace std;

//路径查询算法
template <typename Graph>
class Path{

private:
    Graph &G; // 图的引用
    int s; // 起始点
    bool* visited; // 记录dfs的过程中节点是否被访问
    int * from; // 记录路径, from[i]表示查找的路径上i的上一个节点

 //图的深度优先遍历  
    void dfs(int v){
        visited[v] = true;

    typename Graph::adjIterator adj(G, v);
    for( int i = adj.begin(); !adj.end(); i = adj.next){
         if( !visited[i] ){
              from[i] = v;
              dfs(i);
         }
     }
   }

 public:
    //构造函数,寻路算法,寻找graph从s点到其他的路径
    Path(Graph &graph, int s):G(graph){
         assert( s >= 0 && s < G.V() );

         visited = new bool[G.v()];
         from = new int[G.V()];
         for(int i = 0; i < G.v(); i++){
            visited[i] = false;
            from[i] = -1;
         }
         this->s = s;
        //寻路算法
         dfs(s);
  }

   ~Path(){
        delete[] visited;
        delete[] from;
  }

提供的操作:

  //查询从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(hasPath(w));
      // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        stack<int> s;
        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(hasPath(w));

         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<<"->";
         }
   }
};


本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

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