算法之最小生成樹(shù)

最小生成樹(shù)

概念：

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

算法：

Prim算法

概念：

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

實(shí)現(xiàn)代碼：

使用優(yōu)先隊(duì)列

void Prim(int v){an[v].dist=0;//使用優(yōu)先隊(duì)列,定義參數(shù)<數(shù)據(jù)類(lèi)型，容器類(lèi)型，比較方法>priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;//pair<int,int>對(duì)組的第一個(gè)為權(quán)，第二個(gè)為頂點(diǎn)。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){//選取最小權(quán)的邊而不是頂點(diǎn)到頂點(diǎn)的最短距離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;     //記錄最小生成樹(shù)的總權(quán)for(int i=1;i<=vnum;i++){if(an[i].path!=0){if(i>an[i].path)cout<<"("<<an[i].path<<","<<i<<")"<<" 權(quán):"<<an[i].dist<<endl;elsecout<<"("<<i<<","<<an[i].path<<")"<<" 權(quán):"<<an[i].dist<<endl;w+=an[i].dist;}}cout<<"總權(quán):"<<w;cout<<endl;}

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

struct edge{int v;    //頂點(diǎn)int weight;   //權(quán)
};
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){//選取最小權(quán)的邊而不是頂點(diǎn)到頂點(diǎn)的最短距離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;     //記錄最小生成樹(shù)的總權(quán)for(int i=1;i<=vnum;i++){if(an[i].path!=0){if(i>an[i].path)cout<<"("<<an[i].path<<","<<i<<")"<<" 權(quán):"<<an[i].dist<<endl;elsecout<<"("<<i<<","<<an[i].path<<")"<<" 權(quán):"<<an[i].dist<<endl;w+=an[i].dist;}}cout<<"總權(quán):"<<w;cout<<endl;}

Kruskal算法

概念：

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

并查集

• 并：合并，查：查詢(xún)連通關(guān)系，集：形成集合，用于處理連通性問(wèn)題。

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

1. 查找兩個(gè)元素是否屬于同一集合：所在樹(shù)的根結(jié)點(diǎn)是否相同

2. 合并兩個(gè)集合——將一個(gè)集合的根結(jié)點(diǎn)作為另一個(gè)集合根結(jié)點(diǎn)的孩子

具體操作：

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

實(shí)現(xiàn)代碼：

struct edge{int u,v,w;  //u，v為頂點(diǎn)的，w為權(quán)重,u為起始點(diǎn)，v為終點(diǎn)
};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é)點(diǎn)。t=parent[t];}return t;}void Kruskal(int v){vector<edge>q;//存儲(chǔ)每個(gè)連通變量的父親節(jié)點(diǎn)的數(shù)組int parent[vnum+1];int w=0;     //記錄最小生成樹(shù)的總權(quán)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;}}//進(jìn)行排序?qū)⒆钚?quán)邊放入第一位。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é)點(diǎn)是否相等--判斷是否在一個(gè)集合.if(v1!=v2){cout<<"("<<q[i].u<<","<<q[i].v<<")"<<" 權(quán):"<<q[i].w<<endl;w+=q[i].w;parent[v2]=v1;    //合并集合。num++;}}cout<<"總權(quán):"<<w;cout<<endl;}

尾言

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

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