def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not start in graph:
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
for path in find_all_paths(petersen, -1, -2):
if len(path) == len(petersen):
print(path[1:-1])
import random
ham_paths = [path[1:-1] for path in find_all_paths(petersen, -1, -2)
if len(path) == len(petersen)]
ham_path = random.choice(ham_paths)
然后我们将使用networkx包来绘制图形和选择的路径。在
import networkx
g = networkx.Graph()
for k, vs in petersen.items():
for v in vs:
if v in [-1, -2] or k in [-1, -2]:
continue
if abs(ham_path.index(k) - ham_path.index(v)) == 1:
g.add_edge(k,v, color='red', width=1.5)
else:
g.add_edge(k,v, color='black', width=0.5)
要计算Petersen图中的哈密顿图,我们可以使用this answer中的解
我忘了彼得森图是否与它们的顶点置换同构,所以我假设它们不是。因此,我们将添加两个连接到原始图的每个顶点的新顶点,而不是搜索构成路径末端的成对顶点。因此,如果原图中存在一条哈密顿路径,那么它将存在于这个扩展图中,只要去掉两个额外的顶点(-1)和(-2)。在
^{pr2}$现在我们可以应用帖子中的算法:
由于该算法返回给定顶点之间所有路径的列表,我们将仅将其过滤为哈密顿路径,并切断多余的顶点。在
当然,这可能更有效,但我将优化留给您或其他人。在我看来,对于像彼得森这样的小图形来说,它运行得很快。在
绘图
我们随机选择一条路径并将其存储在
ham_path
变量中。然后我们将使用
networkx
包来绘制图形和选择的路径。在我们创建一个
networkx
图,哈密顿路径中的每条边都将被涂成红色和粗体。另一方面,每一个边缘都会变薄变黑。我们也不希望在我们的绘图中额外的顶点。在相关问题 更多 >
编程相关推荐