CODEBHAVYA • ADS LEVEL 20

🕸️ Advanced Graph Algorithms

Master minimum spanning trees, shortest paths, directed acyclic graphs, strongly connected components and maximum flow through complete algorithms, C programs, visualization and line-by-line tracing.

LEARNING GOALS

🎯 Learning Objectives

  • Distinguish directed, undirected, weighted, connected and residual graphs.
  • Construct minimum spanning trees using Prim and Kruskal.
  • Compute single-source and all-pairs shortest paths.
  • Detect negative cycles using Bellman–Ford.
  • Produce a topological ordering and identify cycles in a directed graph.
  • Find strongly connected components using Kosaraju.
  • Calculate maximum flow using Edmonds–Karp residual networks.
  • Trace every loop, comparison, relaxation and structural update in C.
GRAPH MODEL AND INVARIANTS

🧭 1. Advanced Graph Foundations

Weighted edge

Associates a cost, distance, capacity or time with a connection.

Cut

Partitions vertices into two sets; crossing edges connect the sets.

Relaxation

Improves a known distance through an edge when a cheaper route exists.

Residual edge

Shows how much additional flow can be sent or cancelled.

Representation Space Check edge Enumerate neighbors
Adjacency matrix O(V²) O(1) O(V)
Adjacency list O(V + E) O(deg u) O(deg u)
Edge list O(E) O(E) O(E)
Tracer rule: A repeated loop iteration returns to the actual loop or edge-reading line. A comparison and a successful update are displayed as separate steps.
CONNECT ALL VERTICES CHEAPLY

🌉 2. Minimum Spanning Trees

A spanning tree of a connected undirected graph contains all V vertices, exactly V − 1 edges and no cycle. A minimum spanning tree has the minimum possible total edge weight.

Prim’s Algorithm

Grow one tree. Repeatedly choose the lightest edge crossing from the visited set to an unvisited vertex.

  1. Set every key to ∞ and the source key to 0.
  2. Select the unused vertex with the minimum key.
  3. Add it to the tree.
  4. Relax its incident edges.

Kruskal’s Algorithm

Grow a forest. Process edges in nondecreasing weight and accept an edge only when it joins different components.

  1. Sort all edges.
  2. Find both component roots.
  3. Skip an edge that creates a cycle.
  4. Union accepted components.
Algorithm Main structure Time Best fit
Prim Priority queue / key array O(E log V) Dense or adjacency-list graphs
Kruskal Sorted edges + DSU O(E log E) Sparse edge-list graphs
OPTIMAL ROUTES

🛣️ 3. Shortest-Path Algorithms

Dijkstra

Greedy single-source shortest paths. Requires nonnegative edge weights.

Bellman–Ford

Relaxes every edge V − 1 times and detects reachable negative cycles.

Floyd–Warshall

Dynamic programming for all-pairs shortest paths using each vertex as an intermediate.

Relaxation Algorithm

  1. Read edge u → v with weight w.
  2. Verify that distance[u] is finite.
  3. Compare distance[u] + w with distance[v].
  4. If it is smaller, update distance[v] and predecessor[v].
Algorithm Negative edges Negative-cycle detection Time
Dijkstra No No O(E log V)
Bellman–Ford Yes Yes O(VE)
Floyd–Warshall Yes Via dist[i][i] < 0 O(V³)
ORDER AND COMPONENT STRUCTURE

🧩 4. Directed Graph Algorithms

Kahn Topological Sort

Place all zero-indegree vertices in a queue. Remove one, output it and reduce every outgoing neighbor’s indegree. Fewer than V outputs proves a cycle.

Kosaraju SCC

Run DFS to record decreasing finish time, transpose every edge, then process vertices in finish-time order to reveal strongly connected components.

Related algorithms: Tarjan finds SCCs in one DFS using discovery and low-link values. The same low-link idea identifies articulation points and bridges in undirected graphs.
CAPACITY-CONSTRAINED NETWORKS

🌊 5. Maximum Flow

A feasible flow respects capacity constraints and flow conservation. Ford–Fulkerson repeatedly augments an s–t path. Edmonds–Karp chooses the shortest augmenting path in number of edges using BFS.

1

Build residual graph

Initial residual capacity equals original capacity.

2

Run BFS

Find a residual path from source to sink.

3

Bottleneck

Take the minimum residual capacity on the path.

4

Augment

Decrease forward capacity and increase reverse capacity.

