回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我已经为此挣扎了一段时间了。给定一组节点:</p>
<pre><code>nodes = { ('A','B'),
('B','C'),
('C','D'),
('C','E'),
('B','E'),
('C','F') }
</code></pre>
<p>实现以下目标的最佳方法是什么:</p>
^{pr2}$
<p>我可以看到:</p>
<pre><code>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...
</code></pre>
<p>我这么做的原因,纯粹是因为我想知道如何去做。在</p>
<p>我知道bfs会找到最快的路径(我想我可能会在get children函数中使用类似的方法)</p>
<p>但我不知道循环/递归运行该图的最佳方法。我应该使用字典来处理key/vals还是list。或设置。。。在</p>
<pre><code>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
</code></pre>
<p>我在这里使用*z,因为元组实际上会包含一个float,但是现在我试图保持简单。在</p>
<pre><code>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'}
</code></pre>
<p>getchildren函数用于查找节点根的所有可能的端点:</p>
<pre><code>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))
</code></pre>
<p>在这种情况下,A:</p>
<pre><code>print(getchildren('A', make_graph(nodes)))
# ('A', {'C', 'B', 'E', 'D', 'F'})
</code></pre>