hi,你好!欢迎访问本站!登录
本站由简数采集腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 文章 - 后端开发 - 正文 看Cosplay古风插画小姐姐,合集图集打包下载:炫龙网 · 炫龙图库

c言语最小生成树的完成_后端开发

2019-11-30后端开发ki4网42°c
A+ A-

1.最小生成树引见

什么是最小生成树?

最小生成树(Minimum spanning tree,MST)是在一个给定的无向图G(V,E)中求一棵树T,使得这棵树具有图G中的一切极点,且一切边都是来自图G中的边,而且满足整棵树的边权值和最小。

2.prim算法

和Dijkstra算法很像!!请看以下Gif图,prim算法的中心头脑是对图G(V,E)设置鸠合S,寄存已被接见的极点,然后每次从鸠合V-S中挑选与鸠合S的最短间隔最小的一个极点(记为u),接见并到场鸠合S。以后,令极点u为中心点,优化一切从u能抵达的极点v与鸠合s之间的最短间隔。如许的操纵实行n次,直到鸠合s中包括一切极点。

差别的是,Dijkstra算法中的dist是从源点s到极点w的最短途径;而prim算法中的dist是从鸠合S到极点w的最短途径,以下是他们的伪码形貌对照,关于Dijkstra算法的细致形貌请参考文章

算法完成:

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

关于prim算法的越发细致解说请参考视频 https://www.bilibili.com/video/av55114968?p=99

3.kruskal算法

Kruskal算法也能够用来处理最小生成树的问题,其算法头脑很轻易明白,典范的边贪婪,其算法头脑为:

● 在初始状况时隐去图中一切的边,如许图中每一个极点都是一个零丁的连通块,一共有n个连通块

● 对一切边按边权从小到大举行排序

● 按边权从小到大测试一切边,假如当前测试边所衔接的两个极点不在统一个连通块中,则把这条测试边到场当前最小生成树中,不然,将边舍弃。

● 反复实行上一步骤,直到最小生成树中的边数即是总极点数减一 或许测试完一切边时完毕;假如完毕时,最小生成树的边数小于总极点数减一,申明该图不连通。

请看下面的Gif图!

算法完成:

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

关于kruskal算法更细致的解说请参考视频 https://www.bilibili.com/video/av55114968?p=100

引荐课程:C言语教程

以上就是c言语最小生成树的完成的细致内容,更多请关注ki4网别的相干文章!

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  选择分享方式
  移步手机端
c言语最小生成树的完成_后端开发

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
推荐阅读

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>