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

一、介绍

寻路算法是用来获取两节点之间的路劲问题，它是基于图的深度优先遍历而来的，在图的遍历过程中，每当遍历到一个节点是，会使用一个from数组用来记录该节点的上一个节点，与此同时我们会使用一个栈(先进后出），将from数组记录的节点依次放入栈中，然后依次再从栈中取出栈顶元素将其放入一个队列中，最后对队列中元素依次索引出就可得到相应节点遍历的路径了。

例如：

我们要获取节点0到节点6之间遍历的路径

使用from数组：

使用深度优先遍历后就会得到

from[6] = 4

from[4] = 3

from[3] = 5

from[5] = 0

from[0] = 0

然后使用栈，将其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<<"->";}}
};