Depth-first search (DFS) – Python implementation using stack

def dfs(graph,start):
    path = []
    stack = [start]
    while stack != []:
        v = stack.pop()
        if v not in path:
        for w in reversed(graph[v]):
            if w not in path:
    return path
For recursive solution visit the following link: 
You might also find interesting implementation of other algorithms:

Tags: , ,

One response to “Depth-first search (DFS) – Python implementation using stack”

  1. Hans says :

    “if v not in path:”
    this likely ruins the O(vertices + nodes) into something a lot bigger

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: