CODEWITHSUNDEEP
calgorithmgraph-theorygraph-traversal
Programmer
Programmer

Reputation: 1294

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

I'm trying to implement a function pathExists which takes in a graph ADT 'g' as input, as well as two vertices a and b. If a path exists between the two vertices, then the function returns 1, otherwise it returns 0. I'm unsure how exactly to do this. I've implemented a Depth First Search (DFS) algorithm below which will generate int *visited, an array containing the order in which nodes are visited. I'm just wondering how I can use this algorithm to actually write the pathExists function. Thanks!

EDIT: Attempt- 

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); 
        }
    }

}

Upvotes: 1

Views: 2402

Answers (1)

Roberto Trani
Roberto Trani

Reputation: 1227

I would suggest this faster solution. The first hint is to avoid to waste time if you have already visited the destination node, or you are at one hop from it. The second hint is to use as less global variables as possible (as a general rule). Hence, my proposed solution is the following one:

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;
}

Upvotes: 1

Related Questions