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:
            path.append(v)
        for w in reversed(graph[v]):
            if w not in path:
                stack.append(w)
    return path
 
For recursive solution visit the following link: 
 
You might also find interesting implementation of other algorithms:
Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: