Graph Traversal Algorithms – Complete Notes

With C Code, Diagrams, Applications & Complexity

---

1. What is Graph Traversal?

Graph Traversal = Visiting all vertices (and edges) of a graph in a systematic way.

Two Main Techniques

Algorithm	Strategy	Use Case
BFS (Breadth-First Search)	Level by level	Shortest path (unweighted)
DFS (Depth-First Search)	Deep dive first	Path finding, cycles, components

---

2. Graph Representation

A. Adjacency List (Preferred)

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* head[100];
} Graph;

B. Adjacency Matrix

int adjMatrix[100][100];

List → Sparse graphs
Matrix → Dense graphs

---

3. BREADTH-FIRST SEARCH (BFS)

Explores level by level using a queue.

Analogy

Ripple in a pond — nearest nodes first.

---

Algorithm

1. Start at source s
2. Enqueue s, mark visited
3. While queue not empty:
      u = dequeue()
      Process u
      For each neighbor v of u:
          if v not visited:
              enqueue v
              mark visited
              parent[v] = u

---

C Code (Adjacency List)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* head[MAX];
    int visited[MAX];
} Graph;

typedef struct {
    int arr[MAX];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = -1;
}

void enqueue(Queue* q, int x) {
    if (q->rear == MAX - 1) return;
    if (q->front == -1) q->front = 0;
    q->arr[++q->rear] = x;
}

int dequeue(Queue* q) {
    if (q->front == -1) return -1;
    int x = q->arr[q->front];
    if (q->front == q->rear) q->front = q->rear = -1;
    else q->front++;
    return x;
}

int isEmpty(Queue* q) {
    return q->front == -1;
}

void addEdge(Graph* g, int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = g->head[u];
    g->head[u] = newNode;

    // For undirected
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = u;
    newNode->next = g->head[v];
    g->head[v] = newNode;
}

void BFS(Graph* g, int start) {
    Queue q;
    initQueue(&q);

    g->visited[start] = 1;
    enqueue(&q, start);

    printf("BFS Traversal: ");

    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        printf("%d ", u);

        Node* temp = g->head[u];
        while (temp) {
            int v = temp->vertex;
            if (!g->visited[v]) {
                g->visited[v] = 1;
                enqueue(&q, v);
            }
            temp = temp->next;
        }
    }
    printf("\n");
}

---

BFS Example

    0
   / \
  1   2
 /   / \
3   4   5

BFS from 0: 0 → 1 → 2 → 3 → 4 → 5

---

Level Order (BFS)

void printLevel(Graph* g, int start) {
    Queue q;
    initQueue(&q);
    int level = 0;

    g->visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        int levelSize = q.rear - q.front + 1;
        printf("Level %d: ", level++);
        for (int i = 0; i < levelSize; i++) {
            int u = dequeue(&q);
            printf("%d ", u);
            Node* temp = g->head[u];
            while (temp) {
                int v = temp->vertex;
                if (!g->visited[v]) {
                    g->visited[v] = 1;
                    enqueue(&q, v);
                }
                temp = temp->next;
            }
        }
        printf("\n");
    }
}

---

Complexity

Metric	Time
Time	O(V + E)
Space	O(V) (queue + visited)

---

4. DEPTH-FIRST SEARCH (DFS)

Explores as far as possible along each branch.

Analogy

Maze exploration — go deep, backtrack.

---

Algorithm (Recursive)

DFS(u):
    mark u as visited
    process u
    for each neighbor v of u:
        if v not visited:
            DFS(v)

---

C Code (Recursive DFS)

void DFSUtil(Graph* g, int u) {
    g->visited[u] = 1;
    printf("%d ", u);

    Node* temp = g->head[u];
    while (temp) {
        int v = temp->vertex;
        if (!g->visited[v])
            DFSUtil(g, v);
        temp = temp->next;
    }
}

void DFS(Graph* g, int start) {
    for (int i = 0; i < MAX; i++) g->visited[i] = 0;
    printf("DFS Traversal: ");
    DFSUtil(g, start);
    printf("\n");
}

---

Iterative DFS (Using Stack)

