Depth first search, non-recursive approach

Question

I have implemented DFS using the recursive approach. However, my program breaks right after it is executed.

# Non Recursive approach
def Non_Recursive_dfs(graph, source):
    path = []
    stack = []
    stack.append(source)
    
    while stack:
        s = stack.pop()
        if s not in path:
            path.append(s)

        if s in path:
            #leaf node
            continue
        for neighbour in graph[s]:
            stack.append(neighbour)
    
    return " ".join(path)

Input and output:

print(Non_Recursive_dfs(graph, "A"))
O/p: A

Can anyone explain why is this happening?

Answer 1

The first if statement guarantees that the code under the second one will always execute because it will add s to path if it is not already in it. You can simply change the second if statement to an else-if statement like so:

def Non_Recursive_dfs(graph, source):
    path = []
    stack = []
    stack.append(source)
    
    while stack:
        s = stack.pop()
        if s not in path:
            path.append(s)

        elif s in path:
            #leaf node
            continue
        for neighbour in graph[s]:
            stack.append(neighbour)
    
    return " ".join(path)

I quickly created some dummy data for graph and it seems to run fine.