图中的可达性 - C

Question

我已经在邻接表中实现了我的图表。当用户提供索引时，如何估计一个顶点与另一个顶点的可达性？

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

检查直接邻居很容易，但我很难实现整个算法。

Answer 1

代码来自：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);
}

图中的可达性 - C

Reachability in graph - C

c

graph

graph-algorithm