C 试基于图的深度优先搜索策略写一算法 判别以邻接表方式存储的有向图中是否存在由顶点 vi到顶点 vj的路径 i≠j 。_试基于图的深度优先策略写一算法

严蔚敏 数据结构 7.22

给大佬跪了，这个是要返回的，但是还要兼顾顶点上连接的其他节点，不能一个不行就不行，所以走的路径只返回走通的，走不通的略过，直到最后，能走到最后就说明根本没有通的路径，就这样。

也可以把这个点上的所有连接点用深度遍历走一次，然后看看记录是否点亮的数组里是不是亮着的，亮着就说明是有路径，不亮就没有
这里邻接表相关

//是否存在src到dest的路径
bool isExitedPathDFS(Graph G,int src, int dest){
    
    int a;
    EdgeNode *p;
    //如果相同就返回真
    if(src == dest) {
        return true;
    }
    //既然不同走这里，点亮第src元素
    visited[src] = true;
    p = G.adjlist[src].firstedge;
    //用一个for循环来遍历邻接表上所有连着src元素的点
    for (; p; p = p->next) {
        a = p->adj_vex_index;
        //因为要将每一个结果都要返回，
        //~~如果只是冒然返回isExitedPathDFS的结果，那有一条走不通就都走不通了~~ 
        //如果没有!visited[a]，会陷入死循环
        //所以这里答案巧妙地做成在if语句里走这个结果，而且只需要对的结果，错误的一律不反回
        if(!visited[a] && isExitedPathDFS(G, a, dest)) {
            return true;
        }
//        if(!visited[a]){
//            if(isExitedPathDFS(G, a, dest)){
//                return true;
//            }
//        }
    }
    //执行到了最后就说明真没有
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

答案是怎么想的？服气