How to use Kruskal's algorithm in C++

How to use the Kruskal algorithm in C

The Kruskal algorithm is a commonly used greedy algorithm to solve the minimum spanning tree problem. In programming using C, we can understand and use Kruskal's algorithm through simple code examples.

The basic idea of ​​Kruskal's algorithm is to continuously select edges with the smallest edge weights that do not form a loop until all vertices are included in the spanning tree. Below we will introduce step by step how to implement Kruskal's algorithm using C.

Step One: Data Preparation
First, we need to prepare a graph data structure to represent the problem. In C, graphs can be represented using adjacency matrices or adjacency lists. Here we choose to use adjacency lists to represent undirected graphs.

Adjacency lists can be implemented using a combination of vectors and linked lists. We define two structures to represent the vertices and edges of the graph.

// 图的顶点结构体
struct Vertex {
    int id; // 顶点的唯一标识符
    // ...
};

// 图的边结构体
struct Edge {
    int start; // 边的起始顶点
    int end; // 边的结束顶点
    int weight; // 边的权重
    // ...
};

// 定义一个无向图的类
class Graph {
public:
    // 添加顶点和边的函数
    void addVertex(Vertex v);
    void addEdge(Edge e);
    // ...
private:
    // 保存顶点和边的数据结构
    vector<Vertex> vertices;
    list<Edge> edges;
    // ...
};

Step 2: Implement the Kruskal algorithm
After preparing the data structure of the graph, we can start to implement the Kruskal algorithm. First, we need to sort the edges of the graph from small to large in weight. Then, we use Union-Find to determine whether the selected edges will form a cycle. Finally, we add the selected edges to the minimum spanning tree.

The following is the specific implementation code of Kruskal algorithm:

// 定义并查集结构体
struct UnionFind {
    vector<int> parent;
    // ...
};

// 初始化并查集
void initUnionFind(UnionFind& uf, int n) {
    uf.parent.resize(n);
    // ...
}

// 查找根节点
int findRoot(UnionFind& uf, int x) {
    if (uf.parent[x] != x) {
        uf.parent[x] = findRoot(uf, uf.parent[x]);
    }
    return uf.parent[x];
}

// 合并两个集合
void mergeSets(UnionFind& uf, int x, int y) {
    int rootX = findRoot(uf, x);
    int rootY = findRoot(uf, y);
    if (rootX != rootY) {
        uf.parent[rootX] = rootY;
    }
}

// Kruskal算法主函数
list<Edge> kruskal(Graph& graph) {
    list<Edge> minSpanningTree;
    // 将图的边按照权重从小到大排序
    graph.edges.sort([](const Edge& e1, const Edge& e2) {
        return e1.weight < e2.weight;
    });

    int numVertices = graph.vertices.size();
    UnionFind uf;
    initUnionFind(uf, numVertices);

    for (const Edge& edge : graph.edges) {
        int startRoot = findRoot(uf, edge.start);
        int endRoot = findRoot(uf, edge.end);
        // 如果两个顶点不在同一个集合中，则添加该边到最小生成树中
        if (startRoot != endRoot) {
            minSpanningTree.push_back(edge);
            mergeSets(uf, startRoot, endRoot);
        }
    }
    
    return minSpanningTree;
}

Step 3: Test code
Write a test function, create a graph and call Kruskal algorithm to output the minimum spanning tree:

void testKruskal() {
    Graph graph;
    // 添加顶点和边
    // ...
    
    list<Edge> minSpanningTree = kruskal(graph);
    // 输出最小生成树
    for (const Edge& edge : minSpanningTree) {
        cout << edge.start << " -> " << edge.end << ", weight: " << edge.weight << endl;
    }
}

int main() {
    testKruskal();
    return 0;
}

The above is a simple example of using C to implement Kruskal's algorithm. Through this example, you can better understand and use Kruskal's algorithm to solve the minimum spanning tree problem.

The above is the detailed content of How to use Kruskal's algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!