Module 97

Here are complete, clear, and exam-ready notes on Graph Search Algorithms – the most important ones asked in interviews and university exams (UG/PG).

1. Types of Graph Traversal / Search

Algorithm	Type	Order of Visiting	Uses Queue/Stack	Complete?	Optimal?	Time Complexity	Space Complexity
Breadth-First Search (BFS)	Level-order	Nearest first	Queue	Yes	Yes (unweighted)	O(V + E)	O(V)
Depth-First Search (DFS)	Deepest first	Backtracking	Stack (or recursion)	Yes	No	O(V + E)	O(V)

2. Breadth-First Search (BFS)

Idea: Explore level by level (like flood fill).

Applications:

• Shortest path in unweighted graph
• Level-order traversal
• Bipartite check
• Connected components
• Minimum moves (e.g., Knight, Puzzle 8)

Pseudocode (using Queue):

BFS(G, start)
    Let Q be a queue
    visited[start] ← true
    distance[start] ← 0
    parent[start] ← -1
    ENQUEUE(Q, start)

    while Q is not empty
        u ← DEQUEUE(Q)
        print u or process node u
        for each neighbor v of u
            if not visited[v]
                visited[v] ← true
                distance[v] ← distance[u] + 1
                parent[v] ← u
                ENQUEUE(Q, v)

Example: Graph:
0 → 1, 2
1 → 2
2 → 0, 3
3 → 3

BFS from 2 → Order: 2, 0, 3, 1
Distance: 2:0, 0:1, 3:1, 1:2

3. Depth-First Search (DFS)

Idea: Go as deep as possible before backtracking.

Applications:

• Cycle detection
• Topological sorting (DAG)
• Strongly Connected Components (Kosaraju, Tarjan)
• Finding bridges/articulation points
• Solving mazes with backtracking

Pseudocode (Recursive – Most Common):

DFS(G)
    for each vertex u in G
        visited[u] ← false
    for each vertex u in G
        if not visited[u]
            DFS-VISIT(u)

DFS-VISIT(u)
    visited[u] ← true
    print u or process node
    for each neighbor v of u
        if not visited[v]
            parent[v] ← u
            DFS-VISIT(v)

Iterative DFS (using Stack):

DFS-ITERATIVE(G, start)
    Let S be a stack
    S.push(start)
    visited[start] ← true

    while S is not empty
        u ← S.pop()
        print u or process
        for each neighbor v of u
            if not visited[v]
                visited[v] ← true
                S.push(v)

Example (Same graph as above, start from 0):
Possible DFS order: 0 → 1 → 2 → 3
Another possible: 0 → 2 → 3 → 1

4. Comparison: BFS vs DFS

Feature	BFS	DFS
Order	Level-wise	Deep first
Memory (Space)	O(V) – worse	O(V) – better (recursive)
Shortest Path (unweighted)	Yes	No
Finds all paths easily	No	Yes (with backtracking)
Cycle Detection	Yes	Yes
Topological Sort	No (needs Kahn’s)	Yes
Best for	Shortest path, closeness	Reachability, cycles, paths

5. Important Applications Summary Table

Problem	Best Algorithm	Why?
Shortest path (unweighted)	BFS	Guarantees minimum steps
Shortest path (weighted, non-neg)	Dijkstra	Greedy + priority queue
Shortest path (any weights)	Bellman-Ford	Handles negative weights
All-pairs shortest path	Floyd-Warshall	DP, O(V³)
Detect cycle in undirected graph	DFS or BFS	Back edge or visited parent
Detect cycle in directed graph	DFS (white-gray-black)	Back edge to gray node
Topological Sort	DFS or Kahn’s (BFS)	Linear ordering of DAG
Strongly Connected Components	Kosaraju / Tarjan	Two DFS passes
Bipartite Graph Check	BFS (coloring)	2-coloring possible?

6. Bonus: Cycle Detection Rules

Undirected Graph:

• If you visit a node that is already visited and not parent → Cycle

Directed Graph (DFS colors):

• White = not visited
• Gray = visiting (in current path)
• Black = finished
  → If you find back edge to Gray node → Cycle

7. Time & Space Complexity (for all graph algorithms)

Algorithm	Time Complexity	Space Complexity	Remarks
BFS	O(V + E)	O(V)	Queue + visited
DFS (recursive)	O(V + E)	O(V)	Recursion stack + visited
Dijkstra	O((V+E) log V)	O(V)	With binary heap
Bellman-Ford	O(VE)	O(V)	Detects negative cycles
Floyd-Warshall	O(V³)	O(V²)	All pairs shortest path
Topological Sort	O(V + E)	O(V)	DFS or Kahn’s algorithm

Now you're fully prepared for any question on Graph Search Algorithms – whether it's theory, pseudocode, example tracing, or comparison!
Good luck with your exams and interviews! 🚀