正确更改邻接矩阵的值以表示无向图

Question

我正在尝试解决有关图表的问题。但是，当我尝试构建邻接矩阵时发生了一个非常奇怪的错误。

这是任务：

这是一种简单的 copy/paste 格式的输入：

到目前为止，这些是我尝试解决问题的步骤：

读取输入数据
使边成为两个顶点的一对（元组），例如，(v1, v2) 表示顶点 1 和 2 之间有一条边。
基于"n"条边，我创建了一个"nxn"二次矩阵。我把所有的项目都填成了0。在下一步中，如果顶点之间存在连接，我将尝试将“0”更改为“1”。

观察：我创建了两个函数。一个是创建一个要填充的邻接矩阵。另一个名为 fill_matrix 以在适当的时候将零 (0) 更改为一 (1)。
现在就是问题出现的地方了。我尝试遍历边缘并更改邻接矩阵。

然而，奇怪的事情发生了。具有相同参数的相同函数提供不同的输出。我真的不明白为什么会这样！

到目前为止，这是我的代码：

#Uses python3

import sys

input = sys.stdin.read()
#print ("input", input)

data = list(map (int, input.split()))
#print ("data", data)

nodes_num = data[0]
#print ("number of nodes", nodes_num)

edges_num = data[1]
#print ("number of edges", edges_num)

data = data[2:]
#print ("data withou initial numbers", data)

vertex_start = data[-2]
#print ("initial node", vertex_start)

vertex_end = data[-1]
#print ("final node", vertex_end)

data_edges = data[0:len(data)-2]
#print ("list with the relation of the edges", data_edges)

# this function cnverts the list of edges in appropriate pairs as tupples
def make_edge_pairs(edges_list):

    edges_list_even = edges_list[::2]
    edges_list_odd = edges_list[1::2]
    # using zip function to interlacte odds and events as proper pairs
    edges_tuples_objects = zip(edges_list_even,edges_list_odd)
    edges_list_tuplas = [ ]

    for pair in edges_tuples_objects:

        edges_list_tuplas.append(pair)

    return edges_list_tuplas

def create_adjacency_matrix(vertex_num):

    adj_matrix = []
    lines_list = []

    for i in range(0,vertex_num):

        lines_list.append(0)

    for j in range(0,vertex_num):
        adj_matrix.append(lines_list)

    return adj_matrix

matriz_adj = create_adjacency_matrix(nodes_num)
print ("matriz adj",matriz_adj)

in_case_edges_list = make_edge_pairs(data_edges)
print ("in_case_edges_list", in_case_edges_list)

edges_list = [(1, 2), (3, 2), (4, 3), (1, 4)]
print ("edges_list", edges_list)

matrix_to_be_fill = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print("matrix_to_be_fill",matrix_to_be_fill)

print(matrix_to_be_fill==matriz_adj)
print (edges_list==in_case_edges_list)

def fill_matrix(matrix, edges_list):

    #print (matrix, edges_list)

    for tupla in edges_list:
       lin = (tupla[0]) - 1
       col = (tupla[1]) - 1
       matrix[lin][col] = 1
       matrix[col][lin] = 1
    return matrix

print (fill_matrix(matriz_adj,in_case_edges_list))
print (fill_matrix(matrix_to_be_fill,in_case_edges_list))

此摘录保证输入相同，因为两者 return 正确：

print(matrix_to_be_fill==matriz_adj)
print (edges_list==in_case_edges_list)

然而，具有相同输出的函数return不同的输出：

print (fill_matrix(matriz_adj,in_case_edges_list))
print (fill_matrix(matrix_to_be_fill,in_case_edges_list))

我希望在这两种情况下都将此列表列表作为输出：

[[0, 1, 0, 1],
 [1, 0, 1, 0],
 [0, 1, 0, 1],
 [1, 0, 1, 0]]

这是顶点之间关系的正确表示！

我知道 Python 中还有其他形式表示顶点和边之间的关系。但我想解决这个问题并继续研究这个方法。

我运行代码为：

python3 reachability.py < sample_1.txt

文件sample_1.txt只有我之前显示的输入。

Answer 1

问题是每一行都是同一个列表：

def create_adjacency_matrix(vertex_num):

    adj_matrix = []
    lines_list = []

    for i in range(0,vertex_num):

        lines_list.append(0)

    for j in range(0,vertex_num):
        adj_matrix.append(lines_list)

    return adj_matrix

将adj_matrix.append(lines_list)更改为adj_matrix.append(lines_list[:])

或写成：

def create_adjacency_matrix(vertex_num):

    adj_matrix = []

    for j in range(0,vertex_num):
        lines_list = []

        for i in range(0,vertex_num):
            lines_list.append(0)

        adj_matrix.append(lines_list)

    return adj_matrix

正确更改邻接矩阵的值以表示无向图

Correctly changing the values of an adjacency matrix to represent an undirect graph

python

graph-theory

adjacency-matrix

python-3.x