Implémentation d'un arbre couvrant minimum en langage C

1. Introduction à l'arbre couvrant minimum

Qu'est-ce que l'arbre couvrant minimum ?

L'arbre couvrant minimum (MST) consiste à trouver un arbre T dans un graphe non orienté donné G(V,E), tel que cet arbre ait tous les sommets du graphe G, et que toutes les arêtes proviennent des arêtes. dans le graphique G, et satisfont la somme minimale des poids de bord de l'arbre entier.

L'algorithme 2.prim

est très similaire à l'algorithme de Dijkstra ! ! Veuillez regarder le diagramme Gif suivant. L'idée principale de l'algorithme prim est de définir un ensemble S pour le graphe G (V, E), de stocker les sommets visités, puis de sélectionner le sommet avec la plus petite distance la plus courte du sommet. définissez S à chaque fois à partir de l'ensemble V-S (noté u), accédez et rejoignez l'ensemble S. Ensuite, laissez le sommet u être le milieu et optimisez la distance la plus courte entre tous les sommets v pouvant être atteints depuis u et l'ensemble s. Cette opération est effectuée n fois jusqu'à ce que l'ensemble s contienne tous les sommets.

La différence est que dist dans l'algorithme de Dijkstra est le chemin le plus court du point source s au sommet w tandis que dist dans l'algorithme de prim va de l'ensemble S au sommet w ; , ce qui suit est une comparaison de leurs descriptions de pseudocode. Pour une description détaillée de l'algorithme de Dijkstra, veuillez vous référer à l'article

Implémentation de l'algorithme :

#include<iostream>
#include<vector>
#define INF 100000
#define MaxVertex 105
typedef int Vertex; 
int G[MaxVertex][MaxVertex];
int parent[MaxVertex];   // 并查集 
int dist[MaxVertex]; // 距离 
int Nv;    // 结点 
int Ne;    // 边 
int sum;  // 权重和 
using namespace std; 
vector<Vertex> MST;  // 最小生成树 
// 初始化图信息 
void build(){
    Vertex v1,v2;
    int w;
    cin>>Nv>>Ne;
    for(int i=1;i<=Nv;i++){
        for(int j=1;j<=Nv;j++)
            G[i][j] = 0;  // 初始化图 
        dist[i] = INF;   // 初始化距离
        parent[i] = -1;  // 初始化并查集 
    }
    // 初始化点
    for(int i=0;i<Ne;i++){
        cin>>v1>>v2>>w;
        G[v1][v2] = w;
        G[v2][v1] = w;
    }
}
// Prim算法前的初始化 
void IniPrim(Vertex s){
    dist[s] = 0;
    MST.push_back(s);
    for(Vertex i =1;i<=Nv;i++)
        if(G[s][i]){
            dist[i] = G[s][i];
            parent[i] = s;
        } 
}
// 查找未收录中dist最小的点 
Vertex FindMin(){
    int min = INF;
    Vertex xb = -1;
    for(Vertex i=1;i<=Nv;i++)
        if(dist[i] && dist[i] < min){ 
            min = dist[i];
            xb = i;
        }
    return xb;
}
void output(){
    cout<<"被收录顺序："<<endl; 
    for(Vertex i=1;i<=Nv;i++)
        cout<<MST[i]<<" ";
    cout<<"权重和为："<<sum<<endl; 
    cout<<"该生成树为："<<endl; 
    for(Vertex i=1;i<=Nv;i++)
        cout<<parent[i]<<" ";
}
void Prim(Vertex s){
    IniPrim(s);
    while(1){
        Vertex v = FindMin();
        if(v == -1)
            break;
        sum += dist[v];
        dist[v] = 0;
        MST.push_back(v);
        for(Vertex w=1;w<=Nv;w++)
            if(G[v][w] && dist[w])
                if(G[v][w] < dist[w]){
                    dist[w] = G[v][w];
                    parent[w] = v;
                }
    }
}
int main(){
    build();
    Prim(1);
    output();
    return 0;
}

. À propos de l'algorithme prim Pour une explication plus détaillée, veuillez vous référer à la vidéo https://www.bilibili.com/video/av55114968?p=99

