我已经为此苦苦挣扎了一段时间。 给定一组节点：
nodes = { ('A','B'),
('B','C'),
('C','D'),
('C','E'),
('B','E'),
('C','F') }
实现以下目标的最佳方法是什么：
A
|
B
_________|_________
| |
C E
_____|_____ |
| | | C
D E F ____|____
| |
D F
我可以看到：
the routes from A -> B:
A -> B
the routes from A -> C:
A -> B -> C
A -> B -> E -> C
the routes from A -> D:
A -> B -> C -> D
A -> B -> E -> C -> D
etc...
我这样做的原因纯粹是因为我想了解如何操作。
我知道 bfs 找到了最快的路线，（我想我可能在获取孩子功能中使用类似的东西）
但我不知道循环/递归运行图形的最佳方法。我应该使用字典并使用键/值还是列表。或设置...
def make_graph(nodes):
d = dict()
for (x,y,*z) in nodes:
if x not in d: d[x] = set()
if y not in d: d[y] = set()
d[x].add(y)
d[y].add(x)
return d
我在这里使用 *z，因为元组实际上会包含一个浮点数，但目前我试图让事情变得简单。
def display_graph(nodes):
for (key,val) in make_graph(nodes).items():
print(key, val)
# A {'B'}
# C {'B', 'E', 'D', 'F'}
# B {'A', 'C', 'E'}
# E {'C', 'B'}
# D {'C'}
# F {'C'}
getChildren 函数查找节点根的所有可能端点：
def getchildren(noderoot,graph):
previousnodes, nextnodes = set(), set()
currentnode = noderoot
while True:
previousnodes.add(currentnode)
nextnodes.update(graph[currentnode] - previousnodes)
try:
currentnode = nextnodes.pop()
except KeyError: break
return (noderoot, previousnodes - set(noderoot))
在本例中为 A：
print(getchildren('A', make_graph(nodes)))
# ('A', {'C', 'B', 'E', 'D', 'F'})
在使用程序语言编码之前，您需要正确抽象问题。
首先，您需要考虑图形的属性，例如循环/非循环，有向/无向等。
然后，您需要选择一种方法来相应地解决问题。 例如，如果它是一个非循环的、无向的和连接的图，那么你可以将图表示为一棵树，并使用BFS或DFS来遍历它。
最后，在你考虑了所有这些之后，你可以更容易地把它放到代码中。就像您已经执行的操作一样，您可以为每个节点提供一个存储所有邻居的列表，并使用 BFS 遍历树。
谢谢大家，问题解决了。我需要编写的函数如下。
def trace_graph(k, graph):
""" takes a graph and returns a list of lists showing all possible routes from k """
paths = [[k,v] for v in graph[k]]
for path in paths:
xs = path[:-1]
x = path[-1]
for v in graph[x]:
if v not in xs and path + [v] not in paths:
paths.append(path + [v])
paths.sort()
return paths
for path in trace_graph('A', make_graph(nodes)):
print(path)
['A', 'B']
['A', 'B', 'C']
['A', 'B', 'C', 'D']
['A', 'B', 'C', 'E']
['A', 'B', 'C', 'F']
['A', 'B', 'E']
['A', 'B', 'E', 'C']
['A', 'B', 'E', 'C', 'D']
['A', 'B', 'E', 'C', 'F']
我认为普通的树结构对于表示您的数据没有意义，因为它是顺序的，但不一定是排序/排序的。使用尝试（前缀树或基数树）或（可能更好）有向图可能更合适。
我认为你可能让事情变得比他们需要的更复杂。 想想你代表的数据类型，就像xvatar所说的那样。
对于基本的有向图，字典是有意义的。 只需存储父项：子项列表。
nodes = [ ('A','B'),
('B','C'),
('C','D'),
('C','E'),
('B','E'),
('C','F') ]
from collections import defaultdict
d = defaultdict(list)
for node in nodes:
d[node[0]].append(node[1])
从任何根节点查找所有可访问的子节点非常简单：
def getchildren(root, graph, path=[]):
path = path + [root]
for child in graph[root]:
if child not in path: #accounts for cycles
path=getchildren(child, graph, path)
return path
呼叫时：
>>> print getchildren('A',d)
['A', 'B', 'C', 'D', 'E', 'F']
>>> print getchildren('C',d)
['C', 'D', 'E', 'F']