通过邻接矩阵迭代向图中添加边

Question

我有这样的代码，它从邻接矩阵中向图中添加带有权重的边：

matrix = [[0, 1, 2, 3, 4],
          [1, 0, 5, 6, 0],
          [2, 5, 0, 0, 0],
          [3, 0, 0, 0, 6],
          [4, 0, 0, 6, 0]]


g1 = Graph(len(matrix))
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] > 0:
            g1.add_edge(i, j, matrix[i][j])

这个代码的问题是它添加了两次相同的边，f.e增加了边缘0 - 1和1 -0，0 - 2和2 - 0。我想要的是只添加一次这些边。这有可能吗？

我添加了这个打印print(f'Addind edge {i}-{j} with weight {matrix[i][j]}')语句，这样您就可以看到正在发生的事情了。输出：

Addind edge 0-1 with weight 1
Addind edge 0-2 with weight 2
Addind edge 0-3 with weight 3
Addind edge 0-4 with weight 4
Addind edge 1-0 with weight 1
Addind edge 1-2 with weight 5
Addind edge 1-3 with weight 6
Addind edge 2-0 with weight 2
Addind edge 2-1 with weight 5
Addind edge 3-0 with weight 3
Addind edge 3-4 with weight 6
Addind edge 4-0 with weight 4
Addind edge 4-3 with weight 6

Answer 1

解决这一问题的一种方法是在实际添加边缘之前，为正在添加的边缘添加一个额外的检查。例如，您可以添加一个检查，以确保边没有出现在图形中。您可以通过循环遍历图形，并在添加边缘之前检查边缘是否已经存在来完成此操作。

下面是如何做到这一点的一个示例：

g1 = Graph(len(matrix))
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] > 0:
            # check if the edge is already present
            if not g1.has_edge(i, j):
                g1.add_edge(i, j, matrix[i][j])

Answer 2

若要从邻接矩阵向图中添加边，使每个边只添加一次，可以使用以下方法：

1. 检查当前矩阵位置的值是否大于0。这表明顶点i和j之间有一条边，
2. 如果矩阵大于0，检查j是否大于i，这保证了我们只加一次每个边，因为对于无向图，边i-j与边j- i.
3. 相同，如果j大于i，则用加权矩阵将边if j加到图中。下面是如何修改代码以实现此方法的示例：

matrix = [[0, 1, 2, 3, 4],
          [1, 0, 5, 6, 0],
          [2, 5, 0, 0, 0],
          [3, 0, 0, 0, 6],
          [4, 0, 0, 6, 0]]

g1 = Graph(len(matrix))
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] > 0 and j > i:  # Check if matrix[i][j] is greater than 0 and j is greater than i
            g1.add_edge(i, j, matrix[i][j])  # Add edge i-j with weight matrix[i][j]

在进行此更改后，代码将只添加每条边一次，在打印图形中的边缘时将得到以下输出：

Addind edge 0-1 with weight 1
Addind edge 0-2 with weight 2
Addind edge 0-3 with weight 3
Addind edge 0-4 with weight 4
Addind edge 1-2 with weight 5
Addind edge 1-3 with weight 6
Addind edge 3-4 with weight 6