Algorithme 3.kruskal

L'algorithme de Kruskal peut également être utilisé. Pour résoudre le problème de l'arbre couvrant minimum, l'idée de l'algorithme est facile à comprendre. L'idée de l'algorithme est typique des arêtes gourmandes, l'idée de l'algorithme est :

● Masquer toutes les arêtes du graphique. dans l'état initial, de sorte que chaque sommet du graphique soit un seul bloc connecté, et il y a n blocs connectés au total

● Trier toutes les arêtes en fonction du poids de l'arête, de petit à grand

● Testez toutes les arêtes en fonction du poids de l'arête, de petit à grand, si si les deux sommets connectés par l'arête de test actuelle ne sont pas dans le même bloc connecté, alors l'arête de test est ajoutée à l'arbre couvrant minimum actuel, sinon l'arête est rejeté.

● Répétez l'étape précédente jusqu'à ce que le nombre d'arêtes dans l'arbre couvrant minimum soit égal au nombre total de sommets moins un ou qu'elle se termine lorsque toutes les arêtes sont testées si à la fin, le nombre d'arêtes dans ; l'arbre couvrant minimum est inférieur au nombre total de sommets moins un 1, indiquant que le graphe n'est pas connecté.

Veuillez consulter le Gif ci-dessous !

Implémentation de l'algorithme :

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#define INF 100000
#define MaxVertex 105
typedef int Vertex; 
int G[MaxVertex][MaxVertex];
int parent[MaxVertex];   // 并查集最小生成树 
int Nv;    // 结点 
int Ne;    // 边 
int sum;  // 权重和 
using namespace std; 
struct Node{
    Vertex v1;
    Vertex v2;
    int weight; // 权重 
    // 重载运算符成最大堆 
    bool operator < (const Node &a) const
    {
        return weight>a.weight;
    }
};
vector<Node> MST;  // 最小生成树 
priority_queue<Node> q;   // 最小堆 
// 初始化图信息 
void build(){
    Vertex v1,v2;
    int w;
    cin>>Nv>>Ne;
    for(int i=1;i<=Nv;i++){
        for(int j=1;j<=Nv;j++)
            G[i][j] = 0;  // 初始化图
        parent[i] = -1;
    }
    // 初始化点
    for(int i=0;i<Ne;i++){
        cin>>v1>>v2>>w;
        struct Node tmpE;
        tmpE.v1 = v1;
        tmpE.v2 = v2;
        tmpE.weight = w;
        q.push(tmpE); 
    }
}
//  路径压缩查找 
int Find(int x){
    if(parent[x] < 0)
        return x;
    else
        return parent[x] = Find(parent[x]);
} 
//  按秩归并 
void Union(int x1,int x2){
    if(parent[x1] < parent[x2]){
        parent[x1] += parent[x2];
        parent[x2] = x1;
    }else{
        parent[x2] += parent[x1];
        parent[x1] = x2;
    }
} 
void Kruskal(){
    // 最小生成树的边不到 Nv-1 条且还有边 
    while(MST.size()!= Nv-1 && !q.empty()){
        Node E = q.top();  // 从最小堆取出一条权重最小的边
        q.pop(); // 出队这条边 
        if(Find(E.v1) != Find(E.v2)){  // 检测两条边是否在同一集合 
            sum += E.weight; 
            Union(E.v1,E.v2);     // 并起来 
            MST.push_back(E);
        }
    }
    
} 
void output(){
    cout<<"被收录顺序："<<endl; 
    for(Vertex i=0;i<Nv;i++)
        cout<<MST[i].weight<<" ";
    cout<<"权重和为："<<sum<<endl; 
    for(Vertex i=1;i<=Nv;i++)
        cout<<parent[i]<<" ";
    cout<<endl;
}
int main(){
    build();
    Kruskal();
    output();
    return 0;
}

Pour une explication plus détaillée de l'algorithme Kruskal, veuillez vous référer à la vidéo https://www.bilibili.com/ video/av55114968?p =100

Cours recommandés : Tutoriel du langage C

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!