在图中查找所有长度为 2 的路径

Question

我试图创建一种算法来查找所有长度为 2 的路径，但它似乎无法正常工作：

input_split = input().split(' ')
node_count = int(input_split[0])
input_count = int(input_split[1])
items = np.zeros((node_count, node_count), dtype=np.int32) # matrix of adjacency
for j in range(input_count):
    split = input().split(' ')
    x = int(split[0]) - 1 # convert 1 based coordinates to 0 based
    y = int(split[1]) - 1
    items[x][y] = 1
    items[y][x] = 1
result = np.linalg.matrix_power(items, 2)
result_sum = int(np.sum(result) / 2) # reverse paths are counted only once
print(result_sum)

示例输入：

结果应该是 11，但它打印出 18。

Answer 1

您正在计算保送，其中包括保送 6-7-6（不是 P2）

此讨论可能会有所帮助： https://math.stackexchange.com/questions/1890620/finding-path-lengths-by-the-power-of-adjacency-matrix-of-an-undirected-graph

Answer 2

您在计算邻接矩阵的平方时走在了正确的轨道上。取幂后，您将得到如下所示的结果矩阵：

[[2 1 1 1 0 1]
 [1 4 1 0 2 0]
 [1 1 2 1 0 1]
 [1 0 1 2 0 2]
 [0 2 0 0 2 0]
 [1 0 1 2 0 2]]

首先，您需要从该矩阵中排除所有对角线条目，因为那些表示不是路径的步行，因为它们的起始节点和结束节点相同。请注意，对于长度 2，这是节点重复的唯一方式。

由于对称性，其他条目只需计算一次。所以只看矩阵的右上三角

一种方法是：

result_sum = 0
for i in range(input_count - 1):
    for j in range(i + 1, input_count - 1):
        result_sum += result[i][j]
print(result_sum) # prints 11

更多 Pythonic 方式，单行使用 numpy.trace():

result_sum = (np.sum(result) - np.trace(result)) // 2

在图中查找所有长度为 2 的路径

Find all paths of length 2 in a graph

python

algorithm

graph

path-finding