Recursive Depth-first search algorithm

Question

I am trying to write a recursive depth-first search algorithm that takes an adjacency list representing a graph and prints the visit order of the vertices.

My input is a graph stored as an adjacency list:

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

From there, I have written 2 functions, a main and a secondary function, that make up the program.

import sys

def main():
count = 0
graphAL2v = {}

for key, value in graphAL2.items():
    graphAL2v[key] = 0

print graphAL2v

for key in graphAL2v: 
    if key == 0: 
        dfs(key, count, graphAL2v)
def dfs(v, count, graph):
    count = count + 1 
    graph[v] = count
    for key in graph: 
        if key == 0:
            dfs(key, count, graph)
if __name__ == "__main__":
    sys.exit(main())

Right now my if I run it, the output is:

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
{0: 1, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}

and the first value paired with key 0 keeps incrementing until a

RuntimeError: maximum recursion depth exceeded

is reached. The for loop should be going through the rest of the key-pair values and changing the values to the order that the vertex was visited but I'm not sure why it isn't doing so.

Any thoughts?

Since the first key in graph is 0, you always send off your recursive call dfs(key, count, graph) in the first iteration of the for loop. Although I'm not sure why you're checking key == 0, or how your algorithm is supposed to work. — Blorgbeard
– Blorgbeard, Commented Sep 16, 2015 at 4:58
@Blorgbeard Basically i'm taking the input vertices and marking them all with 0's to show that they haven't been visited yet. If a vertex hasn't been visited, it gets passed into the second function that then alters the 0 to the number corresponding to when the vertex was visited. Since vertex 0 is visited first, its value gets changed from 0 to 1, and then the function should move on to the next vertex, change its value from 0 to 2, and so on and so forth — superfluousAM
– superfluousAM, Commented Sep 16, 2015 at 5:18

Anand S Kumar · Accepted Answer · 2015-09-16 05:49:51Z

4

The issue is in your dfs() function , you are not checking whether the node has already been visited or not , you are checking whether the node is 0 or not in the if condition - if key == 0: , so it keeps recursing for 0th node, even though it has already been visited.

And due to this indefinite recursion for 0th node, when the maximum recursion limit is reached, it pops out with the error - RuntimeError: maximum recursion depth exceeded .

You should check the value for key from graph` , not the graph itself. And you are not using the adjacency list anywhere either. You should loop based on the adjacency list, not the visited dictionary.

Example -

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

def main():
    count = 0
    graphAL2v = {}

    for key, value in graphAL2.items():
         graphAL2v[key] = 0

    print(graphAL2v)

    for key in graphAL2v: 
        if graphAL2v[key] == 0: 
            dfs(key, count, graphAL2, graphAL2v)

    print(graphAL2v)


def dfs(v, count, graphal, graphvisited):
    count = count + 1
    print("Visiting ",v)
    graphvisited[v] = count
    for elem in graphal[v]:
        if not graphvisited[elem]:
            dfs(elem, count, graphal, graphvisited)

main()

Demo -

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
Visiting  0
Visiting  1
Visiting  3
Visiting  5
Visiting  2
Visiting  4
{0: 1, 1: 2, 2: 5, 3: 3, 4: 6, 5: 4}

answered Sep 16, 2015 at 5:49

Anand S Kumar

91.4k18 gold badges196 silver badges179 bronze badges

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

3 Comments

superfluousAM Over a year ago

Awesome, thank you very much! I understand where the error was now and can't believe I didn't think that would be what was causing it. Quick question, now that my code reflects the changes to fix the problem, I'm now getting a "TypeError: 'int' object is not iterable error on the for elem in graphal[v]: line, any suggestions there?

Anand S Kumar Over a year ago

what are you sending in graphal? Can you update the updated code in question?

superfluousAM Over a year ago

The firs time I called dfs() in main, I had swapped the last 2 parameters. I switched those and now the error is gone and results are produced. Thank you again! (Another side note, for breadth-first search it would essentially be the same skeleton, but the second function would need to be changed to accommodate how breadth-first search works right?)

Collectives™ on Stack Overflow

Recursive Depth-first search algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related