This article does not have a corresponding language version

New version found

The website seems to have new content, do you want to update?

Kruskal’s Algorithm for Generating Minimum Spanning Trees

a Problem Analysis

We need to use Kruskal’s algorithm to find the minimum spanning tree (MST) for a graph with 10 nodes and 20 edges. Kruskal’s algorithm is based on a greedy approach, constructing the MST by iteratively selecting edges with the smallest weights while ensuring no cycles are formed.

b Algorithm Design

Key Steps of Kruskal’s Algorithm:

Edge Sorting:

All edges are sorted in ascending order of their weights.

sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
    return a.weight < b.weight;
});

The sort function sorts the elements in a container based on a specified comparison rule. Here, it sorts edges in ascending order of their weights, allowing Kruskal’s algorithm to select edges with the smallest weights first. 1. edges.begin() and edges.end(): These parameters define the range of elements to be sorted. begin() returns an iterator to the first element, and end() returns an iterator to the position after the last element. 2. [](const Edge& a, const Edge& b) { return a.weight < b.weight; }: This is a lambda expression that defines the comparison rule. It compares two edges a and b based on their weights and returns true if a.weight is less than b.weight, ensuring ascending order. 3. const Edge& a and const Edge& b are the parameters of the lambda function, representing the two edges being compared. 4. return a.weight < b.weight; ensures that edges are sorted in ascending order of their weights.

Union-Find Initialization:

Initialize the Union-Find (Disjoint Set Union, DSU) data structure, where each node is initially its own parent.

  • The Union-Find data structure is used to manage sets of elements, supporting two primary operations: Find (to determine the root of an element) and Union (to merge two sets).
  • Basic Operations:
    1. Find: Determines the root of an element, which identifies the set it belongs to.
    2. Union: Merges two sets by connecting their roots.
  • Implementation Details:
    • Typically implemented using arrays where each element’s value represents its parent. Initially, each element is its own parent.
  • Optimizations:
    • Path Compression: During the Find operation, the path from the element to its root is flattened, improving future Find operations.
    • Union by Rank: During the Union operation, the smaller tree (in terms of depth) is attached to the root of the larger tree to keep the tree balanced and operations efficient.
Edge Traversal:

Traverse the sorted edges, adding each edge to the MST if it does not form a cycle.

Implementation:

// Kruskal's Algorithm
vector<Edge> kruskal(vector<Edge>& edges, int numNodes) { // Input: edge list and number of nodes
    // Sort edges by weight in ascending order
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) 
// Parameters: start iterator, end iterator, lambda expression (comparison function)
{
        return a.weight < b.weight; // Comparison rule: sort edges by weight in ascending order
    });

    // Initialize Union-Find
    UnionFind uf(numNodes); // UnionFind(size)

    // Store edges of the MST
    vector<Edge> result;

    // Traverse sorted edges
    for (const Edge& edge : edges) {
        // Check if adding this edge forms a cycle
        if (uf.find(edge.start) != uf.find(edge.end)) { // If the start and end nodes are in different sets (subtrees)
            // No cycle formed, add edge to MST
            result.push_back(edge);
            uf.unite(edge.start, edge.end); // Merge the two subtrees (mark as the same set) to prevent cycles
        }
    }

    return result;
}

c Data Structure Design

1. Edge Struct:

// Edge struct
struct Edge {
    int start, end, weight; // Start node, end node, and weight of the edge
};
  • The Edge struct represents an edge in the graph, containing the start node, end node, and weight.

2. UnionFind Class:

// Union-Find implementation
class UnionFind {
public:
    UnionFind(int size) : parent(size), rank(size, 0) {
// `parent` stores the root of each node, initially set to itself; `rank` approximates tree depth, initialized to 0
        for (int i = 0; i < size; ++i) {
            parent[i] = i; // Root initially set to itself
        }
    }

    int find(int x) { // Find the root of a node
        if (x != parent[x]) { // If `x` is not its own parent (has an ancestor)
            parent[x] = find(parent[x]); // Path compression: set parent to root
        }
        return parent[x]; // Return the root
    }

