主页 / 问题 / 1301371
Accepted
kontsev_
Asked:2022-07-02 22:45:10 +0000 UTC2022-07-02 22:45:10 +0000 UTC

汉密尔顿循环的构造

  • 772

给定一个有向图，需要构造一个哈密顿圈。我不知道为什么程序不能正常工作。例如：

顶点 = 5
边 = 12
0 4
0 1
1 2
2 1
2 3
3 2
3 4
4 3
0 3
3 0
0 2
4 1
输出：0,1,2,3,4
预期结果：0,4,1, 2、3

n = int(input('Vertices: '))
m = int(input('Edges: '))
adj = [[0] * n for _ in range(n)]

for i in range(m):
    k, l = map(int, input().split())
    adj[k][l] = 1

used = [False] * n
path = []
def hamilton (v):
        path.append(v)
        if len(path) == n:
            if adj[path[0]][path[-1]] == 1:
                return True
            else:
                path.pop()
                return False
        used[v] = True
        for next in range(n):
            if adj[v][next] == 1 and not used[next]:
                if hamilton(next):
                    return True
        used[v] = False
        path.pop()
        return False

for i in range(n):
    hamilton(i)
    print (path)
    path.clear()
python

2 个回答

  1. Best Answer

    程序输出一个不正确的答案，因为条件不正确if adj[path[0]][path[-1]] == 1，应该写成if adj[path[-1]][path[0]] == 1。

    • 1 
  2. def hamiltomian_circuit(start, vertices, graph):
    result = [start]
    while result:
        if graph[result[-1]]:
            vertex = graph[result[-1]].pop()
            if vertex not in result:
                result.append(vertex)
        else:
            del graph[result[-1]]
            result.pop()
        if len(result) == vertices:
            break
    return result            


vertices = 5
edges = ['0 4', '0 1', '1 2', '2 1', 
         '2 3', '3 2', '3 4', '4 3', 
         '0 3', '3 0', '0 2', '4 1']
origin_graph = {}
for edge in edges:
    source, destination = edge.split()
    if source not in origin_graph:
        origin_graph[source] = []
    origin_graph[source].append(destination)

path = []
for source in origin_graph:
    path = hamiltomian_circuit(source, vertices, origin_graph.copy())
    if path:
        break
print(' '.join(path))  # 0 2 3 4 1 - результат другой, но соответствует условию
    • 0

相关问题