最小生成树(算法篇)

算法之最小生成树

最小生成树

概念：

• 最小生成树是一颗连接图G所有顶点的边构成的一颗权最小的树，最小生成树一般是在无向图中寻找。
• 最小生成树共有N-1条边(N为顶点数)。

算法：

Prim算法

概念：

• Prim(普里姆)算法是生成最小生成树的一种算法，该算法基本上和求最短路径的Dijkstra算法一样
• 具体操作：选取一个顶点作为树的根节点v1，然后从这个顶点发散，找到其邻接顶点(加入队列中)，然后选取根节点到邻接顶点中权最小的路径(也就是连接该路径的另一个顶点)进行添加到树中(也将连接的顶点除去v1的顶点的邻接顶点加入队列中)，然后初步形成一个图为u，然后再按顺序的查找图u与队列中的顶点的最小路径并加入树中，重复操作。
• 最小生成树信息打印，打印树中边的顶点对组。

实现代码：

使用优先队列

void Prim(int v){
        an[v].dist=0;
        //使用优先队列,定义参数<数据类型，容器类型，比较方法>
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
        //pair<int,int>对组的第一个为权，第二个为顶点。
        q.push(make_pair(0,v));
        while (!q.empty()){
            int w=q.top().second;
            q.pop();
            listnode* p=an[w].next;
            if(an[w].flag) continue;
            while (p!= nullptr){
                //选取最小权的边而不是顶点到顶点的最短距离
                if(p->weight<an[p->data].dist&&!an[p->data].flag){
                    an[p->data].dist=p->weight;
                    an[p->data].path=w;
                    q.push(make_pair(p->weight,p->data));
                }
                p=p->next;
            }
            an[w].flag= true;
        }
        int w=0;     //记录最小生成树的总权
        for(int i=1;i<=vnum;i++){
            if(an[i].path!=0){
                if(i>an[i].path)
                    cout<<"("<<an[i].path<<","<<i<<")"<<" 权:"<<an[i].dist<<endl;
                else
                    cout<<"("<<i<<","<<an[i].path<<")"<<" 权:"<<an[i].dist<<endl;
                w+=an[i].dist;
            }
        }
        cout<<"总权:"<<w;
        cout<<endl;
    }

使用vector容器模拟优先队列

struct edge{
    int v;    //顶点
    int weight;   //权
};
static bool cmp(const edge &a,const edge &b){
        return b.weight<a.weight;
    }
    void Prim(int v){
        an[v].dist=0;
        vector<edge>q;
        q.push_back({v,0});
        while (!q.empty()){
            sort(q.begin(),q.end(),cmp);
            int w=q.back().v;
            q.pop_back();
            listnode* p=an[w].next;
            if(an[w].flag) continue;
            while (p!= nullptr){
                //选取最小权的边而不是顶点到顶点的最短距离
                if(p->weight<an[p->data].dist&&!an[p->data].flag){
                    an[p->data].dist=p->weight;
                    an[p->data].path=w;
                    q.push_back({p->data,p->weight});
                }
                p=p->next;
            }
            an[w].flag= true;
        }
        int w=0;     //记录最小生成树的总权
        for(int i=1;i<=vnum;i++){
            if(an[i].path!=0){
                if(i>an[i].path)
                    cout<<"("<<an[i].path<<","<<i<<")"<<" 权:"<<an[i].dist<<endl;
                else
                    cout<<"("<<i<<","<<an[i].path<<")"<<" 权:"<<an[i].dist<<endl;
                w+=an[i].dist;
            }
        }
        cout<<"总权:"<<w;
        cout<<endl;
    }

Kruskal算法

概念：

• Kruskal(克鲁斯卡尔)算法是连续地按照最小的权选择边，并且当所选的边不产生圈时就把它作为最小生成树中的边。
• 该算法是在处理一个森林–树的集合。开始的时候，存在|V|棵单节点树，而添加一边则将两棵树合并成一颗树。当算法终止时，就只有一棵树，就是最小生成树。

并查集

• 并：合并，查：查询连通关系，集：形成集合，用于处理连通性问题。

• 并查集：集合中的元素组织成树的形式：

1. 查找两个元素是否属于同一集合：所在树的根结点是否相同

2. 合并两个集合——将一个集合的根结点作为另一个集合根结点的孩子

具体操作：

• 该算法是根据选取边来进行生成最小生成树，那么我们就将图的信息用一个边集结构表示，我们需要进行一个循环，循环条件就是当最小生成树的边达到N-1条时就退出(N为元素个数)，每次循环我们都需要选取最小权重的边，并且判断在树中加入这条边会不会形成圈，如果形成圈就不进行加入，直到树的边条数达到N-1就形成了最小生成树。
• 该算法的关键是判断在树中加入边会不会形成圈–也就是判断两个顶点是否位于两个连通分量，这就需要并查集的操作：在图中我们将每个顶点都当作一个集合，我们插入边的时候，直接判断这两个顶点是否处于一个集合中，如何是一个集合就不进行加入，如果不是一个集合，就需要将两个集合进行合并，那么这就需要一个存储每个节点的根(父亲)节点的数组parent。我们将parent每个连通分量(集合)进行初始化为-1，表示没有父亲。

实现代码：

struct edge{
    int u,v,w;  //u，v为顶点的，w为权重,u为起始点，v为终点
};

static bool cmp(const edge &a,const edge &b){
        return a.w<b.w;
    }
    int findroot(int v,int parent[]){
        int t=v;
        while (parent[t]>-1){    //查找该集合的根节点。
            t=parent[t];
        }
        return t;
    }
    void Kruskal(int v){
        vector<edge>q;
        //存储每个连通变量的父亲节点的数组
        int parent[vnum+1];
        int w=0;     //记录最小生成树的总权
        memset(parent,-1, sizeof(int)*(vnum+1));
        //生成边集数组。
        for(int i=1;i<=vnum;i++) {
            listnode *p = an[i].next;
            while (p != nullptr) {
                if(i<p->data)
                    q.push_back({i, p->data, p->weight});
                p = p->next;
            }
        }
        //进行排序将最小权边放入第一位。
        sort(q.begin(),q.end(), cmp);
        for(int i=0,num=0;num<vnum-1;i++){
            int v1=findroot(q[i].u,parent);
            int v2= findroot(q[i].v,parent);
            //判断祖先节点是否相等--判断是否在一个集合.
            if(v1!=v2){
                cout<<"("<<q[i].u<<","<<q[i].v<<")"<<" 权:"<<q[i].w<<endl;
                w+=q[i].w;
                parent[v2]=v1;    //合并集合。
                num++;
            }
        }
        cout<<"总权:"<<w;
        cout<<endl;
    }

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms