Comment utiliser l'algorithme de Kruskal en C++

Comment utiliser l'algorithme de Kruskal en C++

L'algorithme de Kruskal est un algorithme glouton couramment utilisé pour résoudre le problème de l'arbre couvrant minimum. En programmation en C++, nous pouvons comprendre et utiliser l'algorithme de Kruskal à travers des exemples de code simples.

L'idée de base de l'algorithme de Kruskal est de sélectionner en continu l'arête ayant le plus petit poids d'arête et qui ne forme pas de boucle tant que tous les sommets ne sont pas inclus dans l'arbre couvrant. Ci-dessous, nous présenterons étape par étape comment utiliser C++ pour implémenter l'algorithme de Kruskal.

Étape 1 : Préparation des données
Tout d'abord, nous devons préparer une structure de données graphique pour représenter le problème. En C++, les graphiques peuvent être représentés à l'aide de matrices de contiguïté ou de listes de contiguïté. Ici, nous choisissons d'utiliser des listes de contiguïté pour représenter des graphiques non orientés.

Les listes de contiguïté peuvent être implémentées en utilisant une combinaison de vecteurs et de listes chaînées. Nous définissons deux structures pour représenter les sommets et les arêtes du graphe.

// 图的顶点结构体
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;
    // ...
};

Étape 2 : Implémenter l'algorithme Kruskal
Après avoir préparé la structure des données du graphique, nous pouvons commencer à implémenter l'algorithme Kruskal. Tout d’abord, nous devons trier les bords du graphique de petit à grand en poids. Ensuite, nous utilisons Union-Find pour déterminer si les arêtes sélectionnées formeront un cycle. Enfin, nous ajoutons les arêtes sélectionnées à l'arbre couvrant minimum.

Ce qui suit est le code d'implémentation spécifique de l'algorithme Kruskal :

// 定义并查集结构体
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;
}

Étape 3 : tester le code
Écrivez une fonction de test, créez un graphique et appelez l'algorithme Kruskal, et affichez l'arbre couvrant minimum :

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;
}

Ce qui précède est l'implémentation de l'algorithme Kruskal en utilisant C++ Un exemple simple. Grâce à cet exemple, vous pouvez mieux comprendre et utiliser l'algorithme de Kruskal pour résoudre le problème de l'arbre couvrant minimum.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!