void DFSIterative(Graph* g, int start) {
    int stack[MAX], top = -1;
    g->visited[start] = 1;
    stack[++top] = start;

    printf("DFS (Iterative): ");
    while (top >= 0) {
        int u = stack[top--];
        printf("%d ", u);

        Node* temp = g->head[u];
        while (temp) {
            int v = temp->vertex;
            if (!g->visited[v]) {
                g->visited[v] = 1;
                stack[++top] = v;
            }
            temp = temp->next;
        }
    }
    printf("\n");
}

---

DFS Example

    0
   / \
  1   2
 /   / \
3   4   5

DFS from 0: 0 → 1 → 3 → 2 → 4 → 5 (or other valid order)

---

Complexity

Metric	Time
Time	O(V + E)
Space	O(V) (recursion stack)

---

5. Applications

Algorithm	Application
BFS	Shortest path (unweighted), Level order, Connected components, Bipartite check
DFS	Cycle detection, Topological sort, Strongly connected components, Path existence

---

6. BFS vs DFS Comparison

Feature	BFS	DFS
Data Structure	Queue	Stack (or recursion)
Order	Level-wise	Depth-wise
Shortest Path	Yes (unweighted)	No
Memory	O(V)	O(V)
Cycle Detection	Yes	Yes
Best For	Nearest node	All paths

---

7. Key Problems Solved

A. Shortest Path (Unweighted Graph) – BFS

int parent[MAX];
void shortestPath(Graph* g, int src, int dest) {
    Queue q;
    initQueue(&q);
    for(int i=0; i<MAX; i++) {
        g->visited[i] = 0;
        parent[i] = -1;
    }

    g->visited[src] = 1;
    enqueue(&q, src);

    while(!isEmpty(&q)) {
        int u = dequeue(&q);
        if(u == dest) break;

        Node* temp = g->head[u];
        while(temp) {
            int v = temp->vertex;
            if(!g->visited[v]) {
                g->visited[v] = 1;
                parent[v] = u;
                enqueue(&q, v);
            }
            temp = temp->next;
        }
    }

    // Print path
    if(parent[dest] == -1 && src != dest) {
        printf("No path!\n");
        return;
    }
    printf("Path: ");
    int x = dest;
    while(x != -1) {
        printf("%d ", x);
        x = parent[x];
    }
    printf("\n");
}

---

B. Cycle Detection

DFS (Undirected)

int hasCycleDFS(Graph* g, int u, int parent) {
    g->visited[u] = 1;
    Node* temp = g->head[u];
    while(temp) {
        int v = temp->vertex;
        if(!g->visited[v]) {
            if(hasCycleDFS(g, v, u)) return 1;
        }
        else if(v != parent) return 1;
        temp = temp->next;
    }
    return 0;
}

BFS (Directed)

Use coloring: WHITE, GRAY, BLACK → GRAY → GRAY = cycle

---

C. Connected Components

void connectedComponents(Graph* g, int V) {
    int component = 0;
    for(int i = 0; i < V; i++) g->visited[i] = 0;

    for(int i = 0; i < V; i++) {
        if(!g->visited[i]) {
            component++;
            printf("Component %d: ", component);
            DFSUtil(g, i);
            printf("\n");
        }
    }
}

---

8. Visual: BFS vs DFS

        0
      / | \
     1  2  3
    /     /
   4     5

Step	BFS Queue	DFS Stack
1	[0]	[0]
2	[1,2,3]	[1]
3	[2,3,4]	[4]
4	[3,4]	[ ]

---

9. Summary Table

Feature	BFS	DFS
Order	Level	Depth
Structure	Queue	Stack
Shortest Path	Yes	No
Memory	More (wide)	Less (deep)
Cycle	Yes	Yes
Components	Yes	Yes

---

10. Practice Problems

1. Shortest path in maze (0-1 grid)
2. Word ladder (BFS)
3. Detect cycle in directed graph
4. Topological sort (DFS)
5. Number of islands (DFS/BFS)
6. Snake and ladder (BFS)

---

11. Key Takeaways

Insight
BFS = Queue → Level Order → Shortest Path
DFS = Stack/Recursion → Deep First → Cycle Detection
Both O(V+E)
Use visited[] to avoid revisits
Parent array for path reconstruction
BFS for nearest, DFS for existence

---

End of Notes