2

我发现了以下内容：

给定一个有向图，找出给定图中所有顶点对 (i, j) 的顶点 j 是否可以从另一个顶点 i 到达。

这里可达意味着有一条从顶点 i 到 j 的路径。

可达性矩阵称为图的传递闭包。

该图以邻接矩阵的形式给出，例如 'graph[V][V]' 其中如果从顶点 i 到顶点 j 有一条边，或者 i 等于 j，则 graph[i][j] 为 1，否则为图[i][j] 为 0。

我们可以使用 Floyd Warshall 计算距离矩阵 dist[V][V]，如果 dist[i][j] 是无限的，则 j 不可从 i 到达，否则 j 可达且 dist[i][j] 的值将小于 V。

// Prints transitive closure of graph[][] using Floyd Warshall algorithm
void transitiveClosure(int graph[][V])
{
    /* reach[][] will be the output matrix that will finally have the shortest
      distances between every pair of vertices */
    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, 2, .. 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);
}

首先，你能解释一下为什么函数的参数是 graph[][V] 而不是 graph[V][V] 吗？

那我们为什么要初始化矩阵，它最终将在每对顶点之间具有最短距离，用graph[V][V]？

你能解释一下初始化后在for循环中做了什么吗？

我们怎么能写这个命令：reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);elsewhise？

编辑：图是布尔矩阵，还是不是？

如果是这样，那么到达不是一个布尔矩阵吗？

所以如果我们有这个命令： (reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); ) 并且如果reach[i] [j]=1 然后我们执行这个：reach[i][j]=reach[i][j]，否则我们检查 (reach[i][k] +reach[k][j]) 是否为非-零？

还是我理解错了？

4

2 回答 2

0

首先，你能解释一下为什么函数的参数是 graph[][V] 而不是 graph[V][V] 吗？

该函数以这种方式声明，因此它可以接受一个二维数组，其中一个轴的大小未知。由于邻接矩阵在定义上是方形的并且reach[V][V]是稍后定义的，我不知道他们为什么会这样定义函数。有关更多详细信息，请参阅此SO 问题。

那我们为什么要初始化矩阵，它最终将在每对顶点之间具有最短距离，用graph[V][V]？

graph定义可以通过遍历没有中间节点的单个边到达每个其他顶点的每个顶点。当我们开始算法时，这些是最短的路径，也是我们知道的从一个顶点到另一个顶点的唯一路径。通常，如果顶点无法通过直接路径彼此到达，graph则将该边定义为零（无连通性）或无限（它们之间的距离如此之大以至于无法通过）。

你能解释一下初始化后在for循环中做了什么吗？

首先，了解这一行：

reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

它问：“顶点 i 是否可以从顶点 j 到达？或者可以通过中间顶点 k 从顶点 j 到达顶点 i 吗？”

这就解释了为什么需要三个 for 循环。为什么它们像现在这样被订购？

想象一下，您有与上面相同的行，其中的 for 循环如下所示：

for i
  for j
    for k

如果是这种情况，对于每对顶点 (i,j)，您将检查这两个顶点是否可以通过某个中间顶点 k 连接。然后你就辞职了。

但是如果你必须通过两个中间顶点才能从 (i,j) 得到。上述 for 循环的排序可能不会发现这种可能性。

取而代之的是，我们用 k在外面对 for 循环进行排序，因此，找到所有k 是中间点的点对。然后我们对每个可能的中间点 k 执行此操作。有严格的方法可以证明这样做可以让你考虑两点之间的所有路径，但是，如果你想一想，我想你会发现它直觉上是正确的。

我们如何编写这个命令：reach[i][j] =reach[i][j] || （到达[i][k] && 到达[k][j]）；否则呢？

正如另一位评论员所说，您可以写：

reach[i][j] |= (reach[i][k] && reach[k][j])

你也可以写：

reach[i][j] = min(reach[i][j], reach[i][k]+reach[k][j])

这将找到两个顶点之间的最短路径的长度，前提是您的输入图使用无穷大来表示非连接顶点。

请注意：

reach[i][j] = max(reach[i][j], reach[i][k]+reach[k][j])

将是一个非常糟糕的主意。在一般图中找到最长的路径是NP-hard：我们不知道这样做的好方法，而且可能没有。但是，如果你找到了，你不仅会变得富有：整个世界都会在一夜之间改变，你会被永远铭记。

于 2015-04-10T21:58:39.893 回答
0

首先，你能解释一下为什么函数的参数是 graph[][V] 而不是 graph[V][V] 吗？

它也可以是图[V][V]。我更喜欢 graph[V][V] 因为无论如何这是预期的输入。

那我们为什么要初始化矩阵，它最终将在每对顶点之间具有最短距离，用graph[V][V]？

那是因为节点 a 和 b 之间的距离肯定最多是 a 和 b 之间的边的值（如果没有边，假设它是无限的）。例如：如果我们有图，其中 A 和 B 之间有长度为 5 的边，我们肯定知道 A 和 B 之间肯定存在长度为 5 的路径，但是可能存在更短的路径。

这里有一点需要注意。如果您只对可达性感兴趣，那么您并不关心实际距离。在这种情况下，如果不存在任何路径，则可以将值设置为 0，如果存在路径，则可以将值设置为 1。

你能解释一下初始化后在for循环中做了什么吗？

您基本上是在使用动态编程方法。解释很长，在这里阅读：http ://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

我们如何编写这个命令：reach[i][j] =reach[i][j] || （到达[i][k] && 到达[k][j]）；否则？

我们可以写成：reach[i][j] |= (reach[i][k] &&reach[k][j])

于 2015-04-10T20:12:00.410 回答