algorithmgraph
algorithm, c, graph
Source
Edit
History

稀疏图-寻路

Catalogue
  1. 1. 流程图
  2. 2. 解析
  3. 3. 查看路径

寻路的实现是在遍历图的过程中增加一个数组from，from[i]记录了到i节点的源节点

例如: 0 - 2 由0开始访问到节点2，那么有: from[2] = 0

流程图

从0开始遍历整个图，默认初始化为from[0] = -1 -> from[2] = 0

from[4] = 2 -> from[1] = 4

from[3] = 1 结束所有遍历

有了from路径以后，就可以查到任意的路径信息了

解析

先初始化visited 和 from 等两个数组，分别用来记录是否节点被访问，以及访问路径关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
visited = new bool[5];
from    = new int[5];
for(int i = 0; i < 5; i ++){
    from[i] = -1;
    visited[i] = false;
}
graph.addEdge(0,2,1);
graph.addEdge(1,3,1);
graph.addEdge(1,4,1);

graph.addEdge(2,0,1);
graph.addEdge(3,1,1);
graph.addEdge(3,4,1);

graph.addEdge(4,1,1);
graph.addEdge(4,3,1);

构建如下图:

从2节点开始进行寻路,保存了2开始的所有路径

1
2
int p = 2;
depth_first_search(p);

直接判断是否存在2 - 4节点的路:

1
2
if(!visited[3])
    cout << "不存在" <<endl;

因为从2开始的遍历，是无法遍历到4的，所以from [4]肯定是-1所以2-4不通

查看路径

根据上面的测试用例，在新增一条关系使得该图为一个完整的单连通分量图

1
graph.addEdge(2,4,1);

假入我们从0节点开始寻路，那么有如下From表

查看0-3的路线

1
2
3
4
5
6
7
int i = 3;
cout << "3 " ;
while(i != -1 && i != from[i] && from[i] != -1){
    cout << "->";
    cout << from[i];
    i = from[i];
}

输出结果

1
3 -> 1 -> 4 -> 2 -> 0