    void unite(int x, int y) { // Merge two subtrees
        int rootX = find(x); // Root of `x`
        int rootY = find(y); // Root of `y`

        if (rootX != rootY) { // If `x` and `y` are in different sets (subtrees)
            if (rank[rootX] < rank[rootY]) {
                // If `x`'s subtree is shallower than `y`'s
                parent[rootX] = rootY;
                // Attach `x`'s subtree to `y`'s to avoid increasing depth
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else { // If subtrees have the same depth
                parent[rootX] = rootY; // Attach `x`'s subtree to `y`'s
                rank[rootY]++; // Increment depth after merge
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
};
  • The UnionFind class implements the Union-Find data structure for cycle detection. The find function locates the root of a node, and the unite function merges two sets.
  • In the constructor, the rank array is initialized to 0, representing the approximate depth of each tree. Initially, each node is its own tree with depth 0.
  • During unite, the rank array ensures that the smaller tree is attached to the larger one to maintain balance and efficiency.

d Debugging Process

During debugging, intermediate outputs (e.g., sorted edges, MST construction steps, and Union-Find states) were examined to verify the algorithm’s correctness. Edge cases, such as disconnected graphs, were also tested.

e Output

Graph:
0 - 1 : 4
0 - 2 : 1
1 - 3 : 2
1 - 4 : 8
2 - 5 : 3
2 - 6 : 7
3 - 7 : 5
3 - 8 : 1
4 - 9 : 6
5 - 6 : 2
6 - 8 : 6
7 - 9 : 3
8 - 9 : 9
1 - 2 : 2
3 - 4 : 3
5 - 7 : 4
6 - 9 : 7
0 - 3 : 6
2 - 8 : 5
4 - 5 : 4
Edges in the minimum spanning tree:
0 - 2 : 1
3 - 8 : 1
1 - 3 : 2
1 - 2 : 2
5 - 6 : 2
2 - 5 : 3
3 - 4 : 3
7 - 9 : 3
5 - 7 : 4

f Source Code

#include <iostream>
#include <vector>
#include <algorithm> // For `sort`

using namespace std;

// Edge struct
struct Edge {
    int start, end, weight; // Start node, end node, and weight of the edge
};

// Union-Find implementation
class UnionFind {
public:
    UnionFind(int size) : parent(size), rank(size, 0) {
// `parent` stores the root of each node, initially set to itself; `rank` approximates tree depth, initialized to 0
        for (int i = 0; i < size; ++i) {
            parent[i] = i; // Root initially set to itself
        }
    }

    int find(int x) { // Find the root of a node
        if (x != parent[x]) { // If `x` is not its own parent (has an ancestor)
            parent[x] = find(parent[x]); // Path compression: set parent to root
        }
        return parent[x]; // Return the root
    }

    void unite(int x, int y) { // Merge two subtrees
        int rootX = find(x); // Root of `x`
        int rootY = find(y); // Root of `y`

        if (rootX != rootY) { // If `x` and `y` are in different sets (subtrees)
            if (rank[rootX] < rank[rootY]) {
                // If `x`'s subtree is shallower than `y`'s
                parent[rootX] = rootY;
                // Attach `x`'s subtree to `y`'s to avoid increasing depth
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else { // If subtrees have the same depth
                parent[rootX] = rootY; // Attach `x`'s subtree to `y`'s
                rank[rootY]++; // Increment depth after merge
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
};

// Kruskal's Algorithm
vector<Edge> kruskal(vector<Edge>& edges, int numNodes) { // Input: edge list and number of nodes
    // Sort edges by weight in ascending order
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) 
// Parameters: start iterator, end iterator, lambda expression (comparison function)
{
        return a.weight < b.weight; // Comparison rule: sort edges by weight in ascending order
    });

    // Initialize Union-Find
    UnionFind uf(numNodes); // UnionFind(size)

    // Store edges of the MST
    vector<Edge> result;

    // Traverse sorted edges
    for (const Edge& edge : edges) {
        // Check if adding this edge forms a cycle
        if (uf.find(edge.start) != uf.find(edge.end)) { // If the start and end nodes are in different sets (subtrees)
            // No cycle formed, add edge to MST
            result.push_back(edge);
            uf.unite(edge.start, edge.end); // Merge the two subtrees (mark as the same set) to prevent cycles
        }
    }

    return result;
}

int main() {
    // Create a graph with 10 nodes
    int numNodes = 10;

    // Manually define edges with start, end, and weight
    vector<Edge> edges = {
        {0, 1, 4},
        {0, 2, 1},
        {1, 3, 2},
        {1, 4, 8},
        {2, 5, 3},
        {2, 6, 7},
        {3, 7, 5},
        {3, 8, 1},
        {4, 9, 6},
        {5, 6, 2},
        {6, 8, 6},
        {7, 9, 3},
        {8, 9, 9},
        {1, 2, 2},
        {3, 4, 3},
        {5, 7, 4},
        {6, 9, 7},
        {0, 3, 6},
        {2, 8, 5},
        {4, 5, 4}
    };
    // Output the graph
    cout << "Graph:" << endl;
    for (const Edge& edge : edges) {
        cout << edge.start << " - " << edge.end << " : " << edge.weight << endl;
    }
    // Run Kruskal's algorithm
    vector<Edge> minSpanningTree = kruskal(edges, numNodes);

    // Output edges in the MST
    cout << "Edges in the minimum spanning tree:" << endl;
    for (const Edge& edge : minSpanningTree) {
        cout << edge.start << " - " << edge.end << " : " << edge.weight << endl;
    }

    return 0;
}

Dijkstra’s Algorithm for Solving Shortest Path in Weighted Graphs

a Problem Analysis

The code implements Dijkstra’s algorithm to solve the single-source shortest path problem in a weighted graph. Given an adjacency matrix representation of the graph, the algorithm computes the shortest distances from a specified start node to all other nodes.

b Algorithm Design

1. Initialization

int n = graph.size();
distances.resize(n, INF);
  • Analysis: The number of nodes n is determined from the graph’s size. The distances array is initialized with INF (infinity), representing initially unknown distances.

2. Priority Queue Setup

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
distances[start] = 0;
pq.push({0, start});
  • Analysis: A priority queue pq is created to manage nodes by their current shortest distance. The start node’s distance is set to 0, and it is added to the queue.

3. Main Loop

while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();

    for (int v = 0; v < n; ++v) {
        if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) {
            distances[v] = distances[u] + graph[u][v];
            pq.push({distances[v], v});
        }
    }
}
  • Analysis: The loop extracts the node u with the smallest current distance. For each neighbor v of u, if a shorter path is found via u, the distance is updated, and v is added to the queue.

4. Termination

  • Analysis: The algorithm terminates when the queue is empty, having processed all nodes and finalized their shortest distances.

c Data Structure Design

1. Graph (Adjacency Matrix)

typedef vector<vector<int>> Graph;
  • Analysis: The Graph is represented as a 2D vector where graph[u][v] holds the weight of the edge from node u to v. A weight of 0 indicates no edge.

2. Distances Array

vector<int> distances;
  • Analysis: The distances array stores the shortest known distances from the start node to each node, initialized to INF and updated during the algorithm’s execution.

3. Priority Queue

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  • Analysis: The priority queue pq holds pairs of distances and nodes, ordered by distance. The greater comparator ensures the smallest distance is always processed first.

d Debugging Process

  • Intermediate outputs (e.g., queue states, distance updates) were logged to verify correctness.
  • Edge cases (e.g., no edges, negative weights) were tested to ensure robustness.
  • Multiple test cases confirmed the algorithm’s accuracy and efficiency.

e Output

The final output shows the shortest distances from the start node to all other nodes, matching expectations.

Distance from node 0 to 0: 0
Distance from node 0 to 1: 2
Distance from node 0 to 2: 3
Distance from node 0 to 3: 9
Distance from node 0 to 4: 6

f Source Code

#include <iostream>
#include <vector>
#include <queue> // For priority_queue
#include <climits> // For INT_MAX

using namespace std;

#define INF INT_MAX

// Graph representation using adjacency matrix
typedef vector<vector<int>> Graph;
// 2D vector where graph[u][v] represents the weight of the edge from node `u` to `v`

// Dijkstra's Algorithm
void dijkstra(const Graph& graph, int start, vector<int>& distances) {
// Input: graph, start node, and distances array
    int n = graph.size(); // Number of nodes
    distances.resize(n, INF);  // Initialize distances to infinity

    // Priority queue to manage nodes by their current shortest distance
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// Pairs are {distance, node}, stored in a vector, ordered by distance (smallest first)

    distances[start] = 0;  // Distance from start to itself is 0
    pq.push({0, start});   // Add start node to the queue

    while (!pq.empty()) {
        int u = pq.top().second;  // Extract the node with the smallest current distance
        pq.pop();

        for (int v = 0; v < n; v++) {
            if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) {
                // If a shorter path to `v` is found via `u`, update the distance
                distances[v] = distances[u] + graph[u][v];
                pq.push({distances[v], v});  // Add the updated distance and node to the queue
            }
        }
    }
}

int main() {
    // Example graph represented as an adjacency matrix
    Graph graph = {
        {0, 2, 4, 0, 0},
        {0, 0, 1, 7, 0},
        {0, 0, 0, 0, 3},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0,

Author: 孤筝

Title: Data Structure Lab Report 7 – Kruskal's Algorithm and the Minimum Spanning Tree Problem, Dijkstra's Algorithm and the Shortest Path Problem in Weighted Graphs

Published: 2023-12-12 14:58:44

Updated: 2023-12-12 14:58:44

License: All articles on this blog are licensed under the BY-NC-SA license agreement unless otherwise stated. Please indicate the source when reprinting!

Comments 0 Readings

When will I have a drink and discuss the details again?

waline