圖算法小結(jié)(并查集)

（0）目錄

圖算法小結(jié)(prime與dijkstra對(duì)照)

圖算法小結(jié)(并查集)

哈夫曼樹(shù) 之 建樹(shù)和編解碼

1：起因

（1）關(guān)于圖的算法1般是比較復(fù)雜的，自己在這方面也是比較弱的，首先是圖的存儲(chǔ)問(wèn)題 和 遍歷問(wèn)題：

存儲(chǔ)分為兩種，鄰接矩陣 和 臨街表；遍歷分為DFS 和 BFS兩種，非常類似于2叉樹(shù)的先跟遍歷和層次遍歷。

（2）圖在實(shí)際利用中是非常廣泛的，這與萬(wàn)物歸1，萬(wàn)物相連的理論是1致的，兩個(gè)物體之間有著千絲萬(wàn)縷的聯(lián)系，我們成這類聯(lián)系建立的網(wǎng)絡(luò)為圖（帶權(quán)圖）；聯(lián)系的強(qiáng)弱為邊的權(quán)重。

（3）圖的1些復(fù)雜的算法，也是建立在兩種遍歷圖的思想的基礎(chǔ)上進(jìn)行的，所以我們先從簡(jiǎn)單的談起。

（4）圖的相干知識(shí)：

圖的定義：
       很簡(jiǎn)單，G(V,E)， V、E分別表示點(diǎn)和邊的集合。       

圖的表示：
       主要有兩種，鄰接矩陣和鄰接表，前者空間復(fù)雜度，O(V2），后者為O(V+E)。因此，除非非常稠密的圖(邊非常多），1般后者優(yōu)越于前者。

圖的遍歷：
       寬度遍歷BFS(start):    (1) 隊(duì)列Q=Empty，數(shù)組bool visited[V]={false...}. Q.push(start);
                                             (2) while (!Q.empty()){
                                                       u = Q.pop();  visited[u] = true;   //遍歷u結(jié)點(diǎn)
                                                       foreach (u的每個(gè)鄰接結(jié)點(diǎn)v) Q.push(v);
                                                    }   
       深度遍歷DFS(start):     (1) 棧S=Empty, 數(shù)組bool visited[V]={false...}. S.push(start);
                                               (2) while (!S.empty()){
                                                       u = S.pop();
                                                       if (!visited[u]) visited[u] = true;   //遍歷u結(jié)點(diǎn)
                                                       foreach (u的每個(gè)鄰接結(jié)點(diǎn)v) S.push(v);
                                                    }
      兩個(gè)算法很相似，主要區(qū)分在于1個(gè)使用隊(duì)列，1個(gè)使用棧。隊(duì)列是先入先出，所以訪問(wèn)u以后接下來(lái)就訪問(wèn)u中未訪問(wèn)過(guò)的鄰接結(jié)點(diǎn)；而棧的落后先出，當(dāng)訪問(wèn)u后，壓入了u的鄰接結(jié)點(diǎn)，在后面的循環(huán)中，首先訪問(wèn)u的第1個(gè)臨接點(diǎn)v，接下來(lái)又將v的鄰接點(diǎn)w壓入S，這樣接下來(lái)要訪問(wèn)的自然是w了。

最小生成樹(shù)：
       (1)Prime算法:    (1) 集合MST=T=Empty，選取G中1結(jié)點(diǎn)u，T.add(u)
                                  (2) 循環(huán)|V|⑴次：
                                        選取1條這樣的邊e=min{(x,y) | x in T, y in V/T}
                                        T.add(y); MST.add(e);
                                  (3) MST即為所求
       (2) Kruskal算法   (1) 將G中所有的邊排序并放入集合H中，初始化集合MST=Empty,初始化不相交集合T={{v1}, {v2}...}}，也即T中每一個(gè)點(diǎn)為1個(gè)集合。
                                    (2)  順次取H中的最短邊e(u,v)，如果Find-Set(u)!=Find-Set(v)（也即u、v是不是已在1棵樹(shù)中），那末Union(u,v) （即u,v合并為1個(gè)集合)，MST.add(e);
                                    (3) MST即為所求

       這兩個(gè)算法都是貪心算法，區(qū)分在于每次選取邊的策略。證明該算法的關(guān)鍵在于1點(diǎn)：如果MST是圖G的最小生成樹(shù)，那末在子圖G'中包括的子生成樹(shù)MST' 也必定是G'的最小生成樹(shù)。這個(gè)很容易反正，假定不成立，那末G'有1棵權(quán)重和更小的生成樹(shù)，用它替換掉MST'，那末對(duì)G我們就找到了比MST更小的生成樹(shù)，明顯這與我們的假定(MST是最小生成樹(shù))矛盾了。
       理解了這個(gè)關(guān)鍵點(diǎn)，算法的正確性就好理解多了。對(duì)Prime，T于V/T兩個(gè)點(diǎn)集都會(huì)各自有1棵生成樹(shù)，最后要連起來(lái)構(gòu)成1棵大的生成樹(shù)，那末明顯要選二者之間的最短的那條邊了。對(duì)Kruskal算法，如果當(dāng)前選取的邊沒(méi)有引發(fā)環(huán)路，那末正確性是明顯的（對(duì)給定點(diǎn)集順次選最小的邊構(gòu)成1棵樹(shù)固然是最小生成樹(shù)了），如果致使了環(huán)路，那末說(shuō)明兩個(gè)點(diǎn)都在該點(diǎn)集里，由于已構(gòu)成了樹(shù)（否則也不可能致使環(huán)路）并且1直都是挑盡量小的，所以肯定是最小生成樹(shù)。

最短路徑:
       這里的算法基本是基于動(dòng)態(tài)計(jì)劃和貪心算法的，經(jīng)典算法有很多個(gè)，主要區(qū)分在于：有的是通用的，有的是針對(duì)某1類圖的，例如，無(wú)負(fù)環(huán)的圖，或無(wú)負(fù)權(quán)邊的圖等。
       單源最短路徑（1） 通用（Bellman-Ford算法）：
                               （2） 無(wú)負(fù)權(quán)邊的圖(Dijkstra算法)：
                               （3） 無(wú)環(huán)有向圖(DAG) ：
       所有結(jié)點(diǎn)間最短路徑：
                               （1） Floyd-Warshall算法：
                               （2） Johnson算法：

關(guān)鍵路徑 和 拓?fù)渑判?

2：代碼示例

（1）最簡(jiǎn)單的圖的遍歷問(wèn)題

Lake Counting

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
Sample Output

3

要求輸出圖中連通分支的個(gè)數(shù)，最簡(jiǎn)單的圖遍歷問(wèn)題。

圖的常見(jiàn)遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷，他們的作用是將圖中的每一個(gè)點(diǎn)都訪問(wèn)1遍，只不過(guò)是順序不同。

如果把圖中的每條邊長(zhǎng)都相等（比如都是1）的話，深度優(yōu)先遍歷進(jìn)程就是盡量深的去訪問(wèn)節(jié)點(diǎn)，具體進(jìn)程為：

1.任意選定1個(gè)點(diǎn)p0作為遍歷的出發(fā)點(diǎn)

2.當(dāng)訪問(wèn)到某1個(gè)節(jié)點(diǎn)p1時(shí)，如果p1下面有未被遍歷的子節(jié)點(diǎn)，我們就接著訪問(wèn)p1的某1個(gè)未被遍歷子節(jié)點(diǎn)，并標(biāo)記該子節(jié)點(diǎn)被訪問(wèn)過(guò)，

3.如果p1不存在未被訪問(wèn)的子節(jié)點(diǎn)，我們就退回到p1的父節(jié)點(diǎn)，并履行第2步

4.履行第2、3步，直到所有節(jié)點(diǎn)被訪問(wèn)過(guò)。

大家也看出來(lái)了，深度優(yōu)先遍歷的是1個(gè)遞歸的進(jìn)程，因此很容易想到要用到棧這類數(shù)據(jù)結(jié)構(gòu)，具體實(shí)現(xiàn)的時(shí)候可以用遞歸，也能夠用棧。看個(gè)人習(xí)慣了。
廣度優(yōu)先遍歷實(shí)現(xiàn)就要用到隊(duì)列了。以下是poj2386不同實(shí)現(xiàn)方式的代碼

（2）最小生成樹(shù) ---- prime實(shí)現(xiàn) O(N2)

