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

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

5. Important Applications Summary Table

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)

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! 🚀