c - 邻接矩阵中的传递关系

Question

我正在尝试确定两个元素之间的传递关系。我正在用 c 编码。

例如：a->b 由第 1 行第 2 列的邻接矩阵中的“1”表示。

所以如果 a->b 和 b-> c 和 c->d

我想确定是否 a->d。无需更新邻接矩阵。

我采用的方法：检查与 a 对应的行中的所有 1。假设第二列中有一个 1，即 b。[(a->b)] ，现在检查 b->d 是否继续检查 B 行中的所有 1 并继续到第 26 行。

我并不真正关心复杂性。我只是希望实现这一点。

Answer 1

您需要实现广度优先搜索或深度优先搜索。从 开始，到达或用尽所有选项时a停止。d

在您的情况下，深度优先搜索更容易实现，因为“普通”C缺少广度优先搜索所需的内置动态队列。

如果您不关心效率并且不介意更新矩阵，请实现Floyd-Warshall 算法：它是专门为邻接矩阵制定的，只需五行即可实现：

for (int k = 0 ; k != N ; k++)
    for (int i = 0 ; i != N ; i++)
        for (int j = 0 ; j != N ; j++)
            if (matrix[i][k] && matrix[k][j])
                matrix[i][j] = 1;

运行此算法后，结果matrix包含原始算法的传递闭包。