（算法）找到通过所需节点集（可能使用 BFS）和 returns 到 Python 原点的最短路径

Question

我试图找到一条通过一组节点 [4,7,9]（不需要保留顺序）然后 returns 到原点（节点 1）的最短路径.我有一组边：

E = [(1, 10), (1, 11), (2, 3), (2, 10), (3, 2), (3, 12), (4, 5), (4, 12), (5, 4), (5, 14), (6, 7), (6, 11), (7, 6), (7, 13), (8, 9), (8 , 13), (9, 8), (9, 15), (10, 1), (10, 11), (10, 2), (11, 1), (11, 10), (11, 6 ), (12, 13), (12, 3), (12, 4), (13, 12), (13, 7), (13, 8), (14, 15), (14, 5), (15, 14), (15, 9)]

我尝试调整处的答案但产生了错误：

Traceback (most recent call last):
  File "C:/Users/../rough-work.py", line 41, in <module>
    graph[edge[0]].link(graph[edge[-1]])
KeyError: 15

我改编的代码如下：

class Node:
    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def link(self, node): 
        # The edge is undirected: implement it as two directed edges
        self.neighbors.append(node)
        node.neighbors.append(self)

    def shortestPathTo(self, target):
        # A BFS implementation which retains the paths
        queue = [[self]]
        visited = set()
        while len(queue):
            path = queue.pop(0) # Get next path from queue (FIFO)
            node = path[-1] # Get last node in that path
            for neighbor in node.neighbors:
                if neighbor == target:
                    # Found the target node. Return the path to it
                    return path + [target]
                # Avoid visiting a node that was already visited
                if not neighbor in visited:
                    visited.add(neighbor)
                    queue.append(path + [neighbor])

###
n = 15                    
nodes = list(range(1,n))
E = [(1, 10), (1, 11), (2, 3), (2, 10), (3, 2), (3, 12), (4, 5), (4, 12), (5, 4), (5, 14), (6, 7), (6, 11), (7, 6), (7, 13), (8, 9), (8, 13), (9, 8), (9, 15), (10, 1), (10, 11), (10, 2), (11, 1), (11, 10), (11, 6), (12, 13), (12, 3), (12, 4), (13, 12), (13, 7), (13, 8), (14, 15), (14, 5), (15, 14), (15, 9)]

# Create the nodes of the graph (indexed by their names)
graph = {}
for letter in nodes:
    graph[letter] = Node(letter)

print(graph)

# Create the undirected edges
for edge in E:
    graph[edge[0]].link(graph[edge[-1]])

# Concatenate the shortest paths between each of the required node pairs 
start = 1
path = [graph[1]]
for end in [4,7,9,1]:
    path.extend( graph[start].shortestPathTo(graph[end])[1:] )
    start = end

# Print result: the names of the nodes on the path
print([node.name for node in path])

代码可能有什么问题？我想将图形扩展到任意数量的节点，大于 26 - 字母的数量（因为我推断之前的实现仅适用于基于字符的节点）。或者，如果有更直接的方法来执行此操作，那就太好了！

谢谢，我们将不胜感激！

Answer 1

KeyError: 15 和你的行 print(graph) 应该给了你线索：后者表明你的 graph 字典只包含 14 个条目，而你的边缘在 E 明确提及 15 个独立的指数。将 n = 15 更改为 n = 16 并且有效：

[1, 10, 2, 3, 12, 4, 12, 13, 7, 13, 8, 9, 8, 13, 7, 6, 11, 1]

记住：

>>> len(list(range(1,16)))
15

（算法）找到通过所需节点集（可能使用 BFS）和 returns 到 Python 原点的最短路径

(Algorithms) Finding the shortest path that passes through a required set of nodes (possibly with BFS) and returns to the origin in Python

python-3.x

algorithm

graph-algorithm

shortest-path