Блог

Мне нужно написать код, который сообщает, является ли цикл гамильтоновым или нет.

Сначала у меня есть два текстовых файла:

1.файл: Первая строка содержит количество вершин и ребер, в то время как остальная часть представляет собой пару из двух вершин, которые соединены.Например, 0 1 означает, что между этими двумя есть граница.

2.файл: строка с числами (вершинами), где нам нужно проверить, является ли это циклом Гамильтона или нет.

Прежде всего, как записать график без ненаправленных циклов? Поскольку я не смог его получить, это выдает мне ошибку.

Поскольку я пытался:

 def read_graph(f,l):
"""
Read a graph from a text file.

:param f: the file to read
:return: the edge-list, the starting and final vertex of path
"""

header = f.readline().split()
n, m = [int(s) for s in header]

graph = dict((i, []) for i in range(n))
for j in range(m):
    edge = f.readline().split()
    u, v = [int(s) for s in edge]
    graph[u].append(v)
"second file"
header2=l.readline().split()
k=[]
for s in header2:
    k.append(s)
graph2=dict((i,[]) for i in range (len(k)))
for g in range(len(k)-1):
    edge2=l.readline().split()
    w,z=[int(s) for s in edge2]
    graph2[w].append(z)


return graph, graph2




 ......


if __name__ == '__main__':
    import sys
    with open(sys.argv[1], 'r') as f:
        with open(sys.argv[1], 'r') as l:
            graph = read_graph(f,l)
        print(graph)
  

Второй вопрос:

Как вы проверяете, является ли цикл гамильтоновым или нет? Сначала я планирую проверить, действительно ли это цикл или нет, затем, если это так, проверьте, встречается ли вершина только одна.
Есть ли что-нибудь еще, что я должен сделать, чтобы получить свой ответ, совет или более простой способ?

Спасибо за ответ.