最小生成树（克鲁斯卡尔算法 普里姆算法）_最小生成树算法

最小生成树是处理图结构中，简化图的算法；即删除一些边使得图得以简化，但应保证图中任意点都是相连通的。形成的最小生成树应该使得从顶点遍历时走过边的权值和最小。（有n个节点，则最小生成树的边数应为n-1）
如：

变为最小生成树后：

处理最小生成树有两种方法：
1.克鲁斯卡尔算法（kruskal）：
这种算法是先把所有的边拿出来，按其权值从小到大的顺序排列，然后从最小的边开始还原图，即按该边连接其顶点。从权值值最小的边依次连接，每次连接都要判断本次连接是否形成了环，若是，则改变没有必要还原，当还原到已还原边数为n-1时最小生成树完成。


还原步骤：

若形成环则不还原该边。
c++代码参考代码（用到了并查集这是我对并查集的一些理解）：

#include<iostream>
#include<algorithm>
typedef struct//定义边的结构体
{
    int value;
    int node1,node2;
}edge;
#define max_size 20
int parent[20];//用于装节点的根
using namespace std;
int rule(edge a,edge b)//按权值排序边时用
{
    return a.value<b.value;//升序排序
}
int find_root(int v)//找根节点函数
{
    if(parent[v]==-1) return v;
    else
    {
        parent[v]=find_root(parent[v]);//压缩找父节点的路径
        return parent[v];
    }
}
int is_cycle(int v1,int v2)//判断是否成环
{
    int v1_root=find_root(v1);
    int v2_root=find_root(v2);
    if(v1_root==v2_root) return 1;//两个节点的根相同，若在连接两个节点则会形成环
    else
    {
        parent[v1_root]=v2_root;//连接起来，这里最好根据情况 选择把v1或v2的根作为共同的根
        return 0;
    }
}
void kruskal(edge a[],edge b[],int n,int m)
{
    sort(a,a+m,rule);
    for(int i=0,j=0;i<m;i++)
    {
        if(!is_cycle(a[i].node1,a[i].node2))//没有形成环
        {
            b[j].node1=a[i].node1;
            b[j].node2=a[i].node2;
            b[j].value=a[i].value;;
            j++;//统计已还原边数
            if(j==n-1) break;
        }
    }
}
int main()
{
    for(int i=0;i<20;i++)//初始化 节点的父亲
    {
        parent[i]=-1;
    }
    int n,m;
    cin>>n>>m;//输入节点数n，和边数m
    edge arr[m];
    for(int i=0;i<m;i++)//初始化图
    {
        cin>>arr[i].node1>>arr[i].node2>>arr[i].value;
    }
    edge mst[n];//用于装最小生成树
    kruskal(arr,mst,n,m);
    cout<<endl;
    for(int i=0;i<n-1;i++)
    {
        cout<<mst[i].node1<<' '<<mst[i].node2<<' '<<mst[i].value<<endl;
    }
    return 0;
}
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

运行结果：

2.普里姆算法（Prim）：
普里姆算法是从某一端点出发，形成两个集合：已选节点集合，未选节点集合。从已选集合找到一条到未选集合的最小权值边，并把连接的端点划为已选集合。重复这样的操作，直到所有节点都在已选集合时完成操作。
这里讲一下思路：

在代码实现时，在选取某个端点后需要更新到未选节点集合的数值，即从已选节点集合到某个未选节点只有一个值。
步骤如下：
（1）从某个端点出发，把该端点划为已选节点（可以用一个数组来标记哪些是已选节点）。
（2）更新从已选端点到相邻节点的权值，小于之前保存的值时更新（到相邻节点的权值最初的初值为无穷大）。
* 例：赋初值dis[1]=…=dis[6]=inf，inf为无穷大，只要保证大于所有权值即可。如选了v1，则可得到，到v2，v3，v4的权值，它们肯定小于inf，所以更新dis[2]=6,dis[3]=1,dis[4]=5.*
(3)找dis数组中最小值的下标，把改下标划为已选集合，更新dis数组；
例：v1更新完dis后，找到最小值为dis[3],把v3划为已选节点，通过v3，索引未选节点，更新到未选节点的距离，索引v2时：5<6,故dis[2]=5;索引v4时：5<5为假，故不必更新dis[4];索引v5时：6<inf,故dis[5]=6；索引v6时：4<inf,故dis[6]=4；更新完成后找到dis中最小权值的下标，把它划为已选节点，更新dis…重复操作，直到所有节点为已选节点
（4）重复（2）、（3）操作，直到所有的节点都为已选节点时结束。

//数组储存未选集合，每次选到未选集合的最短距离都要遍历数组一遍，有瑕疵
#include<iostream>
#include<vector>//使用向量容器，装相邻节点
using namespace std;
#define max_size 20
#define inf 10000 //表示无穷大
typedef struct
{
    int parent;
    int node;//节点序号
    int value;//从已选节点到该节点的距离（权值）
    int flag;//该节点是否被选，1 已选，0 未选
}node;
typedef struct
{
    int node1;
    int node2;
    int value;
}edge;
vector<int> neighbor[max_size];//装相邻节点
vector<int> value[max_size];//装到相邻节点的权值
int j=0;//用于mst数组下标

void Prim(node a[],edge b[],int n,int v)
{
    a[v].flag=1;
    int i;
    for(i=0;i<neighbor[v].size();i++)//更新到相未选点的距离
    {
        if(value[v][i]<a[neighbor[v][i]].value&&a[neighbor[v][i]].flag==0)
        {
            a[neighbor[v][i]].value=value[v][i];
            a[neighbor[v][i]].parent=v;
        }
    }
    int min_value=inf,p=0;
    for(i=1;i<=n;i++)//找小距离，并选取
    {
        if(min_value>a[i].value&&a[i].flag==0)//找到到未选节点的最小距离
        {
            min_value=a[i].value;
            p=i;//记下所选下标
        }
    }
    if(p==0);//没选取到最小距离，说明所有点都为已选集合，即最小生成树已完成
    else
    {
        b[j].node1=a[p].parent;
        b[j].node2=p;
        b[j].value=min_value;
        j++;
        Prim(a,b,n,p);
    }
}
int main()
{
    node arr[max_size];
    int n,m;
    cin>>n>>m;//输入节点数 n，边数 m
    for(int i=1;i<=n;i++)//初始化节点
    {
        arr[i].flag=0;//初始化为未选
        arr[i].value=inf;//初始化 从已选节点到该节点的距离为无穷大
    }
    int a,b,c;
    for(int i=0;i<m;i++)//输入初始图
    {
        cin>>a>>b>>c;//a b为边的节点，c为权值
        neighbor[a].push_back(b);//把b装入a的邻居
        value[a].push_back(c);//把对应权值装入  a的第i个邻居，对应第i个value值
        neighbor[b].push_back(a);
        value[b].push_back(c);
    }
    edge mst[max_size];//用于装最小生成树
    Prim(arr,mst,n,1);//1号节点开始
    for(int i=0;i<n-1;i++)
    {
        cout<<mst[i].node1<<' '<<mst[i].node2<<' '<<mst[i].value<<endl;
    }
    return 0;
}

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