0

我正在编写一个 C 程序来查找传递性。在二维数组中，如果 adj[0][1] = 1 和adj[1][2] = 1，我也想标记adj[0][2]为1。这应该适用于矩阵中的任何传递关系。

请为此提供一些代码。

    adj_matrix[j1][j2]=1;

    for(i=0;i<26;i++)
    {
        if (adj_matrix[i][j1])
        adj_matrix[i][j2]=1;

    }
    for(i=0;i<26;i++)
    {
        if(adj_matrix[j2][i])
        {
        adj_matrix[j1][i]=1;
        }
    }
4

3 回答 3

1

你想要的是一个“传递闭包算法”

Floyd-Warshall 算法就是其中一个很好的例子，尽管还有很多（很多）其他算法，例如Johnson 算法。在 Google Scholar 上进行快速搜索会为您指明其他一些来源和更多技术描述。

原始形式的 Floyd-Warshall 算法的代码（找到每个连接点之间的最短路径）是：

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );

为您的使用场景修改此代码给出：

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   if(dist[i][k] && dist[k][j])
      dist[i][j] = 1;

注意这里的下标顺序。具有此顺序的下标满足动态规划的标准，该标准确保路径逐渐改进并且始终是最优的。

时间复杂度为 O(N^3)。

于 2012-12-08T12:42:06.870 回答
1

我相信这会奏效：

reachable_matrix = adj_matrix
length_of_path = 1

while(length_of_path < (N - 1)) {
    for(i = 0; i < N; ++i) {
        for(j = 0; j < N; ++j) {
            tmp_matrix[i][j] = 0;
            for(k = 0; k < N; ++k) {
                tmp_matrix[i][j] ||= reachable_matrix[i][k] && reachable_matrix[k][j]; // Can I reach from i to j through k?
            }
        }
    }
    reachable_matrix = tmp_matrix;
    length_of_path *= 2;
}

正如理查德评论的那样，这相当于计算图的可遍历性。

您可以将其视为一个数字，表示从 from到adj_matrix[i][j]有多少​​条长度为 1 的路径。然后（这是 的次方的邻接矩阵）告诉您在任意两个两个节点之间至少有多少条长度路径。ijadj_matrix ** lll

我的代码中的内部循环（使用变量 i、j 和 k 循环）基本上是乘以reachable_matrixbyreachable_matrix并将其存储tmp_matrix在仅在其真值上。

外环保持平方reachable_matrix，而它被提升到的功率（我们检查的路径长度）小于N - 1. 停止N - 1就足够了，因为如果你有这个长度的路径，这意味着你正在访问图中的所有节点。具有更多步骤的路径必然包含循环。另一方面，我并没有完全执行二进制求幂以使事情变得简单（我认为它的效率会低一些，但我不确定）并且因为尝试更长的路径不会造成任何伤害。

总体而言，该算法的复杂度为 O(log(N) * N**3)。

于 2012-12-08T12:05:16.570 回答
0

请让我知道这是否正确。

for(i=0;i<26;i++) 
for(j=0;j<26;j++)
for(k=0;k<26;k++)
if(adj_matrix[i][j] && adj_matrix[j][k])
adj_matrix[i][k]=1;
于 2012-12-08T06:47:11.360 回答