4.

 
 
     
     
# 4. Write program to implement the DFS and BFS algorithm for a graph.

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        # Default dictionary to store the graph as an adjacency list
        self.graph = defaultdict(list)
    
    # Function to add an edge to the graph
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    # Depth-First Search (DFS) using recursion
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        
        # Mark the current node as visited and print it
        visited.add(start)
        print(start, end=" ")
        
        # Recur for all adjacent nodes not yet visited
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)
    
    # Breadth-First Search (BFS) using a queue
    def bfs(self, start):
        visited = set()  # Set of visited nodes
        queue = deque([start])  # Queue initialized with the starting node
        
        visited.add(start)
        
        while queue:
            # Dequeue a vertex from the queue and print it
            node = queue.popleft()
            print(node, end=" ")
            
            # Get all adjacent nodes. If a node has not been visited, mark it visited and enqueue it
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

# Example usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("DFS starting from node 2:")
g.dfs(2)
print("\nBFS starting from node 2:")
g.bfs(2)