DFS and BFS

Exploring Depth First Search (DFS)

Introduction

Depth-First Search (DFS) is a fundamental graph traversal algorithm used in many computer science applications. It explores as far as possible along each branch before backtracking, making it an excellent choice for problems that require exhaustive search of all possible paths or configurations

How DFS Works

DFS starts at a chosen node (root in the case of trees) and explores each branch as deeply as possible before moving on to the next branch. This is typically implemented using recursion or a stack.

Pseudocode for DFS :

Recursive Implementation :

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
        visited.add(start)
        print(start)  # Process the node
        for next in graph[start] - visited:
            dfs_recursive(graph, next, visited)
        return visited

Application of DFS :

Path Finding: Finding paths from a source to a destination in a maze.

Topological Sorting: Ordering tasks or jobs based on dependencies.

Cycle Detection: Detecting cycles in a graph.

Solving Puzzles: Such as the N-Queens problem, Sudoku, etc.

Complexity :

Time Complexity : O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity : O(V), due to the stack/recursion depth.

Exploring Best First Search (BFS)

Introduction

Breadth-First Search (BFS) is another fundamental graph traversal algorithm widely used in computer science. Unlike DFS, BFS explores all neighbors at the present depth prior to moving on to nodes at the next depth level.

How BFS Works

BFS starts at the chosen node (root in trees) and explores all its neighbors first, then moves on to the neighbors of those neighbors, and so on. This approach ensures that the algorithm visits nodes in layers or levels.

Pseudocode for BFS :

Iterative Implementation :

from collections import deque
    def bfs(graph, start):
        queue = set(), deque([start])
        while queue:
                vertex = queue.popleft()
                if vertex not in visited:
                        visited.add(vertex)
                        print(vertex)  # Process the node
                        queue.extend(graph[vertex] - visited)
                return visited

Application of BFS :

Shortest Path: Finding the shortest path in an unweighted graph.

Level Order Traversal: Traversing each level of a tree.

Web Crawlers: Indexing web pages linked to each other.

Social Networks: Finding all friends at a given distance in social networks.

Complexity :

Time Complexity : O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity : O(V), due to the queue storing all vertices in the worst case..