<分区>
我有一个将字符串映射到字符串集的字典。作为玩具示例:
d = {'a': {'b', 'c', 'd'},
'b': {'c', 'x'},
'c': {'d', 'z'}}
这个想法是每个字符串映射到一组字符串，每个字符串又映射到它自己的一组字符串，等等。
我想要一个函数f(start, d, pathLength)，它将接受起始字符串、字典和路径长度，并返回它可以找到的字典中的第一条路径，长度路径长度。一个不变量是，如果路径的最后一个元素等于路径中已存在的值，则路径无法继续。
我编写了递归构建整个树的代码，但这需要大量计算，而且似乎没有必要。为了减少所需的时间，我让它以一定的概率构建了 take 节点。我想保留随机特性，这样每次运行函数时，我们都会得到不同的路径作为返回。我想有一种方法可以使用堆栈和循环而不用递归来做到这一点，但我没有成功。
最佳答案
这是图论中的经典算法；请搜索如何通过有向图找到路径。 Dijktra's algorithm是最短路径的标准。但是，如果您希望恰好给定的路径长度，则需要稍微改变它。
一般来说，您需要保留一个列表，记录您到达每个节点需要多少步:保留所有可能性，而不仅仅是最短的。大纲是:
**search list** <- start node
**found list** <- []
While the **search list** is not empty:
Pop the next node (call it **here**) from the search list.
If the current path length < desired path length:
For each node **next** reachable from **here**:
If **next** is already on the **found list**,
Add the present path to its entry on the found list.
Follow the downstream paths from **here** and update their paths with the new path to **here** (alternate solutions).
Else
Add **next** and the present path to the **found list**.
Add **next** to the search list.
关于python - 通过字典获取路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37401701/