有向图G=（V，E）的平方是图G2=（V、E2），使得u→w在E2中当且仅当u≠w并且存在一个顶点v使得u→v和v→w处于E2。输入文件只是将边按任意顺序列为有序的顶点对，每条边都在一条单独的线上。顶点按从1到顶点总数的顺序进行编号。
*自循环和重复/平行边缘不允许
如果我们看一个输入数据的例子：
1 6
1 4
1 3
2 4
2 8
2 6
2 5
3 5
3 2
3 6
4 7
4 5
4 6
4 8
5 1
5 8
5 7
6 3
6 4
7 5
7 4
7 6
8 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），那么我会将它从指针数组中添加到链表中。我将对文件中的每个数字顶点数字执行此操作。
然而，我觉得这是非常低效的，不是最好的方法。如果有人有其他建议，我将不胜感激。
如果我做对了，你想为每个节点构建一个结果集，其中每个节点的距离为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
希望对有所帮助