CODEWITHSUNDEEP
cgraphgraph-algorithm
Unknown
Unknown

Reputation: 108

Reachability in graph - C

I have implemented my graph in adjacency list. How can I estimate one vertex reachability from another when user provides indexes?

int isReachable(int nodes, int graph[nodes][nodes], int src, int dest)

Checking for direct neighbors is easy, but I struggle with implementing algorithm as whole.

Upvotes: 1

Views: 1127

Answers (1)

Dharam Budh
Dharam Budh

Reputation: 2342

Code from: http://www.geeksforgeeks.org/transitive-closure-of-a-graph/

int reach[V][V], i, j, k;

    /* Initialize the solution matrix same as input graph matrix. Or
       we can say the initial values of shortest distances are based
       on shortest paths considering no intermediate vertex. */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            reach[i][j] = graph[i][j];

    /* Add all vertices one by one to the set of intermediate vertices.
      ---> Before start of a iteration, we have reachability values for
           all pairs of vertices such that the reachability values 
           consider only the vertices in set {0, 1, 2, .. k-1} as 
           intermediate vertices.
      ----> After the end of a iteration, vertex no. k is added to the 
            set of intermediate vertices and the set becomes {0, 1, .. k} */
    for (k = 0; k < V; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++)
        {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++)
            {
                // If vertex k is on a path from i to j,
                // then make sure that the value of reach[i][j] is 1
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }

    // Print the shortest distance matrix
    printSolution(reach);
}

Upvotes: 3

Related Questions