Use list of lists to save every path in a graph

Question

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

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)

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.

Answer 1

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)

This should probably do it. I did not test it. Instead of a Queue class, I just used Python's native list functionality. I begin with my list of paths being a list containing a single path with a single node. Additionally, I have a list of paths I need to follow called toFollow, like your Queue. While there is still a node to follow, I pop it off the Queue (from the beginning). Then I find its corresponding list in paths. After that, I make new lists for each of the neighbors. If this was nonzero, I delete the current_path since it was incomplete.

Answer 2

A very simple depth first search can be as follows: given the starting (head) node, access the children of the node, and for each child, find its children, and repeat the iteration and thus the process itself (recursion):

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))

Output:

True
False

A shorter way:

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)))

Output:

true

Answer 3

The way I do it is by keeping track of the path used to reach each node. See my answer here:

keep track of the path through which the target has been reached. A simple way to do it, is to push into the Queue the whole path used to reach a node, rather than the node itself.

I can't help you with python, but I hope the Java example is clear enough.

Answer 4

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)

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

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