圖算法小結(并查集)

（0）目錄

圖算法小結(prime與dijkstra對照)

圖算法小結(并查集)

哈夫曼樹 之 建樹和編解碼

1：起因

（1）關于圖的算法1般是比較復雜的，自己在這方面也是比較弱的，首先是圖的存儲問題 和 遍歷問題：

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

（2）圖在實際利用中是非常廣泛的，這與萬物歸1，萬物相連的理論是1致的，兩個物體之間有著千絲萬縷的聯系，我們成這類聯系建立的網絡為圖（帶權圖）；聯系的強弱為邊的權重。

（3）圖的1些復雜的算法，也是建立在兩種遍歷圖的思想的基礎上進行的，所以我們先從簡單的談起。

（4）圖的相干知識：

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

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

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

最小生成樹：
       (1)Prime算法:    (1) 集合MST=T=Empty，選取G中1結點u，T.add(u)
                                  (2) 循環|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中每一個點為1個集合。
                                    (2)  順次取H中的最短邊e(u,v)，如果Find-Set(u)!=Find-Set(v)（也即u、v是不是已在1棵樹中），那末Union(u,v) （即u,v合并為1個集合)，MST.add(e);
                                    (3) MST即為所求

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

最短路徑:
       這里的算法基本是基于動態計劃和貪心算法的，經典算法有很多個，主要區分在于：有的是通用的，有的是針對某1類圖的，例如，無負環的圖，或無負權邊的圖等。
       單源最短路徑（1） 通用（Bellman-Ford算法）：
                               （2） 無負權邊的圖(Dijkstra算法)：
                               （3） 無環有向圖(DAG) ：
       所有結點間最短路徑：
                               （1） Floyd-Warshall算法：
                               （2） Johnson算法：

關鍵路徑 和 拓撲排序:

2：代碼示例

（1）最簡單的圖的遍歷問題

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

要求輸出圖中連通分支的個數，最簡單的圖遍歷問題。

圖的常見遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，他們的作用是將圖中的每一個點都訪問1遍，只不過是順序不同。

如果把圖中的每條邊長都相等（比如都是1）的話，深度優先遍歷進程就是盡量深的去訪問節點，具體進程為：

1.任意選定1個點p0作為遍歷的出發點

2.當訪問到某1個節點p1時，如果p1下面有未被遍歷的子節點，我們就接著訪問p1的某1個未被遍歷子節點，并標記該子節點被訪問過，

3.如果p1不存在未被訪問的子節點，我們就退回到p1的父節點，并履行第2步

4.履行第2、3步，直到所有節點被訪問過。

大家也看出來了，深度優先遍歷的是1個遞歸的進程，因此很容易想到要用到棧這類數據結構，具體實現的時候可以用遞歸，也能夠用棧。看個人習慣了。
廣度優先遍歷實現就要用到隊列了。以下是poj2386不同實現方式的代碼

（2）最小生成樹 ---- prime實現 O(N2)

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

#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]; //記錄從頂點集U到V-U的代價最小的邊的輔助數組定義 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的最小生產樹T,N個頂點的圖 void prim(int k,int n) { int i,j; for(j=1;j<=n;j++)//輔助數組初始化 { if(j!=k) { closedge[j].adjvex=k; closedge[j].lowcost=map[k][j]; } } closedge[k].lowcost=0; //初始，U={u},這里將0作為訪問過的標志 int l=0; for(i=1;i<n;i++)//選擇其余n⑴個頂點，這個i不無任何實際意義，僅僅是選取n⑴個點，記錄次數而已 { double min=INF; for(j=1;j<=n;j++)//求出T的下1個結點：第k頂點，最小的，不成環（即未訪問過） { if(closedge[j].lowcost!=0&&min>closedge[j].lowcost) { k=j; min=closedge[j].lowcost; } } closedge[k].lowcost=0; //第k頂點并入U集 path[l++]=map[k][closedge[k].adjvex]; //保存該邊，要是求最小生成樹的本錢，就得改成加和了，要是求最小生成樹的最大邊權值，就得比較最大值了 for(j=1;j<=n;j++) //新頂點并入U后重新選擇最小邊 { 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++) //求出

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