trying to find all the path in a graph using DFS recursive in Python

Question

I have found a solution that was posted some times ago and I have tried to apply it to my exercise but it doesn't work. I have a class graph that has nodes and edges and a method childrenOf that gives all the children of a node. All this works fine. This is my code for the DFS search and I want to find all the paths:

def myDFS(graph,start,end,path=[]):
path=path+[start]
if start==end:
    return path
paths=[]
for node in graph.childrenOf(start):
    if node not in path:
        paths.extend(myDFS(graph,node,end,path))            
return paths

I only got empty lists. WHere do I need to look at? When I was doing path=myDFS... in the loop I had at least the last path. I tried path+=myDFS without success. The graph was created with success so it doesn't come from it. Thanks

winxton · Accepted Answer · 2013-05-24 19:05:50Z

6

Since you only want to get all paths from start to end, the path is appended to your total path list when it reaches the end. The total list of paths is not returned but rather populated:

paths = []

def myDFS(graph,start,end,path=[]): 
    path=path+[start] 
    if start==end:
        paths.append(path) 
    for node in graph.childrenOf(start):
        if node not in path:
            myDFS(graph,node,end,path)

edited May 24, 2013 at 19:05

answered May 24, 2013 at 18:55

winxton

6637 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Andrew M. · Accepted Answer · 2018-10-22 13:53:05Z

i've flattened JSON of nested dicts (depth was four)

{'output':
    'lev1_key1': 'v11',
    'lev1_key2': {
       {'lev2_key1': 'v21',
        'lev2_key2': 'v22',
       }
 }

with recursive call of

paths = []
_PATH_SEPARATOR = '/'
def flatten(treeroot, path=''):
  path=path
  if isinstance(treeroot, dict):
    for k in treeroot.keys():
        s_path = path + _PATH_SEPARATOR + str(k)
        flatten(treeroot[k], path=s_path)
  elif isinstance(treeroot, str):
     path = path + _PATH_SEPARATOR + treeroot
     paths.append(path)
  elif isinstance(treeroot, list):
    # if node has more than one child 
    for k in treeroot.keys():
        s_path = path + _PATH_SEPARATOR + str(k)
        flatten(k, path=s_path)

result is

{
 'output/lev1_key1': 'v11',
 'output/lev1_key2/lev2_key1': 'v21',
 'output/lev1_key2/lev2_key2': 'v22',
}

Collectives™ on Stack Overflow

trying to find all the path in a graph using DFS recursive in Python

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related