Use List Of Lists To Save Every Path In A Graph

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 no

Solution 1:

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

defdfs(tree, start, target):
   if start == target:
      returnTrueif start notin tree:
      returnFalsefor child in tree[start]:
      current = dfs(tree, child, target)
      if current:
        returnTrue

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:

TrueFalse

A shorter way:

defdfs(tree, start, target):
   try:
     return reduce(lambda x, y:x+y, [Trueif i == target else dfs(tree, i, target) for i in tree[start]])
   except:
     returnFalseprint(bool(dfs({1:[2], 2:[3, 4], 4:[5, 6]}, 1, 5)))

Output:

true

Solution 2:

def bfs(G, s):
    paths    = [[s]]
    toFollow = [s]
    whilelen(toFollow) > 0:
        current_node = toFollow.pop(0)
        current_path = [pathforpathin paths ifpath[-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.

Solution 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.

Solution 4:

importcopy

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