Depth-first search (DFS) code in python

Question

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']

• willeM_ Van Onsem: 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...
• Vicky: 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)
• DavidW: 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)
• Vicky: 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.

Answer 1

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)

• Sudarshan: Should the updated code contain the variable visited as dict or list?
• oamandawi: @Sudarshan since it says visited.append(node) the variable visited is a list.
• MM Khan: @Juan Leni or anyone listening: In the for loop of your code, how is variable n not stuck in values between 'B' and 'A' and how come it jumps to 'S' in the third iteration?
• Gulzar: visited should be a set to reduce runtime by o(n)
• Manfred Weis: making visited a bit vector reduces checks to O(1), but one could instead store for every vertex the adjacent vertices in sets and remove visited vertices directly from them.

Answer 2

Without recursion:

def dfs(graph, node):
 visited = set((node,))
 output = [node]
 stack = [node]
 while stack:
 node = stack[-1]
 if node not in visited:
 output.append(node)
 visited.add(node)
 remove_from_stack = True
 for next_node in graph[node]:
 if next_node not in visited:
 stack.append(next_node)
 remove_from_stack = False
 break
 if remove_from_stack:
 stack.pop()
 return output
print (dfs(graph1, 'A'))

Output:

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

• Gulzar: 1. Why extend instead of append? 2. Why is visited a list and not a set?
• gaetano: append is fine. I prefer to leave visited as it is so it can keeps track of the visit order
• Gulzar: If it is a list, you lose o(n) in performance.
• Gulzar: Also note that next is a reserved word in Python
• gaetano: agree, I added a variable output to keep the right visited order

Answer 3

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

def dfs_iterative(graph, start_vertex):
 visited = set()
 traversal = []
 stack = [start_vertex]
 while len(stack) > 0:
 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']

Answer 4

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.

• Gulzar: which cases does the above code fail for?

Answer 5

 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

Answer 6

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

• monkey intern: @AssafLivne why not? Would you mind to expand a bit on that?

Answer 7

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)

Answer 8

 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 

Answer 9

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

Answer 10

very basic code ig

def dfs(arr,vertex):
 dfs=[]
 stack=[]
 stack.append(vertex)
 while len(stack)!=0:
 top=stack.pop()
 if top not in dfs:
 dfs.append(top)
 
 for i in arr[top]:
 if i in dfs:
 continue
 stack.append(top)
 stack.append(i)
 break
 
 return dfs
print(dfs(arr,'A'))