CODEWITHSUNDEEP
pythondepth-first-searchgraph-traversal
FallingInForward
FallingInForward

Reputation: 315

Python get all paths from graph

I'm trying to find the paths that a user could take through a website. I have represented my graph using this format:

graph = { 0 : [1, 2],
          1 : [3, 6, 0],
          2 : [4, 5, 0],
          3 : [1],
          4 : [6, 2],
          5 : [6, 2],
          6 : [1, 4, 5]}

I have implemented a depth first algorithm, but it needs a change for it to be useful. It needs to return the path and not just the nodes in the order it goes to them.

visitedList = [[]]
def depthFirst(graph, currentVertex, visited):
    visited.append(currentVertex)
    for vertex in graph[currentVertex]:
        if vertex not in visited:
            depthFirst(graph, vertex, visited)
    return visited

traversal = depthFirst(graph, 0, visitedList)
print('Nodes visited in this order:')
print(visitedList)

That function returns this:

[[], 0, 1, 3, 6, 4, 2, 5]

Whereas I want something like this:

[[0, 1, 3], [0, 1, 6], [0, 2, 4, 6], [0, 2, 5, 6]]

Upvotes: 7

Views: 13367

Answers (1)

mprostak
mprostak

Reputation: 246

When passing a list in python it does not deep copy. Using list.copy() can really help here. I'm not sure this is what you wanted but here is the code:

visitedList = [[]]

def depthFirst(graph, currentVertex, visited):
    visited.append(currentVertex)
    for vertex in graph[currentVertex]:
        if vertex not in visited:
            depthFirst(graph, vertex, visited.copy())
    visitedList.append(visited)

depthFirst(graph, 0, [])

print(visitedList)

It returns all the paths.

[[], [0, 1, 3], [0, 1, 6, 4, 2, 5], [0, 1, 6, 4, 2], [0, 1, 6, 4], [0, 1, 6, 5, 2, 4], [0, 1, 6, 5, 2], [0, 1, 6, 5], [0, 1, 6], [0, 1], [0, 2, 4, 6, 1, 3], [0, 2, 4, 6, 1], [0, 2, 4, 6, 5], [0, 2, 4, 6], [0, 2, 4], [0, 2, 5, 6, 1, 3], [0, 2, 5, 6, 1], [0, 2, 5, 6, 4], [0, 2, 5, 6], [0, 2, 5], [0, 2], [0]]

List copy worked for me in python3.

Upvotes: 7

Related Questions