Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def find_value(l, value):
- result = []
- for i, val in enumerate(l):
- if value == val:
- result.append(i)
- return result
- def is_cycle(edges):
- ways = ["0"]
- result = False
- last_hop = None
- while True:
- print(ways)
- for way in ways:
- ways.remove(way)
- for end_edge_index in find_value(edges[0], int(way[-1])):
- if not (str(edges[1][end_edge_index]) + way[-1]) in way:
- ways.append(way + str(edges[1][end_edge_index]))
- for way in ways:
- if way[-1] in way[0:-1]:
- result = True
- if result:
- break
- if ways[:] == last_hop:
- break
- last_hop = ways[:]
- return result
- m_size = int(input("Размер матрицы: "))
- matric = []
- for i in range(0, m_size):
- converted_string = []
- for num in input("Введите " + str(i + 1) + " срочку матрицы: ").split(" "):
- converted_string.append(int(num))
- matric.append(converted_string)
- edges = [[], []]
- for i_string in range(0, m_size):
- for i_val in range(0, m_size):
- if matric[i_string][i_val] == 1:
- edges[0].append(i_string)
- edges[1].append(i_val)
- weight = []
- for edge_index in range(0, len(edges[0])):
- weight.append(int(input("Введите вес для ребра " + str(edges[0][edge_index] + 1) +
- "-" + str(edges[1][edge_index] + 1) + ":")))
- result = [[],[]]
- while not len(weight) == 0:
- print(result)
- choosen_edge_index = weight.index(min(weight))
- result[0].append(edges[0][choosen_edge_index])
- result[1].append(edges[1][choosen_edge_index])
- weight.pop(choosen_edge_index)
- edges[0].pop(choosen_edge_index)
- edges[1].pop(choosen_edge_index)
- if is_cycle(result):
- result[0].pop()
- result[1].pop()
- print(result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement