算法之最小生成樹

最小生成樹

概念：

• 最小生成樹是一顆連接圖G所有頂點的邊構成的一顆權最小的樹，最小生成樹一般是在無向圖中尋找。
• 最小生成樹共有N-1條邊(N為頂點數(shù))。

算法：

Prim算法

概念：

• Prim(普里姆)算法是生成最小生成樹的一種算法，該算法基本上和求最短路徑的Dijkstra算法一樣
• 具體操作：選取一個頂點作為樹的根節(jié)點v1，然后從這個頂點發(fā)散，找到其鄰接頂點(加入隊列中)，然后選取根節(jié)點到鄰接頂點中權最小的路徑(也就是連接該路徑的另一個頂點)進行添加到樹中(也將連接的頂點除去v1的頂點的鄰接頂點加入隊列中)，然后初步形成一個圖為u，然后再按順序的查找圖u與隊列中的頂點的最小路徑并加入樹中，重復操作。
• 最小生成樹信息打印，打印樹中邊的頂點對組。

實現(xiàn)代碼：

使用優(yōu)先隊列

void Prim(int v){an[v].dist=0;//使用優(yōu)先隊列,定義參數(shù)<數(shù)據(jù)類型，容器類型，比較方法>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;elsecout<<"("<<i<<","<<an[i].path<<")"<<" 權:"<<an[i].dist<<endl;w+=an[i].dist;}}cout<<"總權:"<<w;cout<<endl;}

使用vector容器模擬優(yōu)先隊列

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;elsecout<<"("<<i<<","<<an[i].path<<")"<<" 權:"<<an[i].dist<<endl;w+=an[i].dist;}}cout<<"總權:"<<w;cout<<endl;}

Kruskal算法

概念：

• Kruskal(克魯斯卡爾)算法是連續(xù)地按照最小的權選擇邊，并且當所選的邊不產(chǎn)生圈時就把它作為最小生成樹中的邊。
• 該算法是在處理一個森林–樹的集合。開始的時候，存在|V|棵單節(jié)點樹，而添加一邊則將兩棵樹合并成一顆樹。當算法終止時，就只有一棵樹，就是最小生成樹。

并查集

• 并：合并，查：查詢連通關系，集：形成集合，用于處理連通性問題。

• 并查集：集合中的元素組織成樹的形式：

1. 查找兩個元素是否屬于同一集合：所在樹的根結點是否相同

2. 合并兩個集合——將一個集合的根結點作為另一個集合根結點的孩子

具體操作：

• 該算法是根據(jù)選取邊來進行生成最小生成樹，那么我們就將圖的信息用一個邊集結構表示，我們需要進行一個循環(huán)，循環(huán)條件就是當最小生成樹的邊達到N-1條時就退出(N為元素個數(shù))，每次循環(huán)我們都需要選取最小權重的邊，并且判斷在樹中加入這條邊會不會形成圈，如果形成圈就不進行加入，直到樹的邊條數(shù)達到N-1就形成了最小生成樹。
• 該算法的關鍵是判斷在樹中加入邊會不會形成圈–也就是判斷兩個頂點是否位于兩個連通分量，這就需要并查集的操作：在圖中我們將每個頂點都當作一個集合，我們插入邊的時候，直接判斷這兩個頂點是否處于一個集合中，如何是一個集合就不進行加入，如果不是一個集合，就需要將兩個集合進行合并，那么這就需要一個存儲每個節(jié)點的根(父親)節(jié)點的數(shù)組parent。我們將parent每個連通分量(集合)進行初始化為-1，表示沒有父親。

實現(xiàn)代碼：

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){    //查找該集合的根節(jié)點。t=parent[t];}return t;}void Kruskal(int v){vector<edge>q;//存儲每個連通變量的父親節(jié)點的數(shù)組int parent[vnum+1];int w=0;     //記錄最小生成樹的總權memset(parent,-1, sizeof(int)*(vnum+1));//生成邊集數(shù)組。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);//判斷祖先節(jié)點是否相等--判斷是否在一個集合.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;}

尾言

完整版筆記也就是數(shù)據(jù)結構與算法專欄完整版可到我的博客進行查看，或者在github庫中自取(包含源代碼)

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