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