Edmonds–Karp complexity: O(VE²). At termination, maximum flow equals the capacity of a minimum s–t cut.
COMPLETE TRACEABLE IMPLEMENTATIONS

💻 6. Complete C Programs

Prim’s Minimum Spanning Tree View program 
#include <stdio.h>
#include <limits.h>

#define V 6

int minimumKey(int key[], int used[]) {
    int best = INT_MAX;
    int vertex = -1;

    for (int i = 0; i < V; i++) { /* prim select loop */
        if (!used[i] && key[i] < best) { /* prim select compare */
            best = key[i];
            vertex = i;
        }
    }

    return vertex; /* prim select result */
}

void prim(int graph[V][V]) {
    int parent[V];
    int key[V];
    int used[V] = {0};

    for (int i = 0; i < V; i++) { /* prim initialize */
        key[i] = INT_MAX;
        parent[i] = -1;
    }

    key[0] = 0;

    for (int count = 0; count < V; count++) { /* prim main loop */
        int u = minimumKey(key, used); /* prim choose */

        if (u == -1)
            break;

        used[u] = 1; /* prim add vertex */

        for (int v = 0; v < V; v++) { /* prim edge loop */
            if (
                graph[u][v] &&
                !used[v] &&
                graph[u][v] < key[v]
            ) { /* prim relax compare */
                key[v] = graph[u][v]; /* prim relax update */
                parent[v] = u;
            }
        }
    }

    int total = 0;

    for (int v = 1; v < V; v++) {
        if (parent[v] != -1) {
            printf(
                "%c-%c %d\n",
                'A' + parent[v],
                'A' + v,
                graph[v][parent[v]]
            );

            total += graph[v][parent[v]];
        }
    }

    printf("MST cost = %d\n", total); /* prim output */
}

int main(void) {
    int graph[V][V] = {
        {0, 4, 2, 0, 0, 0},
        {4, 0, 1, 5, 0, 0},
        {2, 1, 0, 8, 10, 0},
        {0, 5, 8, 0, 2, 6},
        {0, 0, 10, 2, 0, 3},
        {0, 0, 0, 6, 3, 0}
    };

    prim(graph);

    return 0;
}
Kruskal’s Minimum Spanning Tree View program 
#include <stdio.h>
#include <stdlib.h>

#define V 6
#define E 9

typedef struct {
    int u;
    int v;
    int w;
} Edge;

int compare(const void *first, const void *second) {
    const Edge *a = first;
    const Edge *b = second;

    return a->w - b->w;
}

int find(int parent[], int vertex) {
    if (parent[vertex] != vertex) {
        parent[vertex] =
            find(parent, parent[vertex]);
    }

    return parent[vertex]; /* kruskal find */
}

void unite(
    int parent[],
    int rank[],
    int first,
    int second
) {
    first = find(parent, first);
    second = find(parent, second);

    if (rank[first] < rank[second]) {
        parent[first] = second;
    } else if (rank[first] > rank[second]) {
        parent[second] = first;
    } else {
        parent[second] = first;
        rank[first]++;
    }
}

int main(void) {
    Edge edges[E] = {
        {0, 1, 4},
        {0, 2, 2},
        {1, 2, 1},
        {1, 3, 5},
        {2, 3, 8},
        {2, 4, 10},
        {3, 4, 2},
        {3, 5, 6},
        {4, 5, 3}
    };

    int parent[V];
    int rank[V] = {0};
    int selected = 0;
    int total = 0;

    for (int i = 0; i < V; i++) { /* kruskal initialize */
        parent[i] = i;
    }

    qsort(
        edges,
        E,
        sizeof(Edge),
        compare
    ); /* kruskal sort */

    for (
        int i = 0;
        i < E && selected < V - 1;
        i++
    ) { /* kruskal edge loop */

        Edge edge = edges[i]; /* kruskal consider */

        int firstRoot =
            find(parent, edge.u);

        int secondRoot =
            find(parent, edge.v);

        if (firstRoot != secondRoot) { /* kruskal cycle check */

            printf(
                "%c-%c %d\n",
                'A' + edge.u,
                'A' + edge.v,
                edge.w
            );

            total += edge.w;
            selected++; /* kruskal accept */

            unite(
                parent,
                rank,
                firstRoot,
                secondRoot
            );
        }
    }

    printf("MST cost = %d\n", total); /* kruskal output */

    return 0;
}
Dijkstra’s Shortest Paths View program 
#include <stdio.h>
#include <limits.h>

