Я пытаюсь решить вопрос о графиках.Однако, действительно странная ошибка происходит, когда я пытаюсь построить матрицу смежности.
Это задача: 
Это ввод в простойФормат копирования / вставки:
4 4
1 2
3 2
4 3
1 4
1 4
Это шаги, которые я уже предпринял, пытаясь решить проблему:
- Считать входные данные
- Сделать ребранапример, пара (кортеж) из двух вершин (v1, v2) выражает наличие ребра между вершинами 1 и 2.
На основании числа «n» ребер, Iсоздал квадратичную матрицу "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))
Этот отрывок гарантирует, что входы одинаковы, поскольку оба возвращают True:
print(matrix_to_be_fill==matriz_adj)
print (edges_list==in_case_edges_list)
Однако функции с одинаковыми выходами возвращают разные выходы:
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 просто есть ввод, который я показал ранее.