使用列表列表的每一个路径保存在图(Use list of lists to save every p

我要实现DFS算法来保存从一个起始节点的所有路径。因此，例如，我有以下图表：

我有一个列表path = []保存所有的路径从节点1开始所以我的列表将只具有起始节点1： 1 ，然后我将检查的1邻居是节点2和列表将是： [1,2] 。现在我检查哪些是3和4的名单，现在我认为它会像2邻居[[1,2,3], [1,2,4]]并在结束时的最终名单将在[[1,2,3], [1,2,4,5], [1,2,4,6]] 。我怎样才能实现呢？我有每个节点的邻居，但我不知道该怎么每次保存路径，因为进出口新的蟒蛇。这里是我的代码：

def bfs(G, s):
    paths = []
    q = queue.Queue()
    visited = []
    q.put(s)
    visited.append(s)
    while not q.empty():
        v = q.get()
        for node in G.neighbors(v):
            #here i think that i must save the paths
            if node not in visited:
                q.put(node)
                visited.append(node)

我用networkx创建图表。所以G是我的曲线，S是起始节点和G.neighbors(v)我能找到的节点V的邻居。

Answer 1:

一个非常简单的深度优先搜索可以如下：给定的起始（头）节点，接入节点的孩子们，并为每个孩子，找它的孩子，并重复迭代，从而过程本身（递归）：

def dfs(tree, start, target):
   if start == target:
      return True
   if start not in tree:
      return False 
   for child in tree[start]:
      current = dfs(tree, child, target)
      if current:
        return True

result = dfs({1:[2], 2:[3, 4], 4:[5, 6]}, 1, 5)
result1 = dfs({1:[2], 2:[3, 4], 4:[5, 6]}, 1, 10)
print(bool(result))
print(bool(result1))

输出：

True
False

更短的方式：

def dfs(tree, start, target):
   try:
     return reduce(lambda x, y:x+y, [True if i == target else dfs(tree, i, target) for i in tree[start]])
   except:
     return False

print(bool(dfs({1:[2], 2:[3, 4], 4:[5, 6]}, 1, 5)))

输出：

true

Answer 2:

def bfs(G, s):
    paths    = [[s]]
    toFollow = [s]
    while len(toFollow) > 0:
        current_node = toFollow.pop(0)
        current_path = [path for path in paths if path[-1] == current_node][0]
        neighbors    = G.neighbors(current_node)
        nonzero = False
        for n in neighbors:
            nonzero = True
            toFollow.append(n)
            newPath = list(current_path)
            newPath.append(n)
            paths.append(newPath)
        if nonzero:
            paths.remove(current_path)

这也许应该这样做。我没有测试它。取而代之的是Queue类的，我只是用Python的本地列表功能。我开始与我的路径是包含具有单个节点的单一路径列表清单。另外，我有我需要遵循所谓toFollow，喜欢你的队列路径列表。虽然仍有遵循一个节点，我弹出它关闭队列（从开始）。然后我找到的路径及其相应的列表。在那之后，我为每个邻居的新名单。如果这是非零，我删除，因为的current_path它是不完整的。