題意：北極有1些村落，現(xiàn)需要在這些村落間建立起通訊，有s個(gè)衛(wèi)星頻道，任何兩個(gè)具有衛(wèi)星頻道的村落都可以直接通過(guò)衛(wèi)星進(jìn)行通訊而疏忽距離，沒(méi)有衛(wèi)星的村落通過(guò)無(wú)線電進(jìn)行通訊，并且這兩個(gè)村落的距離不能超過(guò)D，D值取決于無(wú)線電收發(fā)器的功率，功率越大，D值越大，但價(jià)格也越高，出于購(gòu)買(mǎi)費(fèi)用和保護(hù)費(fèi)用的斟酌，所有村落的無(wú)線電收發(fā)器都相同，即D值相同，現(xiàn)要求在保證任意兩個(gè)村落間都能直接或間接通訊，并且D值最小，輸出這個(gè)最小值。就是輸出最小生成樹(shù)最大邊的權(quán)值，但是衛(wèi)星頻道是不肯定因素。這道題有個(gè)很好的解法及證明。
其實(shí)題目意思是將1棵最小生成樹(shù)轉(zhuǎn)化成1個(gè)森林，森林里有S棵樹(shù)，每棵樹(shù)配1個(gè)衛(wèi)星頻道，并且使得森林里所有邊中最長(zhǎng)的邊的長(zhǎng)度最小
其實(shí)意思就是可以刪除最小生成樹(shù)中的S⑴條邊，問(wèn)剩下的邊中最長(zhǎng)的是多少
由于建圖時(shí)每?jī)蓚€(gè)點(diǎn)之間都有邊，是稠密圖，故用Prim法比較好 ---- 有的題目也略微復(fù)雜1點(diǎn)，首先得判斷是不是聯(lián)通，再求最小生成樹(shù)

#include <iostream> #include<cmath> #include<algorithm> using namespace std; const int INF = 1000000; const int MAX_SIZE = 501; double map[MAX_SIZE][MAX_SIZE]; double path[MAX_SIZE]; struct node { int x; int y; }point[MAX_SIZE]; //記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義 struct { int adjvex; double lowcost; }closedge[MAX_SIZE]; bool cmp(double a,double b)//從大到小偏序 { return a>b; } // 求距離 inline double CalDist(struct node &a, struct node &b) { double xx = (a.x-b.x); double yy = (a.y-b.y); return sqrt(xx*xx + yy*yy); } //用普里姆算法從第k個(gè)頂點(diǎn)動(dòng)身構(gòu)造網(wǎng)G的最小生產(chǎn)樹(shù)T,N個(gè)頂點(diǎn)的圖 void prim(int k,int n) { int i,j; for(j=1;j<=n;j++)//輔助數(shù)組初始化 { if(j!=k) { closedge[j].adjvex=k; closedge[j].lowcost=map[k][j]; } } closedge[k].lowcost=0; //初始，U={u},這里將0作為訪問(wèn)過(guò)的標(biāo)志 int l=0; for(i=1;i<n;i++)//選擇其余n⑴個(gè)頂點(diǎn)，這個(gè)i不無(wú)任何實(shí)際意義，僅僅是選取n⑴個(gè)點(diǎn)，記錄次數(shù)而已 { double min=INF; for(j=1;j<=n;j++)//求出T的下1個(gè)結(jié)點(diǎn)：第k頂點(diǎn)，最小的，不成環(huán)（即未訪問(wèn)過(guò)） { if(closedge[j].lowcost!=0&&min>closedge[j].lowcost) { k=j; min=closedge[j].lowcost; } } closedge[k].lowcost=0; //第k頂點(diǎn)并入U(xiǎn)集 path[l++]=map[k][closedge[k].adjvex]; //保存該邊，要是求最小生成樹(shù)的本錢(qián)，就得改成加和了，要是求最小生成樹(shù)的最大邊權(quán)值，就得比較最大值了 for(j=1;j<=n;j++) //新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊 { if(map[k][j]<closedge[j].lowcost) { closedge[j].adjvex=k; closedge[j].lowcost=map[k][j]; } }// end of for }// end of for } int main() { int t,m,n; int i,j; cin>>t; while(t--) { cin>>m>>n; // input for(i=1;i<=n;i++) { cin>>point[i].x>>point[i].y; } // init dist for(i=1;i<=n;i++) //求出

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)