Implement DFS and BFS Algorithms
Here are implementations of Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms in Python:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs_util(self, node, visited):
visited.add(node)
print(node, end=" ")
for neighbor in self.graph[node]:
if neighbor not in visited:
self.dfs_util(neighbor, visited)
def dfs(self, start_node):
visited = set()
self.dfs_util(start_node, visited)
def bfs(self, start_node):
visited = set()
queue = deque([start_node])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in self.graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# Example usage:
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)
print("Depth-First Search (DFS):")
graph.dfs(2) # Output: 2 0 1 3
print("\nBreadth-First Search (BFS):")
graph.bfs(2) # Output: 2 0 3 1
In this implementation:
Graph class with methods to add edges (add_edge), perform DFS (dfs), and perform BFS (bfs).dfs_util) and a set to keep track of visited nodes.deque from collections) and a set to keep track of visited nodes.2 in this example).
You can modify the add_edge method to add edges between nodes in your graph. Then, you can use the dfs and bfs methods to perform DFS and BFS traversal, respectively, starting from any node in the graph.
Thank you,