使用列表列表保存图形中的每个路径 [英] Use list of lists to save every path in a graph

问题描述

我必须实现dfs算法以保存来自起始节点的所有路径。因此，例如，我有以下图形：

I have to implement dfs algorithm to save all paths from a starting node. So for example i have the following graph:

我有一个列表 path = [] 来保存从节点1开始的所有路径。因此，我的列表将只有起始节点1： 1 ，然后我将检查1的邻居（即节点2），列表将为： [1,2] 。
现在，我检查2的邻居，分别是3和4。现在，我认为列表类似于 [[1,2,3]，[1,2,4]] ，最后的最终列表将是 [[1,2,3]，[1,2,4,5]，[1,2,4,6] ] 。我该如何实施？我有每个节点的邻居，但我不知道如何保存每个路径，因为我是python的新手。
这是我的代码：

i have a list path = [] to save all the paths starting from node 1. So my list will have only the starting node 1: 1, then i will check for neighbors of 1 which is the node 2 and the list will be: [1,2]. Now i check the neighbors of 2 which are 3 and 4. The list now i think that it will be like [[1,2,3], [1,2,4]] and in the end the final list will be [[1,2,3], [1,2,4,5], [1,2,4,6]]. How can i implement this? I have the neighbors of every node but i dont know how to save every path because im new to python. Here is my code:

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的邻居。

I used networkx to create the Graph. So G is my graph, s is the starting node and with G.neighbors(v) i can find the neighbors of node v.

推荐答案

import copy

def dfs(tree, u, all_paths, one_path=[]):

    one_path = copy.deepcopy(one_path)
    one_path.append(u)

    if u not in tree:
        all_paths.append(one_path)
        return

    for v in tree[u]:
        dfs(tree, v, all_paths, one_path)

    return



tree = {1:[2], 2:[3, 4], 4:[5, 6]}
starting_node = 1
all_paths = []

dfs(tree, starting_node, all_paths)

print(all_paths)

这会打印[[1、2、3]，[1、2、4、5]，[1、2、4、6]]

This prints [[1, 2, 3], [1, 2, 4, 5], [1, 2, 4, 6]]

由于列表在python中是可变的，所以关键是在每个节点递归中创建路径的深层副本。

Since lists are mutable in python, the key is creating a deep copy of the path in each node recursion.

这篇关于使用列表列表保存图形中的每个路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！