首页 文章

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

提问于
浏览 次
1

我正在尝试实现一个函数 pathExists ，它接收图形ADT 'g'作为输入，以及两个顶点 a 和 b . 如果两个顶点之间存在路径，则函数返回1，否则返回0. I 'm unsure how exactly to do this. I' ve实现了深度优先搜索（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); 
        }
    }

}
c algorithm graph-theory graph-traversal

1 回答

  • 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;
}
    回复于

相关问题