#define V 6

int minimumDistance(
    int distance[],
    int completed[]
) {
    int best = INT_MAX;
    int vertex = -1;

    for (int i = 0; i < V; i++) { /* dijkstra select loop */
        if (
            !completed[i] &&
            distance[i] < best
        ) { /* dijkstra select compare */

            best = distance[i];
            vertex = i;
        }
    }

    return vertex; /* dijkstra select result */
}

void dijkstra(
    int graph[V][V],
    int source
) {
    int distance[V];
    int parent[V];
    int completed[V] = {0};

    for (int i = 0; i < V; i++) { /* dijkstra initialize */
        distance[i] = INT_MAX;
        parent[i] = -1;
    }

    distance[source] = 0;

    for (
        int count = 0;
        count < V;
        count++
    ) { /* dijkstra main loop */

        int u = minimumDistance(
            distance,
            completed
        ); /* dijkstra choose */

        if (u == -1)
            break;

        completed[u] = 1; /* dijkstra settle */

        for (int v = 0; v < V; v++) { /* dijkstra edge loop */

            if (
                graph[u][v] &&
                !completed[v] &&
                distance[u] != INT_MAX
            ) { /* dijkstra edge check */

                int candidate =
                    distance[u] +
                    graph[u][v];

                if (
                    candidate < distance[v]
                ) { /* dijkstra relax compare */

                    distance[v] =
                        candidate; /* dijkstra relax update */

                    parent[v] = u;
                }
            }
        }
    }

    for (int i = 0; i < V; i++) {
        printf(
            "A to %c = %d\n",
            'A' + i,
            distance[i]
        ); /* dijkstra output */
    }
}

int main(void) {
    int graph[V][V] = {
        {0, 4, 2, 0, 0, 0},
        {4, 0, 1, 5, 0, 0},
        {2, 1, 0, 8, 10, 0},
        {0, 5, 8, 0, 2, 6},
        {0, 0, 10, 2, 0, 3},
        {0, 0, 0, 6, 3, 0}
    };

    dijkstra(graph, 0);

    return 0;
}
Bellman–Ford Shortest Paths View program 
#include <stdio.h>
#include <limits.h>

#define V 6
#define E 9

typedef struct {
    int u;
    int v;
    int w;
} Edge;

int main(void) {
    Edge edges[E] = {
        {0, 1, 4},
        {0, 2, 2},
        {1, 2, -1},
        {1, 3, 5},
        {2, 3, 8},
        {2, 4, 10},
        {3, 4, 2},
        {3, 5, 6},
        {4, 5, 3}
    };

    int distance[V];
    int parent[V];

    for (int i = 0; i < V; i++) { /* bellman initialize */
        distance[i] = INT_MAX;
        parent[i] = -1;
    }

    distance[0] = 0;

    for (
        int pass = 1;
        pass < V;
        pass++
    ) { /* bellman pass loop */

        int changed = 0;

        for (int i = 0; i < E; i++) { /* bellman edge loop */

            Edge edge =
                edges[i]; /* bellman read edge */

            if (
                distance[edge.u] != INT_MAX &&
                distance[edge.u] + edge.w
                    < distance[edge.v]
            ) { /* bellman relax compare */

                distance[edge.v] =
                    distance[edge.u] +
                    edge.w; /* bellman relax update */

                parent[edge.v] = edge.u;
                changed = 1;
            }
        }

        if (!changed) {
            break; /* bellman early stop */
        }
    }

    for (int i = 0; i < E; i++) { /* bellman cycle loop */

        Edge edge = edges[i];

        if (
            distance[edge.u] != INT_MAX &&
            distance[edge.u] + edge.w
                < distance[edge.v]
        ) { /* bellman cycle check */

            printf("Negative cycle\n");
            return 0;
        }
    }

    for (int i = 0; i < V; i++) {
        printf(
            "A to %c = %d\n",
            'A' + i,
            distance[i]
        ); /* bellman output */
    }

    return 0;
}
Floyd–Warshall All-Pairs Shortest Paths View program 
#include <stdio.h>

#define V 5
#define INF 99999

