无向图寻路问题

Question

寻路算法是按从小到大找路径的, 但是这是无环图, 如果起始节点是8或者6，终止节点是0或者3, 这个路径stack就变成空了,请问如何兼容这种反向找路径的问题

Answer 1

liuyubobobo 2022-01-25 13:53:59

课程的代码依然是适用的。

以课程代码为例：https://git.imooc.com/coding-71/coding-71/src/master/07-Graph-Basics/Course%20Code%20%28C++%29/06-Finding-a-Path  （课程中的测试用例只有 7 个节点，所以没有编号为 8 的节点）。

你可以尝试将 main 中的相关参数修改为寻找从 6 到 3 的路径：

Path<SparseGraph> path(g,6);
cout<<"Path from 6 to 3 : " << endl;
path.showPath(3);

然后运行试试看？是不是找到了从 6 到 3 的路径？然后可以是用单步跟踪的方式看一看，这个代码是如何找到的从 6 到 3 的路径？

继续加油！：）

• 提问者 宝慕林7457467 #1

  波波老师，可能是我描述的有问题, 因为*from记录的是从0开始到6的上一个节点，而0这个节点上一个节点是初始化-1的，如果从6到0，或者从4到0,寻路时,栈中将只推入0. 因为这个方法:
  
      void path(int w, vector<int> &vec){
  
          assert( hasPath(w) );
  
          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();
          }
      }
  循环第一次时，w是0, 而后p被赋值成0的from,0对应的from是-1.

• liuyubobobo 回复 提问者 宝慕林7457467 #2

  当创建 Path 的时候，第二个参数传的是 0，from 里存的才是从 0 开始到 6 的上一个节点。但如果你传的是 6，记录的就是从 6 开始的路径。依然是，请你实验一下上面的代码（注意参数的变化），看是否成功找到了从 6 到 3 的路径？

• 提问者 宝慕林7457467 #3

  理解了，谢谢波波老师.原来是我写from指针的时候有问题