如何使用递归来确定图中两个节点之间是否存在路径？

Question

我正在尝试实现一个函数 pathExists，它接受图形 ADT 'g' 作为输入，以及两个顶点 a 和 b。如果两个顶点之间存在一条路径，则函数 returns 1，否则它 returns 0。我不确定该怎么做。我在下面实现了深度优先搜索 (DFS) 算法，该算法将生成 int *visited，一个包含节点访问顺序的数组。我只是想知道如何使用此算法实际编写 pathExists 函数。谢谢！

编辑：尝试-

void dfsR(Graph g, int v); 
int *visited;  // array of visited
int order; 


int PathExists(Graph g, int src, int dest)
{

    int i;
    order = 1; 
    visited = malloc(sizeof(int)*g->nV); 

    for(i=0; i<g->nV; i++){
        visited[i] = -1; 
    }

    dfsR(g, src);
    int connected = 0; 


    if(visited[dest]!=-1){
        connected = 1;
    }


   return connected;
}

void dfsR(Graph g, int v){ 

    visited[v] = order++; 
    int w; 
    for(w=0; w<g->nV; w++){
        if(!hasEdge(g, v,w)){
            continue; 
        }
        if(!visited[w]){
            dfsR(g, w); 
        }
    }

}

Answer 1

我会建议这个更快的解决方案。第一个提示是，如果您已经访问了目标节点，或者距离目标节点仅一跳，请避免浪费时间。第二个提示是尽可能少地使用全局变量（作为一般规则）。因此，我提出的解决方案如下：

typedef unsigned char bool;
#define true  1
#define false 0

bool dfsR(Graph g, int v, int dest, bool * visited);

bool PathExists(Graph g, int src, int dest)
{
    bool connected = false;  // result
    bool * visited = 0;  // array of visited nodes

    if (src == dest) {
        return true;
    }

    // initialize the support array
    visited = malloc(g->nV);
    memset(visited, false, g->nV);

    // call the recursive depth first search
    connected = dfsR(g, src, dest, visited);

    // free the memory from the support array
    free(visited);

    return connected;
}

bool dfsR(Graph g, int v, int dest, bool * visited){ 
    visited[v] = 1;

    // check if there is a direct edge toward dest before going on with the recursion
    if (hasEdge(g, v, dest)) {
        return true;
    }
    // try to find it recursively
    bool connected;
    for(int w=0; w<g->nV; w++) {
        if(hasEdge(g, v, w) && !visited[w]) {
            if (dfsR(g, w, dest, visited)) {
                return true;
            }
        }
    }
    return false;
}

如何使用递归来确定图中两个节点之间是否存在路径？

How to use recursion to determine if path exists between two nodes in graph?

c

algorithm

graph-theory

graph-traversal