int main(void) {
    int distance[V][V] = { /* floyd initialize */
        {0, 3, INF, 7, INF},
        {8, 0, 2, INF, INF},
        {5, INF, 0, 1, INF},
        {2, INF, INF, 0, 4},
        {INF, INF, 1, INF, 0}
    };

    for (int k = 0; k < V; k++) { /* floyd k loop */

        for (int i = 0; i < V; i++) { /* floyd i loop */

            for (int j = 0; j < V; j++) { /* floyd j loop */

                if (
                    distance[i][k] != INF &&
                    distance[k][j] != INF
                ) { /* floyd path check */

                    int through =
                        distance[i][k] +
                        distance[k][j];

                    if (
                        through < distance[i][j]
                    ) { /* floyd relax compare */

                        distance[i][j] =
                            through; /* floyd relax update */
                    }
                }
            }
        }
    }

    for (int i = 0; i < V; i++) { /* floyd output */

        for (int j = 0; j < V; j++) {
            printf(
                "%5d",
                distance[i][j]
            );
        }

        printf("\n");
    }

    return 0;
}
Kahn’s Topological Sort View program 
#include <stdio.h>

#define V 6

int main(void) {
    int graph[V][V] = {
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    int indegree[V] = {0};
    int queue[V];
    int front = 0;
    int rear = 0;
    int count = 0;

    for (int u = 0; u < V; u++) { /* topo indegree outer */

        for (int v = 0; v < V; v++) {

            if (graph[u][v]) {
                indegree[v]++; /* topo indegree update */
            }
        }
    }

    for (int i = 0; i < V; i++) {

        if (indegree[i] == 0) {
            queue[rear++] =
                i; /* topo enqueue initial */
        }
    }

    while (front < rear) { /* topo queue loop */

        int u =
            queue[front++]; /* topo dequeue */

        printf(
            "%c ",
            'A' + u
        ); /* topo output vertex */

        count++;

        for (int v = 0; v < V; v++) { /* topo edge loop */

            if (graph[u][v]) {

                indegree[v]--; /* topo reduce indegree */

                if (indegree[v] == 0) {
                    queue[rear++] =
                        v; /* topo enqueue */
                }
            }
        }
    }

    if (count != V) {
        printf(
            "Cycle detected"
        ); /* topo cycle check */
    }

    printf("\n");

    return 0;
}
Kosaraju Strongly Connected Components View program 
#include <stdio.h>

#define V 6

void firstDFS(
    int vertex,
    int graph[V][V],
    int visited[],
    int stack[],
    int *top
) {
    visited[vertex] = 1; /* kosa first visit */

    for (int next = 0; next < V; next++) { /* kosa first edge loop */

        if (
            graph[vertex][next] &&
            !visited[next]
        ) {
            firstDFS(
                next,
                graph,
                visited,
                stack,
                top
            ); /* kosa first recurse */
        }
    }

    stack[(*top)++] =
        vertex; /* kosa finish push */
}

void secondDFS(
    int vertex,
    int transpose[V][V],
    int visited[]
) {
    visited[vertex] = 1; /* kosa second visit */

    printf(
        "%c ",
        'A' + vertex
    );

    for (int next = 0; next < V; next++) { /* kosa second edge loop */

        if (
            transpose[vertex][next] &&
            !visited[next]
        ) {
            secondDFS(
                next,
                transpose,
                visited
            ); /* kosa second recurse */
        }
    }
}

int main(void) {
    int graph[V][V] = {
        {0, 1, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 1, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    int transpose[V][V] = {{0}};
    int visited[V] = {0};
    int stack[V];
    int top = 0;

    for (int i = 0; i < V; i++) {

        if (!visited[i]) {
            firstDFS(
                i,
                graph,
                visited,
                stack,
                &top
            ); /* kosa first start */
        }
    }

    for (int u = 0; u < V; u++) {

        for (int v = 0; v < V; v++) {

            transpose[v][u] =
                graph[u][v]; /* kosa transpose */
        }
    }

    for (int i = 0; i < V; i++) {
        visited[i] = 0;
    }

    while (top > 0) { /* kosa stack loop */

        int vertex =
            stack[--top]; /* kosa pop */

        if (!visited[vertex]) {

            secondDFS(
                vertex,
                transpose,
                visited
            ); /* kosa component */

            printf("\n");
        }
    }

    return 0;
}
Edmonds–Karp Maximum Flow View program 
#include <stdio.h>
#include <limits.h>

#define V 6

int bfs(
    int residual[V][V],
    int source,
    int sink,
    int parent[]
) {
    int visited[V] = {0};
    int queue[V];
    int front = 0;
    int rear = 0;

    queue[rear++] = source;
    visited[source] = 1; /* flow bfs initialize */

    while (front < rear) { /* flow bfs loop */

        int u =
            queue[front++]; /* flow dequeue */

        for (int v = 0; v < V; v++) { /* flow edge loop */

            if (
                !visited[v] &&
                residual[u][v] > 0
            ) { /* flow residual check */

                parent[v] = u;
                visited[v] = 1;

                queue[rear++] =
                    v; /* flow enqueue */
            }
        }
    }

    return visited[sink]; /* flow bfs result */
}

int main(void) {
    int capacity[V][V] = {
        {0, 16, 13, 0, 0, 0},
        {0, 0, 10, 12, 0, 0},
        {0, 4, 0, 0, 14, 0},
        {0, 0, 9, 0, 0, 20},
        {0, 0, 0, 7, 0, 4},
        {0, 0, 0, 0, 0, 0}
    };

    int residual[V][V];
    int parent[V];
    int maximum = 0;

    for (int u = 0; u < V; u++) {

        for (int v = 0; v < V; v++) {

            residual[u][v] =
                capacity[u][v]; /* flow initialize */
        }
    }

    while (
        bfs(
            residual,
            0,
            5,
            parent
        )
    ) { /* flow augment loop */

        int pathFlow = INT_MAX;

        for (
            int v = 5;
            v != 0;
            v = parent[v]
        ) { /* flow bottleneck loop */

            int u = parent[v];

            if (
                residual[u][v] < pathFlow
            ) {
                pathFlow =
                    residual[u][v]; /* flow bottleneck */
            }
        }

        for (
            int v = 5;
            v != 0;
            v = parent[v]
        ) { /* flow update loop */

            int u = parent[v];

            residual[u][v] -=
                pathFlow; /* flow forward update */

            residual[v][u] +=
                pathFlow; /* flow reverse update */
        }

        maximum +=
            pathFlow; /* flow total update */
    }

    printf(
        "Maximum flow = %d\n",
        maximum
    ); /* flow output */

    return 0;
}
INTERACTIVE GRAPH ALGORITHMS

🎬 7. Premium Advanced Graph Visualizer

Select an algorithm and follow vertex selection, edge inspection, relaxation, union, queue, stack, component and residual-flow updates.

CodeBhavya Code Bhavya
Choose an algorithm, verify the graph and click Load Visualizer.
SELECTABLE C PROGRAM TRACER

🔍 8. Program Tracing — Advanced Graphs

The complete selected C program appears with executable-line highlighting, live variables, graph state and automatic current-line scrolling.

Select a program and click Load Program Tracer.
ASYMPTOTIC SUMMARY

⏱️ 9. Complexity Comparison

Algorithm Time Space Output
Prim O(E log V) O(V + E) MST
Kruskal O(E log E) O(V + E) MST
Dijkstra O(E log V) O(V + E) Single-source distances
Bellman–Ford O(VE) O(V) Distances and negative cycle
Floyd–Warshall O(V³) O(V²) All-pairs distances
Kahn O(V + E) O(V) Topological order or cycle
Kosaraju O(V + E) O(V + E) SCC partition
Edmonds–Karp O(VE²) O(V²) Maximum flow
CHECK YOUR UNDERSTANDING

✍️ 10. Practice Problems

Solve each problem first. Use Hint only when required, then open Show Answer.

1. How many edges does a spanning tree of V vertices contain?

2. Why does Kruskal require DSU?

3. Can Dijkstra process a negative edge safely?

4. Why are V − 1 Bellman–Ford passes sufficient?

5. What Floyd–Warshall value reveals a negative cycle?

6. When does Kahn’s algorithm report a cycle?

7. Why does Kosaraju transpose the graph?

8. What is an augmenting path?

9. What does a reverse residual edge permit?

10. Which MST cut property justifies a greedy choice?

QUICK RECALL

📝 11. Quick Revision

  • Prim grows one tree; Kruskal joins a forest using DSU.
  • Dijkstra requires nonnegative weights.
  • Bellman–Ford supports negative edges and detects reachable negative cycles.
  • Floyd–Warshall solves all-pairs shortest paths in O(VÂł).
  • Kahn’s algorithm uses indegrees and a zero-indegree queue.
  • Kosaraju uses finish order, a transpose and a second DFS.
  • Residual forward and reverse edges make flow decisions reversible.
  • Edmonds–Karp uses BFS and runs in O(VE²).
  • Relaxation comparisons and updates are traced separately.
  • Repeated iterations return to their actual loop line.