//深度优先找出从顶点u到顶点v的简单路径,pre用来存储路径
void one_path(adjMatrix *G, int u, int v, int *pre){
int i;
pre = (int *)malloc(G->vexnum * sizeof(int));
for (i = 0; i < G->vexnum; i++) {
pre[i] = -1;
}
pre[u] = u;//不是-1表示被访问过了
cout<<DFS_path(G, u, v, pre)<<endl;
free(pre);
}
int DFS_path(adjMatrix *G, int u, int v, int *pre){
int j;
for (j = firstadj(G, u); j > 0; j = nextadj(G, u, j)) {
cout<<"j="<<j<<endl;
if (pre[j] == -1 || j==v) {
pre[j] = u;//出发索引存在到达的点上
if (j == v) {
cout<<"find path is:"<<endl;
return 1;
}else if(DFS_path(G, j, v, pre)){//递归调用，如果 临接点->目的地 存在路径则返回，不再去寻找别的路径
return 1;
}/*{
DFS_path(G, j, v, pre);//in this case it will always return 0 except there is only one step from start to end. last called will return 1,first called will return 0;
}*/
}
}
return 0;
}
//找到u的第一个邻接点位置
int firstadj(adjMatrix *G, int u){
for (int i = 0; i < G->vexnum; i++) {
if (G->arcs[u][i].adj < INFINITY) {
return i;
}
}
return 0;
}
//找到当前邻接点的下一个邻接点
int nextadj(adjMatrix *G, int u, int now){
now++;
for (int i = now; i < G->vexnum; i++) {
if (G->arcs[u][now].adj < INFINITY) {
return i;
}
}
return 0;
}
图之深度优先找到简单路径
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 两种遍历 图的遍历分为深度优先搜索(Depth First Search)和广度优先搜索 深度优先搜索(DFS) ...
- 说真的，拥有梦想的人太多了，可在命运闭上眼睛时候，仍旧苦苦坚守的能有几个？很多时候，我们沦落为平庸的人，呼应了北岛...
- 梦境，是内心追求的寄托，也是现实生活的折射。 浪漫的情怀自古就有，残缺与遗憾却是人生常态。疲惫的求与不得之后，自嘲...
