c - 来自有向边列表的顶点连接算法

Question

有向图 G = (V, E) 的平方是图 G2 = (V, E2) 使得 u→w 在 E2 中当且仅当 u ≠ w 并且存在顶点 v 使得两个 u→v和 v→w 在 E2 中。输入文件简单地将边以任意顺序列出为有序的顶点对，每条边在单独的行上。顶点按从 1 到顶点总数的顺序编号。

*不允许自循环和重复/平行边

如果我们看一个输入数据的例子：

那么输出将是：

1: 3 4 7 8 5 2 6
2: 5 6 3 4 1 8 7
3: 1 7 8 6 5 4
4: 5 6 8 7 3 1
5: 3 1 4 6
6: 2 7 5 8
7: 1 5 6 8 3 4
8: 6 4 3

我正在用 C 编写代码。

我的想法是遍历文件，看看它们有多少个顶点，然后分配一个指针数组。继续通过列表再次搜索行中包含 1 的位置，然后查看这些相应数字的位置。如果它不是重复的或相同的数字（1），那么我会将它从指针数组中添加到链表中。我将为文件中的每个数字顶点编号执行此操作。

但是，我觉得这非常低效，而且不是最好的方法。如果有人有任何其他建议，我将不胜感激。

score 2 · Accepted Answer

如果我做对了，您想为每个节点构建一个结果集，其中声明了每个节点距离为 1 和 2 的所有节点。

因此，可以将边缘保存在位数组的邻接矩阵中，其中当存在边缘时位为 1，否则为 0。

现在可以将这个矩阵与自身相乘。在这种情况下，乘法意味着您可以对行和列进行 AND。

一个小例子（抱歉，不知道如何正确插入矩阵）：

0 1 0   0 1 0   0 0 1
0 0 1 x 0 0 1 = 1 1 0
1 1 0   1 1 0   0 1 1

该矩阵包含一个用于通过两步到达的所有节点的矩阵。简单地说，它是两步而不是一步的邻接矩阵。如果您现在将此矩阵与初始矩阵进行 OR，您将拥有一个包含所有长度为 1 和 2 的路径的矩阵。

这种方法有很多优点。在第一位操作非常快。cpu 使您的计算瘫痪，如果找到一对结果矩阵单元格，您可以停止结果矩阵单元格。

此外，有据可查的是如何并行计算矩阵乘法。

您可以轻松计算所有其他路径长度。对于长度 k，必须计算：

A^k = A^(k-1) * A

希望有帮助

1 回答 1