最小生成树 -- prim算法以及Kruskal算法实现_实现prim算法以及克鲁斯卡尔算法c语言

最小生成树

基本概念：

最小生成树： 将n个顶点的图联通，最少只需要n - 1条边，构建最小生成树的目的是将各个 顶点连通起来且权值和最小。
子图： 从原图中选中一些顶点和边组成的图，称为原图的子图。
生成子图： 在原图中选中一些边和所有顶点组成的图，称为原图的生成子图
生成树： 如果生成子图恰好是一棵树，则成为生成树（无环路的连通图）
最小生成树： 权值之和最小的生成树，则成为最小生成树

prim算法（避圈法）实现最小生成树

核心思想：
通过选点产生最小生成树。
把已经生成树中的节点看作是一个集合，把剩下的结点看作另一个集合，
从连接两个集合的边中选择一条权值最小的边即可，然后把与该边相关联
的结点加入到生成树集合中，直到生成树集合中的结点树等于图中所有的
结点数量，则选中的边和所有的结点组成的图就是最小生成树。
可以看做是两个集合合并成一个集合，每次我们都选取两个集合相连的最小边权，
那么最终合并这两个集合的边权和一定是最小的。（即从局部最优实现全局最优）
复杂度分析：
时间复杂度： O（n^2）
主要时间复杂度来源于找V-U集合距离U集合最近的点t（最近的边），时间复杂度为O（n^2），以及通过将点t加入U集合后对U到U-V的最近距离clowcost和closest的更新，时间复杂度也为O（n ^ 2），所以总的时间复杂度为O（n^2）
空间复杂度： O（n）
算法需要的辅助空间包含i，j，lowcost和closest，则算法的空间复杂度为O（n）
代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100;
bool s[N];  
//通过一个bool变量去表示顶点i是在集合U中，还是在集合V-U中
//U集合：已经加入最小生成树的结点
//V—U集合：还未加入最小生成树中的结点
//从连接U集合和V-U集合的边中选择一条权值最小的边，然后将与该边
//相关联的结点加入到U集合中
int closest[N]; //表示V——U中的顶点j到集合U中的最邻近点。
int lowcost[N]; //表示V——U中的顶点j到集合U中的最邻近点的边值，即边（j，closest[j]）的权值
int c[N][N];    //通过邻接矩阵来存图信息
void prim(int n, int u0){
    //初始化
    s[u0] = true;   //初始，集合U中只有一个元素，即顶点u0
    
    for(int i = 1; i <= n; i ++){
        if(i != u0) //除u0之外的顶点
        {
            lowcost[i] = c[u0][i];  //u0到其他顶点的权值
            closest[i] = u0;    //最邻近点出初始化为u0
            s[i] = false;   //初始化u0之外的顶点不属于U集合，即属于U——V集合
        }
        else lowcost[i] = 0;    //u0到自身的权值就是0
    }
    //在集合V-U中寻找距离集合U最近的顶点t
    for(int i = 1; i <= n; i ++){
        int tmp = INF;  //默认tmp为最小权值
        int t = u0;
        for(int j = 1; j <= n; j ++)    
        {
            if((!s[j]) && (lowcost[j] < tmp))   //当前结点j在U——V集合中且权值小于tmp
            {
                t = j;
                tmp = lowcost[j];
            }
        }
        if(t == u0)break;   //找不到t，跳出循环
        //更新U到U——V的最近距离clowcost和closest数组
        s[t] = true;    //将t加入到集合U
        for(int j = 1; j <= n; j ++){
            if((!s[j]) && (c[t][j] < lowcost[j]))   //当j在集合U——V中且t到j到边值小于当前最邻近值
            {
                lowcost[j] = c[t][j];   //更新j到最邻近值为t到j到边值
                closest[j] = t; //更新j到最邻近点为t
            }
        }
    }
    
}

