从边列表构建所有哈密顿路径 [英] Build all Hamiltonian paths from an edge list

问题描述

我无法找到从相关元组列表构建树路径的方法?我只想要每个节点被访问一次的每个路径的列表，也就是哈密顿路径.

I'm having trouble finding a way to build a tree path from a list of related tuples? I only want a list of every path where each node is visited once, aka hamiltonian path.

我一直在靠近但错过了一些路径.

I keep getting close but missing some path.

例如，假设我们有这个连接列表:

For example, let's say we have this list of connections:

connections = [(1, 4), (1, 5), (2, 5), (3, 4), (4, 1), (4, 3), (4, 5), (5, 1), (5, 2), (5, 4)]

所需的输出:

[[1,4,3], [1,4,5,2], [1,5,2], [1,5,4,3], 
 [2,5,1,4,3], [2,5,4,1], [2,5,4,3],
 [3,4,1,5,2], [3,4,5,1], [3,4,5,2], 
 [4, 3], [4,1,5,2], [4,5,1], [4,5,2],
 [5, 2], [5,1,4,3], [5,4,1], [5,4,3]
]

因此存储了每个可能的路径并且每个节点仅被访问一次:

So each possible path is stored and each node is visited only once:

这是我所拥有的，但缺少很多路径:

Here's what I have but it's missing a lot of paths:

def find_paths(current_vertex):
    if current_vertex not in current_path:
        current_path.append(current_vertex)

    possible_next_verticies = [v2 for v1,v2 in connections if v1 == current_vertex]

    # if the current vertex is in the current_path
    if current_vertex in current_path:
        # if all the possible_next_vertices are in the current_path, return
        adjacencies = [v for v in possible_next_verticies if v not in current_path]
        if not adjacencies:
            print "current_path: %s" % current_path
            if current_path not in TESTED_PATHS:
                TESTED_PATHS.append(current_path)
            current_path.remove(current_vertex)
            return

    for next_vertice in possible_next_verticies:
        if next_vertice not in current_path:
            current_path.append(next_vertice)
            find_paths(next_vertice)
            continue
        else:
            continue

    return current_path

推荐答案

好的，由于我尝试使用的数据结构，我遇到了很多麻烦，因为原始连接图中存在重复项.

OK, I was having so much trouble because of the data structure I was trying to work from, since there were duplicates in the original connections graph.

最好使用这样的数据结构:

Better is to use a data structure like this:

connections = {1: [4, 5], 2: [5], 3: [4], 4: [1, 3, 5], 5: [1, 2, 4]} 

那么下面两种算法可以从https://www.python.org/文档/论文/图表/

Then the following two algorithms can be used from https://www.python.org/doc/essays/graphs/

def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath: return newpath
    return None

以及完整路径

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

这篇关于从边列表构建所有哈密顿路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！