Skip to main content

Minimum Spanning Tree, Prim's Algorithm, Kruskal's Algorithm

Overview​

The Minimum Spanning Tree (MST) is an important concept in graph theory, primarily used for weighted undirected graphs. A minimum spanning tree is a connected subgraph that includes all vertices and minimizes the sum of edge weights. MSTs are widely used in network design, cluster analysis, and other fields.

Video Explanation​

Kruskal's and Prim's Algorithm Animation Demo (Bilibili)

Basic Concepts​

  • Undirected Graph: A graph in which edges have no direction.
  • Weighted Graph: A graph in which each edge has a weight (cost).
  • Spanning Tree: A connected subgraph that includes all vertices of the graph but contains no cycles.
  • Minimum Spanning Tree: A spanning tree in which the sum of all edge weights is minimized.

Minimum Spanning Tree Example​

First, here is the original graph:

graph TD;
    A((A)) ---|2| B((B));
    A ---|3| C((C));
    A ---|1| D((D));
    B ---|4| C;
    B ---|2| E((E));
    C ---|5| E;
    D ---|3| E;

In this graph, nodes A, B, C, D, and E are vertices, and the numbers on the edges represent edge weights.

Then, here is the minimum spanning tree of the original graph:

graph TD;
    A((A)) ---|1| D((D));
    A ---|2| B((B));
    B ---|2| E((E));
    A ---|3| C((C));

In this minimum spanning tree, all vertices are included, and the total weight is minimized.

Explanation:​

  • Original Graph: Each vertex in the graph is connected to other vertices through edges of various weights.
  • Minimum Spanning Tree: A subset of edges is selected from the original graph such that all vertices are connected and the sum of the selected edge weights is minimized.

This graph provides a visual understanding of the minimum spanning tree concept, illustrating how to select the minimum-weight edges to connect all vertices while maintaining connectivity.

Common Algorithms​

Both Prim's and Kruskal's algorithms are greedy algorithms

Prim's Algorithm​

Prim's algorithm is a greedy algorithm that works by gradual expansion. It starts from a single vertex and progressively adds the minimum-weight edge until all vertices are included in the tree.

Steps:

  1. Choose a starting vertex and add it to the minimum spanning tree.
  2. Repeat the following steps until the minimum spanning tree includes all vertices:
    • Among all edges connecting included and non-included vertices, select the edge with the minimum weight. (Here, it is the edge with the minimum weight from a non-included vertex to the set of already-included vertices, not the edge weight to the starting vertex -- this is where it differs from Dijkstra's algorithm.)
    • Add the selected edge and its corresponding vertex to the minimum spanning tree.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5

// Select the edge with minimum weight among all edges connecting included and non-included vertices
// Here, edges connected to vertices in the included set are updated to find the minimum weight edge
int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (mstSet[v] == 0 && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}


// Print MST
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]) {

    // graph[V][V] stores edge weight values
    
    int parent[V]; // Parent nodes
    int key[V]; // Current weight to the MST set
    int mstSet[V]; // Whether vertex is included in MST set

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

    key[0] = 0;
    parent[0] = -1;
    
    // Prim's algorithm
    for (int count = 0; count < V - 1; count++) {
        // Find vertex with minimum weight edge
        int u = minKey(key, mstSet);
        
        // Add to MST set
        mstSet[u] = 1;
        
        // Update vertices connected to the newly added vertex
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == 0 && 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;
}

Kruskal's Algorithm​

Kruskal's algorithm is an edge-based greedy algorithm. Initially, all vertices are independent sets. Edges are then sorted by weight in ascending order, and the minimum-weight edge that does not form a cycle is progressively selected until the tree includes all vertices.

Steps:

  1. Sort all edges by weight in ascending order.
  2. Select the edge with the minimum weight. If the two vertices connected by this edge are not in the same set, add the edge to the minimum spanning tree and merge the two vertex sets.
  3. Repeat the above steps until the minimum spanning tree includes all vertices.
#include <stdio.h>
#include <stdlib.h>

#define V 5
#define E 7

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(graph->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 xroot = find(subsets, x);
    int yroot = find(subsets, y);

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

int compareEdges(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->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]), compareEdges);

    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 next_edge = graph->edge[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        if (x != y) {
            result[e++] = next_edge;
            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;
}

Application Scenarios​

  1. Network Design: Such as cable and telephone line connection design, where the minimum spanning tree can help find the lowest-cost connectivity solution.
  2. Cluster Analysis: In data mining, the minimum spanning tree can be used for cluster analysis to discover natural clusters in data.
  3. Transportation Networks: Planning highways, railways, etc., to minimize total construction costs.

Summary​

The minimum spanning tree is an important problem in graph theory that can be efficiently solved using Prim's and Kruskal's algorithms. The above content provides a detailed introduction to its concepts, algorithm steps, and C implementation code for ease of understanding and application.

Greedy Algorithms​

Introduction​

A greedy algorithm is an algorithm that solves a global optimization problem by making the locally optimal choice at each step. It is typically used to solve optimization problems such as shortest paths, minimum spanning trees, and activity selection problems.

Application Scenarios​

Greedy algorithms are applicable to the following types of problems:

  • Shortest Path Problem: For example, Dijkstra's algorithm.
  • Minimum Spanning Tree Problem: For example, Prim's algorithm and Kruskal's algorithm.
  • Activity Selection Problem: Selecting the maximum number of non-overlapping activities.
  • Coin Change Problem: Making change with the minimum number of coins.

Steps of a Greedy Algorithm​

The general steps of a greedy algorithm are as follows:

  1. Choose an Initial State: Select an initial state based on the problem description.
  2. Find the Local Optimum: Select the optimal solution at the current state.
  3. Update the State: Update the current state based on the selected optimal solution.
  4. Repeat: Repeat steps 2 and 3 until a termination condition is met.

Example Code for a Greedy Algorithm​

Example: Coin Change Problem​

Given coins of different denominations and a total amount, find the combination of coins with the minimum count.

#include <stdio.h>

void findMinCoins(int coins[], int n, int amount) {
    int result[n];
    for (int i = 0; i < n; i++) {
        result[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            result[i]++;
        }
    }

    printf("Coin combination for change:\n");
    for (int i = 0; i < n; i++) {
        if (result[i] != 0) {
            printf("%d coins of denomination %d\n", result[i], coins[i]);
        }
    }
}

int main() {
    int coins[] = {25, 10, 5, 1};
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 63;

    findMinCoins(coins, n, amount);
    return 0;
}

Advantages and Disadvantages of Greedy Algorithms​

Advantages​

  • Simple and Easy to Understand: Greedy algorithms are typically intuitive, easy to understand, and easy to implement.
  • High Efficiency: In suitable scenarios, greedy algorithms have low time complexity and can quickly find solutions to problems.

Disadvantages​

  • Limitations: Greedy algorithms are not applicable to all problems. They can only guarantee a global optimum for problems that satisfy the greedy-choice property and the optimal substructure property.
  • Local Optimum Is Not Always Global Optimum: In some cases, the solution found by a greedy algorithm may only be a local optimum rather than a global optimum.