Depth-first search (DFS) code in python

8
votes

Can you please let me know what is incorrect in below DFS code. It's giving correct result AFAIK, but I don't know when it will fail.

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

visited = []

def dfs(graph,node):
    global visited
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n)

    dfs(graph1,'A')
    print(visited)

Output:

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
9
pythondepth-first-search
First of all: don't use globals avoid them as much as possible!! - Willem Van Onsem
DFS is a search algorithm, but there is no target defined you are looking for... - Willem Van Onsem
Thanks for the response.. visited = [] def dfs(graph,node,visited): if node not in visited: visited.append(node) for n in graph[node]: dfs(graph,n,visited) dfs(graph1,'A',visited) print(visited) - Vicky
I'm also not convinced that the output you show is generated by the data you show - I don't see where S, H and G come from? (But I could possibly be wrong here) - DavidW
Hi Willem, if you checkout the link eddmann.com/posts/… there a sample code for the DFS is given but If I change the graph as given in youtube tutorial "youtu.be/iaBEKo5sM7w" I am not getting the result as mentioned. So I thought of writing my own version based on the tutorial. - Vicky

9 Answers

17
votes

I think you have an indentation problem there. Assuming your code looks like this:

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

visited = []

def dfs(graph,node):
    global visited
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n)

dfs(graph1,'A')
print(visited)

I would say a couple of things:

  • Avoid globals if you can
  • Instead of a list for visited, use a set

plus:

  • This will not work for forests but I assume you already know that
  • It will fail if you reference a node that does not exist.

Updated code:

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

visited = dfs(graph1,'A', [])
print(visited)
9
votes

Without recursion:

def dfs(graph, node):
    visited = [node]
    stack = [node]
    while stack:
        node = stack[-1]
        if node not in visited:
            visited.extend(node)
        remove_from_stack = True
        for next in graph[node]:
            if next not in visited:
                stack.extend(next)
                remove_from_stack = False
                break
        if remove_from_stack:
            stack.pop()
    return visited

print (dfs(graph1, 'A'))

Output:

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
3
votes

Here's an iterative (non-recursive) implementation of a DFS:

def dfs_iterative(graph, start_vertex):
    visited = set()
    traversal = []
    stack = [start_vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            traversal.append(vertex)
            stack.extend(reversed(graph[vertex]))   # add vertex in the same order as visited
    return traversal

test_graph = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

print(dfs_iterative(test_graph, 'A'))

Output:

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']

1
votes
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self,u,v):
        self.graph[u].append(v)

    def DFS(self,v,vertex):
        visited = [False]*vertex
        print(self. graph)
        # print(len(self.graph),"+++")
        self.DFSUtil(v,visited)

    def DFSUtil(self,v,visited):
        visited[v]=True
        print(v)

        for i in self.graph[v]:
            if visited[i] == False:
                # print(visited)
                self.DFSUtil(i,visited)
g= Graph()

vertex=7

g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(0,6)
g.addEdge(0,5)
g.addEdge(5,3)
g.addEdge(5,4)
g.addEdge(4,3)
g.addEdge(6,4)

g.DFS(0,vertex)

This is the modification for the above code because that doesn't work with in all cases.
We have to specify the number of vectors and then give edges manually.

0
votes
 graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

   def dfs(s,d):
    def dfs_helper(s,d):
        if s == d:
            return True
        if  s in visited :
            return False
        visited.add(s)
        for c in graph[s]:
            dfs_helper(c,d)
        return False
    visited = set()
    return dfs_helper(s,d) 
dfs('A','E') ---- True
dfs('A','M') ---- False
0
votes

DFS implementation in Python 

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFSUtil(self, v, visited):
        visited[v]=True
        print(v)

        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    def DFS(self):
        V = len(self.graph)

        visited = [False]*(V)

        for i in range(V):
            if visited[i] == False:
                self.DFSUtil(i, visited)

# Driver code
# Create a graph given in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is Depth First Traversal")
g.DFS()

Source :: this

0
votes

Here is a more versatile algorithm, the one asked in the question works only for undirected graphs. But this hopefully works for both them. Check it out

graph1= {
'A' : ['B','S'],
'B' : [],
'C' : ['E','S'],
'D' : ['C'],
'E' : ['H'],
'F' : ['C'],
'G' : ['F','S'],
'H' : ['G'],
'S' : []
}
visited = []

def dfs_visit(graph, s):
    global visited
    for v in graph[s]:
        if v not in visited:
            visited.append(v)
            dfs_visit(graph, v)


def dfs(graph):
    global visited
    for v in [*graph]:
        if v not in visited:
            visited.append(v)
            dfs_visit(graph,v)

dfs(graph1)
print(visited)
0
votes
    def DFS(graph,pointer,visit):
          visit.add(pointer)
          print(pointer,end=' ')

    for travel in graph[pointer]-visit:
        if travel not in visit:
            DFS(graph,travel,visit)


graph={'0':set(['1','2','3']),'1':set(['0','2']),'2':set(['0','1','4']),'3':set(['0']),'4':set(['2'])}
visit=set()
print("DFS for graph: ",graph)
DFS(graph,'0',visit)

Output

DFS for graph:  {'0': {'1', '3', '2'}, '1': {'0', '2'}, '2': {'1', '0', '4'}, '3': {'0'}, '4': {'2'}}
0 1 2 4 3
0
votes

A recursive implementation:

def dfs(G, u, visited=[]):
    """Recursion version for depth-first search (DFS).
    Args:
        G: a graph
        u: start
        visited: a list containing all visited nodes in G
    Return:
        visited
    """
    visited.append(u)
    for v in G[u]:
        if v not in visited:
            dfs(G, v, visited)
    return visited

An iterative implementation using a stack:

def dfs_iterative(G, u, visited=[]):
    stack = [u, ] #initialize
    while stack:
        u = stack.pop()
        if u not in visited:
            visited.append(u)
            stack.extend(reversed(G[u])) #reversed() is used as the same traversal as recursive DFS
    return visited