Graph Traversal Algorithms – Complete Notes

With C Code, Diagrams, Applications & Complexity

Graph Traversal Algorithms – Complete Notes

With C Code, Diagrams, Applications & Complexity

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

Last updated: Nov 12, 2025

Graph Traversal Algorithms – Complete Notes

With C Code, Diagrams, Applications & Complexity

Graph Traversal Algorithms – Complete Notes

With C Code, Diagrams, Applications & Complexity

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

Last updated: Nov 12, 2025