int main()
{
    int n, m, u, v, w;
    int u0;
    cout<<"输入结点数n和边数m："<<'\n';
    cin>>n>>m;
    int sumcost = 0;
    memset(c, INF, sizeof(c));  //初始化图的权值都为无穷大（即点与点之间不可到达）
    cout<<"输入结点数u，v和边值w："<<'\n';
    for(int i = 1; i <= m; i ++){
        cin>>u>>v>>w;
        //无向图构边
        c[u][v] = w;
        c[v][u] = w;
    }
    cout<<"输入任一结点u0："<<'\n';  //对于prime算法，从任何点开始结果都是一样的
    cin>>u0;
    //计算最后的lowcost的总和，即为最后要求的最小费用之和
    prim(n, u0);
    cout<<"数组lowcost的内容为："<<'\n';
    for(int i = 1; i <= n; i ++)cout<<lowcost[i]<<' ';
    cout<<'\n';
    for(int i = 1; i <= n; i ++)sumcost +=lowcost[i];
    cout<<"最小的花费是："<<sumcost<<'\n';
    return 0;
}
/*
最小生成树（prim算法/避圈法）
主要思路：
把已经生成树中的节点看作是一个集合，把剩下的结点看作另一个集合，
从连接两个集合的边中选择一条权值最小的边即可，然后把与该边相关联
的结点加入到生成树集合中，直到生成树集合中的结点树等于图中所有的
结点数量，则选中的边和所有的结点组成的图就是最小生成树。

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

运行结果：

Kruskal算法实现最小生成树

核心思想：
通过选边产生最小生成树。
将n个顶点看作是n个孤立的连通分支，将所有的边的权值从小到达排序，因为n个点
的最小生成树需要边数为n-1，所以只要没有选中n - 1条边我们就一直循环，选边的
时候要注意加入该边后图不会出现环路。
如果做到避圈呢？
如果选择加入的边的起点和终点都是在T集合中，那么就可以断定一定会形成回路（圈）。
其实这就是我们之前提到的避圈法：边的两个结点不能属于同一集合。
复杂度分析：
时间复杂度： O（n^2）
首先要对边进行快速排序，我们通过STL中是sort函数实现，所以时间复杂度消耗为O（nlogn）。对于合并集合需要n-1次合并，每次合并需要O（n）时间复杂度，，所以合并集合的时间复杂度为O（n^{2），所以总的时间复杂度为O（n}2）
空间复杂度： O（n）
算法所需要的辅助空间包含集合号数组nodeset[n],则算法空间复杂度为O（n）
空间复杂度： O（n）
算法需要的辅助空间包含i，j，lowcost和closest，则算法的空间复杂度为O（n）
代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 105;
int nodeset[N]; //集合号数组
int n, m;
struct Edge //存储边的信息的结构体
{
    //两个顶点 u， v
    int u;  
    int v;
    //该边的权值
    int w;
}e[N * N];

// 自定义所有的边按照权值的大小从小到大排序
bool cmp（Edge x, Edge y){
    return x.w < y.w;
}
//初始化，给每一个结点赋值一个集合号
void Init(int n){
    for(int i = 1; i <= n; i ++)nodeset[i] = i;
}
//合并集合
int Merge(int a, int b){
    int p = nodeset[a]; //p为a结点的集合号
    int q = nodeset[b]; //q为b结点的集合号
    if(p == q)return 0; //集合号相同，即表示什么也不做，返回
    for(int i = 1; i <= n; i ++)    //检查所有结点，把集合号是q的全部改成p
    {
        if(nodeset[i] == q)nodeset[i] = p;  //a的集合号付给b集合号
    }
    return 1;
}
int Kruskal(int n){
    int ans = 0;
    for(int i = 0; i < m; i ++){
        if(Merge(e[i].u, e[i].v))
        {
            ans += e[i].w;
            n--;
            if(n == 1)return ans;
        }
    }
    return 0;
}

int main()
{
    cout << "输入结点数n和边数m："<<'\n';
    cin>>n>>m;
    Init(n);
    cout<<"输入结点数u，v和边值w："<<'\n';
    for(int i = 0; i < m; i ++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e, e + m, cmp);
    int ans = Kruskal(n);
    cout<<"最小话费数"<<ans<<'\n';
       
    
    return 0;
}
/*

最小生成树（Kruskal算法）
通过选边产生最小生成树
将n个顶点看作是n个孤立的连通分支，将所有的边的权值从小到达排序，因为n个点
的最小生成树需要边数为n-1，所以只要没有选中n - 1条边我们就一直循环，选边的
时候要注意加入该边后图不会出现环路。
如果做到避圈呢？
如果选择加入的边的起点和终点都是在T集合中，那么就可以断定一定会形成回路（圈）。
其实这就是我们之前提到的避圈法：边的两个结点不能属于同一集合。

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

运行结果：

Kruskal算法通过并查集优化

我们对上述算法的时间复杂度主要消耗在了合并集合上，其时间复杂度是O（n^2），这里我们如果用并查集算法优化一下，可以使合并集合的时间复杂度降到O（n），这样就可以让算法的整体时间复杂度降到O（nlogn）
我们只需要加一个并查集的函数和修改一下集合合并的函数即可，其他内容如上述一样不变：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 105;
int nodeset[N]; //集合号数组
int n, m;
struct Edge //存储边的信息的结构体
{
    //两个顶点 u， v
    int u;  
    int v;
    //该边的权值
    int w;
}e[N * N];

// 自定义所有的边按照权值的大小从小到大排序
bool cmp(Edge x, Edge y){
    return x.w < y.w;
}
//初始化，给每一个结点赋值一个集合号
void Init(int n){
    for(int i = 1; i <= n; i ++)nodeset[i] = i;
}

//查找x的祖宗结点
int find(int x){
    if(nodeset[x]!=x)nodeset[x]=find(nodeset[x]);//表示当前这个数不是祖宗结点
    return nodeset[x];//找到祖宗结点返回
}

//合并集合
int Merge(int a, int b){
    int p = find(a); //p为a结点的集合号
    int q = find(b); //q为b结点的集合号
    if(p == q)return 0; //集合号相同，即表示什么也不做，返回
    if(p > q)nodeset[p] = q;    //小的集合号赋给大的集合号
    else nodeset[q] = p;    
    return 1;
}
int Kruskal(int n){
    int ans = 0;
    for(int i = 0; i < m; i ++){
        if(Merge(e[i].u, e[i].v))
        {
            ans += e[i].w;
            n--;
            if(n == 1)return ans;
        }
    }
    return 0;
}

int main()
{
    cout << "输入结点数n和边数m："<<'\n';
    cin>>n>>m;
    Init(n);
    cout<<"输入结点数u，v和边值w："<<'\n';
    for(int i = 0; i < m; i ++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e, e + m, cmp);
    int ans = Kruskal(n);
    cout<<"最小话费数"<<ans<<'\n';
       
    
    return 0;
}
/*

最小生成树（Kruskal算法）
通过选边产生最小生成树
将n个顶点看作是n个孤立的连通分支，将所有的边的权值从小到达排序，因为n个点
的最小生成树需要边数为n-1，所以只要没有选中n - 1条边我们就一直循环，选边的
时候要注意加入该边后图不会出现环路。
如果做到避圈呢？
如果选择加入的边的起点和终点都是在T集合中，那么就可以断定一定会形成回路（圈）。
其实这就是我们之前提到的避圈法：边的两个结点不能属于同一集合。

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

对两种算法的比较：
因为Kruskal算法是通过选边来构建最小生成树的，所以它适合点多变少的图（即稀疏图）。而prim算法是通过选点来构建最小生成树的，所以它适合点少变多的图（即稠密图）