给定图G，节点n和长度L，我想收集所有（非环状的）长度L的那个由正离开路径。
你有没有对如何处理这个任何想法？
到现在为止，我在我的图是一个networkx.Graph实例，但我真的不关心，如果如IGRAPH建议。
非常感谢！
Answer 1:
我只是想在兰斯Helsten的出色答卷扩大：
当它发现它在一定深度范围内的特定节点的深度限制搜索的搜索（你叫什么长度L），并停止。 如果你看看在伪代码维基链接在他的回答，你就会明白这一点：
DLS(node, goal, depth) {
if ( depth >= 0 ) {
if ( node == goal )
return node
for each child in expand(node)
DLS(child, goal, depth-1)
}
}
在你的情况，但是，当你正在寻找从一个节点长度为L的所有路径，你不会在任何地方停止。 因此，伪代码必须修改为：
DLS(node, depth) {
for each child in expand(node) {
record paths as [node, child]
DLS(child, depth-1)
}
}
你和记录来自DLS的连续巢所有单链路路径完成后，只是把他们的产品，以获得整个路径。 这些数字让你从节点开始所需要的深度的路径的数量。
Answer 2:
接近（与完全解决）这个问题的一种非常简单的方式是使用图的邻接矩阵A。 第（i，j）个的^ L型元件是节点i和长度L j的之间路径的数量。 所以，如果你总结这些所有j保持我固定在N，你从长度为L的节点N发出的所有路径。
这也算不幸中的循环路径。 这些令人高兴的是，可以从元件中发现A^L(n,n)所以只减去。
因此，最终的答案是： Σj{A^L(n,j)} - A^L(n,n)
警告：您说您是从节点1寻找长度为5的路径：此计算也将算小的循环路径内像1-2-3-2-4 ，取决于你如何5或4的长度选择看它，所以要小心这一点。
Answer 3:
使用深度有限搜索（ http://en.wikipedia.org/wiki/Depth-limited_search ，你保持一组访问节点的用于检测周期时的路径上）。 例如，您可以从您的节点建立一个树n，其中的所有节点和L的长度再修剪树。
我做了快速搜索的图形算法来做到这一点，但没有发现任何东西。 还有的图形算法（名单http://en.wikipedia.org/wiki/Category:Graph_algorithms可能有你要找的）。
Answer 4:
该解决方案可能会在效率方面得到改善，但它似乎很短，而且利用了networkx功能：
G = nx.complete_graph(4)
n = 0
L = 3
result = []
for paths in (nx.all_simple_paths(G, n, target, L) for target in G.nodes_iter()):
print(paths)
result+=paths
Answer 5:
这里是我想出了这里读书的答案层出不穷（比较幼稚）实现：
def findAllPaths(node, childrenFn, depth, _depth=0, _parents={}):
if _depth == depth - 1:
# path found with desired length, create path and stop traversing
path = []
parent = node
for i in xrange(depth):
path.insert(0, parent)
if not parent in _parents:
continue
parent = _parents[parent]
if parent in path:
return # this path is cyclic, forget
yield path
return
for nb in childrenFn(node):
_parents[nb] = node # keep track of where we came from
for p in findAllPaths(nb, childrenFn, depth, _depth + 1, _parents):
yield p
graph = {
0: [1, 2],
1: [4, 5],
2: [3, 10],
3: [8, 9],
4: [6],
5: [6],
6: [7],
7: [],
8: [],
9: [],
10: [2] # cycle
}
for p in findAllPaths(0, lambda n: graph[n], depth=4):
print(p)
# [0, 1, 4, 6]
# [0, 1, 5, 6]
# [0, 2, 3, 8]
# [0, 2, 3, 9]
文章来源: All paths of length L from node n using python
