Chapter 21 – Graph Algorithms

Chapter 21: Graph Algorithms

Welcome back! In this chapter, we’ll explore Graph Algorithms, which are crucial in solving problems related to networks, connections, and paths. These algorithms help us navigate through graphs and solve problems like finding the shortest path, traversing graphs, and much more.

We’ll focus on two widely-used algorithms for solving problems involving graphs:

1. Shortest Path Algorithms
2. Minimum Spanning Tree (MST) Algorithms

Let’s dive right in!

---

21.1 Shortest Path Algorithms

In many real-world applications like GPS navigation, computer networks, and transportation systems, we are often asked to find the shortest path from one point to another in a graph.

21.1.1 Dijkstra’s Algorithm

Dijkstra’s Algorithm is used to find the shortest path from a source node to all other nodes in a graph with non-negative edge weights.

Problem Definition:

Given a graph and a source node, find the shortest path from the source to all other nodes.

Algorithm Steps:

1. Create a set of all nodes in the graph.
2. Assign a tentative distance value to every node: 0 for the source node and infinity for all other nodes.
3. While there are unvisited nodes:
   • Pick the unvisited node with the smallest tentative distance.
   • Update the tentative distances of its neighboring nodes.
   • Mark the node as visited.

Dijkstra’s Algorithm (in C):

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    dijkstra(graph, 0);
    return 0;
}

Explanation:

• The graph is represented by an adjacency matrix where graph[i][j] represents the weight of the edge between vertices i and j. If there is no edge, the value is 0.
• We maintain an array dist[] where dist[i] holds the shortest distance from the source to vertex i.
• sptSet[] keeps track of vertices for which we have finalized the shortest distance.

Time Complexity:

The time complexity of this implementation is O(V²), where V is the number of vertices.

---

21.2 Minimum Spanning Tree (MST) Algorithms

Next up, we’ll look at Minimum Spanning Trees (MST). This is a fundamental problem in network design.

Problem Definition:

Given a connected, undirected graph, a Minimum Spanning Tree is a subset of the edges that connects all the vertices together without any cycles and with the minimum possible total edge weight.

Two well-known algorithms to find MSTs:

1. Prim’s Algorithm
2. Kruskal’s Algorithm

---

21.2.1 Prim’s Algorithm

Prim’s Algorithm finds a minimum spanning tree by starting from a single vertex and growing the tree one edge at a time, always choosing the smallest edge that connects a new vertex to the tree.

Algorithm Steps:

1. Initialize the minimum spanning tree (MST) with a single vertex.
2. Repeatedly add the smallest edge that connects a vertex inside the MST to one outside it.
3. Stop when all vertices are in the MST.

Prim’s Algorithm (in C):

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 5

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}

void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    primMST(graph);
    return 0;
}

Explanation:

• We represent the graph using an adjacency matrix. graph[i][j] contains the weight of the edge between vertex i and j.
• key[] keeps track of the minimum edge weights that connect vertices to the MST.
• parent[] stores the constructed MST.

Time Complexity:

The time complexity of Prim’s algorithm is O(V²).

---

21.2.2 Kruskal’s Algorithm

Kruskal’s Algorithm works by sorting all the edges of the graph in non-decreasing order of their weight. It then repeatedly adds the smallest edge to the MST unless doing so would form a cycle.

Algorithm Steps:

1. Sort all edges in non-decreasing order of their weight.
2. Pick the smallest edge. If it doesn’t form a cycle, add it to the MST.
3. Repeat until there are exactly V-1 edges in the MST.

Kruskal’s Algorithm (in C):

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

#define V 4
#define E 5

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*) malloc(E * sizeof(struct Edge));
    return graph;
}

struct subset

 {
    int parent;
    int rank;
};

int find(struct subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y) {
    int rootX = find(subsets, x);
    int rootY = find(subsets, y);

    if (subsets[rootX].rank < subsets[rootY].rank)
        subsets[rootX].parent = rootY;
    else if (subsets[rootX].rank > subsets[rootY].rank)
        subsets[rootY].parent = rootX;
    else {
        subsets[rootY].parent = rootX;
        subsets[rootX].rank++;
    }
}

int compare(const void* a, const void* b) {
    struct Edge* edgeA = (struct Edge*) a;
    struct Edge* edgeB = (struct Edge*) b;
    return edgeA->weight > edgeB->weight;
}

void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];
    int e = 0;
    int i = 0;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);

    struct subset* subsets = (struct subset*) malloc(V * sizeof(struct subset));

    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    while (e < V - 1 && i < graph->E) {
        struct Edge nextEdge = graph->edge[i++];
        int x = find(subsets, nextEdge.src);
        int y = find(subsets, nextEdge.dest);

        if (x != y) {
            result[e++] = nextEdge;
            Union(subsets, x, y);
        }
    }

    printf("Following are the edges in the constructed MST:\n");
    for (i = 0; i < e; ++i)
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}

int main() {
    int V = 4;
    int E = 5;
    struct Graph* graph = createGraph(V, E);

    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;

    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;

    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;

    KruskalMST(graph);
    return 0;
}

Explanation:

• We represent the graph using an edge list.
• find() function helps in finding the parent (or representative) of the set containing the vertex.
• Union() function merges two subsets.

Time Complexity:

The time complexity of Kruskal’s algorithm is O(E log V), where E is the number of edges and V is the number of vertices.

---

Wrapping Up Graph Algorithms

In this chapter, we’ve explored:

• Shortest Path Algorithms, such as Dijkstra’s Algorithm for finding the shortest path in weighted graphs.
• Minimum Spanning Tree Algorithms, including Prim’s and Kruskal’s algorithms for constructing MSTs efficiently.

Graph algorithms form the backbone of many real-world systems, from navigation to network optimization.

In the next chapter, we’ll look into Advanced Graph Algorithms like Depth-First Search (DFS), Breadth-First Search (BFS), and more. Stay tuned!

---

Next Up: Chapter 22: Advanced Graph Algorithms