最小生成树MST

定义

在一给定的无向联通带权图\(G = (V, E, W)\)中，\((u, v)\) 代表连接顶点 \(u\) 与顶点 \(v\) 的边，而 \(w(u, v)\) 代表此边的权重，若存在 \(T\) 为 \(E\) 的子集,且为无循环图，使得 \(w(T)\) 最小，则此 \(T\) 为 \(G\) 的最小生成树。

其中\(w(T)=\sum\limits_{(u,v)∈t} w(u,v)\)

由定义易得，\(T\)中的边数为 顶点个数\(-1\)。

实现算法常用\(Kruskal\)和\(Prim\)

Kruskal 算法

将边按权值从小到大排序再依次放入图中，当整个图只有一个连通分量时，程序结束。

实现方法：

• 1.找到\(E\)中最小边
• 2.判断边的两点是否在同一连通分量中
• 3.若在，舍弃此边，转1。
• 4.若不在，添加此边，将端点所在连通分量合并。
• 5.所有边全选完后，若选边数为n-1，则输出解，否则无解处理。

代码：

#include <bits/stdc++.h>
using namespace std;
const int EDG=1000010;
const int VER=100010;
int n,m;
struct edge 
{
    int _start;
    int _end;
    int _weigh;
} arc[EDG];/*结构体存边，便于排序*/ 
bool cmp(edge a,edge b)
{
    return a._weigh<b._weigh;
}
int parent[VER];
inline void init();
inline int find(int x);
int union_(int x,int y);
inline bool search_(int x,int y);

int main()
{
    init();
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>arc[i]._start>>arc[i]._end>>arc[i]._weigh;
    }
    if(m<n-1)//如果不够n-1条边，直接无解 
    {
        cout<<"orz";
        return 0;
    }
    sort(arc+1,arc+1+m,cmp);//权值排序 
    int num=0;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(!search_(arc[i]._start,arc[i]._end))//如果边的端点不在同一个连通分量中 
        {
            ans+=arc[i]._weigh;//选择这条边 
            union_(arc[i]._end,arc[i]._start);//合并两个连通分量 
            num++;//选择的边数 +1 
        }
    }
    if(num==n-1)//最小生成树只可能有n-1条边 
    {
        cout<<ans;
    }
    else cout<<"orz";
}

/*----------并查集相关----------*/
inline void init()
{
    for(int i=0;i<=VER;i++)
    {
        parent[i]=i;
    }
}
inline int find(int x)
{
    int x_root=x;
    while(x_root!=parent[x_root])
    {
        x_root=parent[x_root];
    }
    while(x!=x_root)
    {
        int tmp=parent[x];
        parent[x]=x_root;
        x=tmp;
    }
    return x_root;
}
int union_(int x,int y)
{
    int x_root=find(x);
    int y_root=find(y);
    if(x_root==y_root) return 0;
    parent[x_root]=y_root;
    return 1;
}
inline bool search_(int x,int y)
{
    return find(x)==find(y);
}

Prim 算法

其实就是\(dijksrta\)的变种，配合理解即可

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int edg[1010][1010];
int dis[100010];
int vis[100010];
int n;

void prim()
{
    int sum=0;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=edg[1][i];
    vis[1]=1;
    dis[1]=1;
    for(int i=1;i<n;i++)
    {
        int minn=INF;
        int u;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&minn>dis[j])
            {
                u=j;
                minn=dis[j];
            }
        }
        vis[u]=1;
        sum+=minn;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&edg[u][j]<dis[j])
            {
                dis[j]=edg[u][j];
            }
        }
    }
    cout<<sum;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>edg[i][j];
        }
    }
    prim();
    return 0;
}