Write a Program to Traverse a Graph using Depth First Search in Python using recursion and iteration methods.
Depth-first search in Python is a graph traversal algorithm that is used to traverse and explore all the vertices in a graph. The algorithm starts at a source node and explores as far as possible along each branch before backtracking. The algorithm uses a stack to keep track of the nodes to be visited and a set to keep track of visited nodes to avoid revisiting them.
2 Ways to Implement Depth First Search in Python
In Python DFS can be implemented using either recursion or iteration. The recursive implementation is more concise and easier to understand while iterative implementation is more efficient and can handle larger graphs without running out stack space.
Recursive implementation of Depth first search in Python:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
In this implementation the dfs() the function takes in a graph (as an adjacency list) a starting node and a set of visited nodes (which is initialized as an empty set if not provided). The function starts by adding the starting node to the set of visited nodes and printing it. It then call itself recursively on all the neighbors of the starting node that have not been visited yet.
To use the DFS algorithm to traverse a graph you would call the dfs() function with the graph and a starting node as arguments
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("DFS traversal of graph starting from node 'A':")
dfs(graph, 'A')
This would output the following:
DFS traversal of graph starting from node 'A':
A B D E F C
This show that DFS algorithm has successfully visited all nodes in the graph in a depth-first manner starting from node ‘A’.
Depth first search in Python using iteration
Implementing depth-first search (DFS) in Python using iteration (i.e, a stack-based approach)
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
stack.extend(reversed(graph[node]))
In this implementation the dfs() function takes in a graph (as an adjacency list) and a starting node. The function starts by initializing a set to store visited nodes and a stack to keep track of nodes to visit. The starting node is added to the stack.
Then the function enters a loop that continues as long as there are nodes on the stack. In each iteration of the loop, the next node to visit is popped from the stack and if it has not been visited yet it is added to the visited set and printed. Finally, the neighbors of the current node are added to the stack in reverse order so that the first neighbor to be visited is the one that was added last.
To use this DFS algorithm, you would call the dfs() function with the graph and a starting node as arguments. For example let’s say we have the following graph:
A -> B, C
B -> D, E
C -> F
D ->
E -> F
F ->
And we want to traverse the graph starting from node ‘A’. We would call the dfs() function like this:
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
dfs(graph, 'A')
This would output the following:
A
C
F
B
E
D
This shows that the DFS algorithm has successfully visited all nodes in the graph in a depth-first manner starting from node ‘A’.
4 Ways to Implement Linear Search in Python – Linear Search in Python
3 Ways to Implement Binary Search in Python