时间戳

首页 > 技术文章 > 最小生成树

最小生成树

1314cyd 2021-08-25 16:53 原文

　　定义：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的

　所有n 个结点，并且有保持图连通的最少的边。常用kruskal算法或prim算法求解。

 

kruskal算法：

　　前置知识：并查集判环，优先队列。

　　　算法流程：

　　　　1.以每个点为元素建立并查集。

　　　　2.将所有边以边长为主元插入优先队列。

　　　　3.依次取出优先队列中边长最小的边，判断x,y是否在同一个集合

　　　　　　　　是： 跳过。

　　　　　　　　否：将x,y所在集合合并,将该边加入树中。

　　　　4.所有点都处于同一个集合，算法结束。

　　　下面我们证明算法的正确性：

　　　　　　假设上述流程所得到的不是最小生成树，则一定存在一个节点x，满足

　　x->A（A为除了节点x外，剩下的节点的组成的最小生成树）存在一条边U(x->A)

　　小于x->A的最小距离，则U(x->A)必定在当前边之前被取出，与优先队列的性质

　　不符合，假设不成立，可知该算法得到的生成树为这个图的最小生成树。

　　　模板

　　

#include<bits/stdc++.h>
#define N 1000000

using namespace std;

struct node 
{
    int x,y,v;
    bool friend operator <(const node &a,const node &b)
    {
        return a.v>b.v;
    }
}e[N];
int fa[N];
int n,m;
int ans,cut;
priority_queue<node>dl;

int find(int x)
{
    if(fa[x]!=x)return fa[x]=find(fa[x]);
    return fa[x];
}

void kruskal()
{
    while(dl.size())
    {
        node t=dl.top();
        dl.pop();
        int x=t.x,y=t.y,v=t.v;
        int fx=find(x);
        int fy=find(y);
        if(fx==fy)continue;
        fa[fx]=fy;
        e[++cut]=t;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        dl.push({x,y,v});
    }
    
    for(int i=1;i<=n;i++) fa[i]=i;
    kruskal();
    for(int i=1;i<=cut;i++)
        printf("%d %d %d\n",e[i].x,e[i].y,e[i].v);
    return 0;
}

prime算法：

　　摘录于：https://blog.csdn.net/lqcsp/article/details/14118871

　　　　Prime算法的核心步骤是：在带权连通图中V是包含所有顶点的集合，U已

　　经在最小生成树中的节点，从图中任意某一顶点v开始，此时集合U={v}，重复

　　执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，

　　将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，

　　就找到了这颗最小生成树。其实，算法的核心步骤就是：在所有u∈U,w∈V-U

　　的边(u,w)∈E中找到一条权值最小的边。

      　　下面我就用图示法来演示一下工作流程，如图：

　　　　首先，确定起始顶点。我以顶点A作为起始点。根据查找法则，与点A相邻

　　的点有点B和点H，比较AB与AH，我们选择点B，如下图。并将点B加入到U中。

 　　　　继续下一步，此时集合U中有{A,B}两个点，再分别以这两点为起始点，根据

　　查找法则，找到边BC（当有多条边权值相等时，可选任意一条），如下图。并将

　　点C加入到U中。

　　　　继续，此时集合U中有{A,B,C}三个点，根据查找法则，我们找到了符合要求的

　　边CI，如下图。并将点I加入到U中。


　　　　继续，此时集合U中有{A,B,C,I}四个点，根绝查找法则，找到符合要求的边CF，

　　如下图。并将点F加入到集合U中。

　　　　继续，依照查找法则我们找到边FG,如下图。并将点G加入到U中。

 　　　　继续，依照查找法则我们找到边GH,如下图。并将点H加入到U中。

　　　　继续，依照查找法则我们找到边CD,如下图。并将点D加入到U中。

　　　　继续，依照查找法则我们找到边DE,如下图。并将点E加入到U中。

　　　　此时，满足U = V，即找到了这颗最小生成树

#include <algorithm>
const int MAX_V = 100;
const int INF = 1000000;
int cost[MAX_V][MAX_V];//图
int V;
bool path[MAX_V][MAX_V];//记录结果
int res;
bool used[MAX_V];//表示是否访问过
int mincost[MAX_V];//表示到此点消耗值

void Prime()
{
    res = 0;//统计最小消耗
    for (int i = 0;i < V;++i)//初始化
    {
        used[i] = false;
        mincost[i] = INF;
        for (int j = 0;j < V;++j)
        {
            path[i][j] = false;
        }
    }
    mincost[0] = 0;//从0点开始
    int prev = 0;//记录路径
    while (true)
    {
        int visited = -1;
        for (int i = 0;i < V;++i)
        {
            if (!used[i] && (visited == -1 || mincost[i] < mincost[visited])) visited = i;//贪婪寻找最短边
        }
        if (visited == -1) break;
        used[visited] = true;
        if (visited)
        {
            path[prev][visited] = true;
            prev = visited;
        }
        res += mincost[visited];
        for (int i = 0;i < V;++i)
        {
            mincost[i] = std::min(mincost[i], cost[visited][i]);
        }
    }
}

 

 

 

　　　

推荐阅读