圖中的可達性 - 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); 
}