python-3.x 通过迭代邻接矩阵向Graph添加边

xytpbqjk  于 2022-12-05  发布在  Python
关注(0)|答案(2)|浏览(129)

我有这样的代码,它添加一个权重的边到一个图从邻接矩阵:

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])

这段代码的问题是,它添加了两次相同的边,例如,它添加了0 - 11 -00 - 22 - 0。我想要的是只添加一次这些边。这可能吗?
我添加了这个print 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
pepwfjgg

pepwfjgg1#

解决此问题的一种方法是,在实际添加边之前,为正在添加的边添加一个附加检查。例如,可以添加一个检查以确保该边尚未出现在图形中。为此,可以在添加边之前循环遍历图形并检查该边是否已出现。
以下是如何执行此操作的示例:

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])
j0pj023g

j0pj023g2#

要从邻接矩阵向图形添加边,以便每条边只添加一次,可以使用以下方法:
1.检查当前矩阵[i][j]位置的值是否大于0。这表示顶点i和j之间存在权重矩阵为[i][j]的边。
1.如果matrix[i][j]大于0,检查j是否大于i。这确保了我们只将每条边添加一次,因为对于无向图,边i-j与边j-i相同。
1.如果j大于i,则将边i-j添加到权重矩阵为[i][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

相关问题