Graph Traversals; Shortest Path Algorithms; Minimum Spanning Tree

Graph Traversals

17.1 BFS — Breadth-First Search

Visits vertices level by level — explores all neighbors before going deeper.

Uses a QUEUE.

Graph:
  0 --- 1 --- 4
  |     |
  2 --- 3

BFS from 0: 0, 1, 2, 4, 3
(Visit 0's neighbors first, then their neighbors, etc.)

void bfs(int start, int n) {
    int visited[n];
    int queue[n];
    int front = 0, rear = -1;

    for (int i = 0; i < n; i++) visited[i] = 0;

    visited[start] = 1;
    queue[++rear] = start;

    while (front <= rear) {
        int vertex = queue[front++];
        printf("%d ", vertex);

        // Visit all unvisited neighbors
        node_t *curr = adj[vertex];
        while (curr != NULL) {
            if (!visited[curr->vertex]) {
                visited[curr->vertex] = 1;
                queue[++rear] = curr->vertex;
            }
            curr = curr->next;
        }
    }
}

Applications:

• Shortest path in unweighted graph
• Level-order tree traversal
• Web crawling
• Social network friend suggestions ("People you may know")

Complexity: O(V + E)

17.2 DFS — Depth-First Search

Explores as deep as possible before backtracking.

Uses a STACK (or recursion which uses call stack).

Graph:
  0 --- 1 --- 4
  |     |
  2 --- 3

DFS from 0: 0, 1, 4, 3, 2
(Go as deep as possible first)

int visited[MAX_V] = {0};

void dfs(int vertex) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    node_t *curr = adj[vertex];
    while (curr != NULL) {
        if (!visited[curr->vertex]) {
            dfs(curr->vertex);  // recursive DFS
        }
        curr = curr->next;
    }
}

Applications:

• Topological sorting
• Detecting cycles in a graph
• Finding connected components
• Solving mazes
• Path finding

Complexity: O(V + E)

BFS vs DFS Comparison

Shortest Path Algorithms

18.1 Dijkstra's Algorithm

For weighted graphs with non-negative weights — finds shortest path from one source to all vertices.

Uses a Min Priority Queue (or simple array).

Algorithm:
1. Initialize dist[src] = 0; all others = INFINITY
2. Add src to min-priority queue
3. While queue not empty:
   a. Extract vertex u with minimum distance
   b. For each neighbor v of u:
      If dist[u] + weight(u,v) < dist[v]:
         dist[v] = dist[u] + weight(u,v)
         Add/update v in priority queue
4. dist[] contains shortest distances from src

Complexity: O((V + E) log V) with binary heap

Cannot handle negative weights — use Bellman-Ford for negative edges.

18.2 Floyd-Warshall Algorithm

All-pairs shortest path — finds shortest path between all pairs of vertices.

void floyd_warshall(int dist[V][V], int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

Complexity: O(V³)

Minimum Spanning Tree

What is a Spanning Tree?

A Spanning Tree of a connected graph is a subgraph that:

• Connects all vertices

Has no cycles

• Has exactly V-1 edges

A Minimum Spanning Tree (MST) is the spanning tree with minimum total edge weight.

19.1 Kruskal's Algorithm

1. Sort all edges by weight (ascending)
2. Process edges one by one; add edge if it doesn't create a cycle
3. Stop when V-1 edges added

Uses Union-Find data structure to detect cycles.

Complexity: O(E log E)

19.2 Prim's Algorithm

1. Start with any vertex
2. Greedily add the minimum weight edge connecting tree to a non-tree vertex
3. Repeat until all vertices included

Complexity: O(V² ) or O(E log V) with priority queue