連通分支演算法
1. 已知一個無向有限圖的鄰接矩陣，怎麼求這個圖的連通分支數啊
求出Laplace矩陣的秩就可以了，因為0特徵值個個數就是連通分支數。
也可以用類似於最小生成樹的演算法把所有的連通分支都找出來。
2. 為什麼破圈法和避圈法為什麼不能求一點至另一點的最短距離
1.1最小生成樹
最小生成樹：一個有n個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個結點，並且有保持圖連通的最少的邊，如圖1.1.1所示。
圖1.1.1 最小生成樹示意圖
設G = (V, E)是無向連通帶權圖，即一個網路。E中的每一條邊（v, w）的權為W(v, w)。如果G的子圖G』是一棵包含G的所有頂點的樹，則稱G』為G的生成樹。生成樹上各邊權的總和稱為生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。
1.1.1避圈法
避圈法的主要思想就是：開始選一條最小權的邊，以後每一步中，總從與已選邊不構成圈的那些未選邊中，選擇一條權最小的（每一步中，如果有兩條或兩條以上的邊都是權值最小的邊，則從中任選一條）。避圈法主要分為兩種：Prim演算法和Kruskal演算法，下面分別進行介紹。
1.1.1.1 Prim演算法
設G = (V, E)是連通帶權圖，V = {1,2,…,n}。構造G的最小生成樹Prim演算法的基本思想是：首先置S = {1}，然後，只要S是V的真子集，就進行如下的貪心選擇：選取滿足條件i∈S, j∈V – S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S = V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。圖1.1.2顯示了某一帶權圖。最小生成樹的生成過程如下：
→=
c
13;1
→=
c
36;4
32;5
→=
c
c
→=
25;3
最終得到的最小生成樹如圖1.1.3所示。
圖1.1.2 帶權圖G
圖1.1.3 帶權圖G的最小生成樹示意圖
1.1.1.2 Kruskal演算法
給定無向連通帶權圖G = (V, E), V = {1,2,...,n}。Kruskal演算法構造G的最小生成樹的基本思想是：
(1) 將G的n個頂點看成n個孤立的連通分支，並將所有的邊按權從小到大排序；
(2) 從第一條邊開始，依據每條邊的權值遞增的順序檢查每一條邊，並按照下述方法連接兩個不同的連通分支：當查看到第k條邊(v, w)時，如果端點v和w分別是當前兩個不同的連通分支T1和T2的端點時，就用邊(v, w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接查看第k+1條邊，這個過程一個進行到只剩下一個連通分支時為止。此時，已構成G的一棵最小生成樹。
仍以圖1.1.2所示的帶權圖G為例說明其最小生成樹的生成過程，生成過程如下所示：
→=
c
13;1
25;3c →=
36;4c →=
23;5c →=
最終得到的最小生成樹和圖1.1.3所示是一樣的。
1.1.2 破圈法
破圈法可以描述如下：
(1) 如果我們給的連通圖G 中沒有迴路，那麼G 本身就是一棵生成樹；
(2) 若G 中只有一個迴路，則刪去G 的迴路上的一條邊（不刪除結點），則產生的圖仍是連通的且沒有迴路，則得到的子圖就是圖G 的一棵生成樹；
(3) 若G 的迴路不止一個，只要刪去每一個迴路上的一條邊，直到G 的子圖是連通沒有迴路且與圖G 有一樣的結點集，那麼這個子圖就是一棵生成樹。
由於我們破壞迴路的方法可以不一樣，所以可得到不同的生成樹，但是在求最小生成樹的時候，為了保證求得的生成樹的樹權最小，那麼在刪去迴路上的邊的時候，總是在保證帶權圖仍連通的前提下刪掉權值較大的邊，保留權值較小的邊。破圈法就是在帶權圖的迴路中找出權值最大的邊，將該邊去掉，重復這個過程，直到圖連通且沒有圈為止，保留下來的邊所組成的圖即為最小生成樹。下面仍利用圖1.1.2對破圈法進行說明。
首先是去除權值大的邊，並且檢測去除該邊後整個圖是否連通，對於圖1.1.2來說，即第一步去掉權值為6的邊，如圖1.1.4所示。
圖1.1.4 去掉權值為6的G 的示意圖
從圖中可以看出，去掉權值為6的邊後整個圖仍是連通的。所以接下來去除權值為5的邊，並且檢測去除該邊後圖是否連通，結果如圖1.1.5所示。由圖可知，去掉所有權值為5的邊會造成圖G 不連通，因此23;5c →=這條邊是必須保留的。然後再去除權值為4的
邊。由於權值為1、2、3、4的邊分別連接著獨立的節點，故都必須保留，得到的最小生成
圖1.1.5 去掉權值為5的G的示意圖
樹結果與圖1.1.3也是一樣的。
1.1.3避圈法與破圈法比較
Prim演算法是從空圖出發，將點進行二分化，從而逐步加邊得到最小生成樹。它是近似求解演算法，雖然對於大多數最小生成樹問題都能求得最優解，但相當一部分求得的是近似最優解，具體應用時不一定很方便。但是它可以看作是很多種最小樹演算法的概括，在理論上有一定的意義。
Kruskal演算法也是從空圖出發。它是精確演算法，即每次都能求得最優解，但對於規模較大的最小生成樹問題，求解速度較慢。
破圈法是從圖G出發，逐步去邊破圈得到最小生成樹。它最適合在圖上工作，當圖較大時，可以幾個人同時在各個子圖上工作，因此破圈法在實用上是很方便的。
￥
5.9
網路文庫VIP限時優惠現在開通,立享6億+VIP內容
立即獲取
破圈法vs避圈法
1.1最小生成樹
最小生成樹：一個有n個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個結點，並且有保持圖連通的最少的邊，如圖1.1.1所示。
圖1.1.1 最小生成樹示意圖
設G = (V, E)是無向連通帶權圖，即一個網路。E中的每一條邊（v, w）的權為W(v, w)。如果G的子圖G』是一棵包含G的所有頂點的樹，則稱G』為G的生成樹。生成樹上各邊權的總和稱為生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。
第 1 頁
1.1.1避圈法
避圈法的主要思想就是：開始選一條最小權的邊，以後每一步中，總從與已選邊不構成圈的那些未選邊中，選擇一條權最小的（每一步中，如果有兩條或兩條以上的邊都是權值最小的邊，則從中任選一條）。避圈法主要分為兩種：Prim演算法和Kruskal演算法，下面分別進行介紹。
1.1.1.1 Prim演算法
設G = (V, E)是連通帶權圖，V = {1,2,…,n}。構造G的最小生成樹Prim演算法的基本思想是：首先置S = {1}，然後，只要S是V的真子集，就進行如下的貪心選擇：選取滿足條件i∈S, j∈V – S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S = V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。圖1.1.2顯示了某一帶權圖。最小生成樹的生成過程如下：
3. 編程計算無向圖的連通分支數，求助
連通分量 在無向圖中，如果從頂點vi到頂點vj有路徑，則稱vi和vj連通。如果圖中任意兩個頂點之間都連通，則稱該圖為連通圖，否則，將其中的極大連通子圖稱為連通分量。 在有向圖中，如果對於每一對頂點vi和vj，從vi到vj和從vj到vi都有路徑，則稱該圖為強連通圖；否則，將其中的極大連通子圖稱為強連通分量。
追問：
什麼是極大連通子圖呢
回答：
最大連通子圖 也就是把圖的所有結點用最少的邊將其連接起來的子圖，所以極大連通子圖不唯一，也就是因為這個原因可以說最大連通子圖是一個累贅概念，因為任何一個極大連通子圖，其實都可以叫做最大連通子圖，但是一般都不這么叫。
4. 「強連通分支演算法」相關證明
首先,這個演算法求出的是一個有向圖最大強連通子圖.一個圖的最大強連通子圖只有一個解集(這沒什麼疑問吧).
那我只好理解為你要問這個演算法如何求出的這個最大強連通子圖（C）的解集.
首先改變邊方向應該好理解,它能導出一個C。因為一個C裡面的點在邊改變後還是到能在一次深搜搜到的。唯一問題，如何保證不會搜出不是C的點。
這樣的點有兩種情況：在原圖中這個點可以到達這個C但無法通過這個C到達它本身；可以通過C到達，但無法到達C。
第1種情況，這個點的編號肯定比C大，邊變向後，就會先搜這個點，而且不會搜到C。
第2中情況雷同。
建議樓主在實踐中採用求最早祖先的方法求最大強連通。方法也比較好理解，代碼也短 ，只用一遍深搜就行。
希望樓主看完我的回答有所收益
5. 題目1:一個簡單的演算法演示程序(JAVA語言實現)
1. 選擇一個演算法（提供選擇見下），利用各種方法（圖形、動畫等）演示演算法的演示過程。
2. 可以進行手動演示，也可以自動步進式演示。
3. 允許用戶設置演算法的各個輸入參數，以及自動步進式演示中的時間間隔。
4. 不同的演算法輸入要求見下。
界面要求：
1. 盡量使用圖形界面實現，要符合日常軟體使用規范來設計菜單和界面。
2. 如果無法實現圖形界面，則在命令行方式下也需要提供菜單，方便用戶操作。
其他要求：
1. 標識符命名遵循Windows命名規范。
2. 能夠注意各種異常處理，注重提高程序運行效率。
提交內容：
1. 全部源代碼。
2. 軟體設計和使用說明書（UML類圖；實現的功能、主要技術；使用幫助文檔）
參考演算法：
1. 最小生成樹演算法：Prim演算法、Kruskal演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
2. 單源最短路演算法：Dijkstra演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
3. 最優編碼演算法：Huffman編碼演算法。允許用戶輸入一段英文文字，或者打開一個txt文檔（英文內容），據此文檔內容進行編碼。要求動態列出每個字元的出現概率統計結果以及對應編碼。
4. 其他可供演示的具有一定難度的演算法，如關鍵路徑問題、有向圖的極大連通分支等。
6. sparkgraphx的連通分支演算法有什麼作用
連通分支演算法使用最小編號的頂點來標記每個連通分支。在一個社會網路，連通圖近似簇。這里我們計算一個連通分支實例，所使用的數據集和PageRank一樣。
7. 求krusal演算法原理
kruskal演算法構造G的最小生成樹的思想是，首先將G的n個頂點看成是n個孤立的連通分支，將所有的邊按權從小到大排序，然後從第一條邊開始，依邊權遞增的順序查看每一邊，並按下述方法連接兩個不同的連通分支:當查看到第k條邊(v,w)時，如果端點v,w分別是當前兩個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊。這個過程就是G的一棵最小生成樹。
8. 什麼是分支演算法
分支限界演算法：
分支定界 (branch and bound) 演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。
利用分支定界演算法對問題的解空間樹進行搜索，它的搜索策略是：
1 ．產生當前擴展結點的所有孩子結點；
2 ．在產生的孩子結點中，拋棄那些不可能產生可行解（或最優解）的結點；
3 ．將其餘的孩子結點加入活結點表；
4 ．從活結點表中選擇下一個活結點作為新的擴展結點。
如此循環，直到找到問題的可行解（最優解）或活結點表為空。
從活結點表中選擇下一個活結點作為新的擴展結點，根據選擇方式的不同，分支定界演算法通常可以分為兩種形式：
1 ． FIFO(First In First Out) 分支定界演算法：按照先進先出原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。
2 ．最小耗費或最大收益分支定界演算法：在這種情況下，每個結點都有一個耗費或收益。如果要查找一個具有最小耗費的解，那麼要選擇的下一個擴展結點就是活結點表中具有最小耗費的活結點；如果要查找一個具有最大收益的解，那麼要選擇的下一個擴展結點就是活結點表中具有最大收益的活結點。
又稱分支定界搜索法。過程系統綜合的一類方法。該法是將原始問題分解，產生一組子問題。分支是將一組解分為幾組子解，定界是建立這些子組解的目標函數的邊界。如果某一子組的解在這些邊界之外，就將這一子組舍棄（剪枝）。分支定界法原為運籌學中求解整數規劃(或混合整數規劃)問題的一種方法。用該法尋求整數最優解的效率很高。將該法原理用於過程系統綜合可大大減少需要計算的方案數日。
分支定界法的思想是：首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。
在競賽中，我們有時會碰到一些題目，它們既不能通過建立數學模型解決，又沒有現成演算法可以套用，或者非遍歷所有狀況才可以得出正確結果。這時，我們就必須採用搜索演算法來解決問題。
搜索演算法按搜索的方式分有兩類，一類是深度優先搜索，一類是廣度優先搜索。我們知道，深度搜索編程簡單，程序簡潔易懂，空間需求也比較低，但是這種方法的時間復雜度往往是指數級的，倘若不加優化，其時間效率簡直無法忍受；而廣度優先搜索雖然時間復雜度比前者低一些，但其龐大的空間需求量又往往讓人望而卻步。
所以，對程序進行優化，就成為搜索演算法編程中最關鍵的一環。
本文所要討論的便是搜索演算法中優化程序的一種基本方法棗「剪枝」。
什麼是剪枝
相信剛開始接觸搜索演算法的人，都做過類似迷宮這樣的題目吧。我們在「走迷宮」的時候，一般回溯法思路是這樣的：
1、這個方向有路可走，我沒走過
2、往這個方向前進
3、是死胡同，往回走，回到上一個路口
4、重復第一步，直到找著出口
這樣的思路很好理解，編程起來也比較容易。但是當迷宮的規模很大時，回溯法的缺點便暴露無遺：搜索耗時極巨，無法忍受。
我們可不可以在向某個方向前進時，先一步判斷出這樣走會不會走到死胡同里呢？這樣一來，搜索的時間不就可以減少了嗎？
答案是：可以的。
剪枝的概念，其實就跟走迷宮避開死胡同差不多。若我們把搜索的過程看成是對一棵樹的遍歷，那麼剪枝顧名思義，就是將樹中的一些「死胡同」，不能到達我們需要的解的枝條「剪」掉，以減少搜索的時間。
搜索演算法，絕大部分需要用到剪枝。然而，不是所有的枝條都可以剪掉，這就需要通過設計出合理的判斷方法，以決定某一分支的取捨。在設計判斷方法的時候，需要遵循一定的原則。
剪枝的原則
1、正確性
正如上文所述，枝條不是愛剪就能剪的。如果隨便剪枝，把帶有最優解的那一分支也剪掉了的話，剪枝也就失去了意義。所以，剪枝的前提是一定要保證不丟失正確的結果。
2、准確性
在保證了正確性的基礎上，我們應該根據具體問題具體分析，採用合適的判斷手段，使不包含最優解的枝條盡可能多的被剪去，以達到程序「最優化」的目的。可以說，剪枝的准確性，是衡量一個優化演算法好壞的標准。
3、高效性 設計優化程序的根本目的，是要減少搜索的次數，使程序運行的時間減少。但為了使搜索次數盡可能的減少，我們又必須花工夫設計出一個准確性較高的優化演算法，而當演算法的准確性升高，其判斷的次數必定增多，從而又導致耗時的增多，這便引出了矛盾。
因此，如何在優化與效率之間尋找一個平衡點，使得程序的時間復雜度盡可能降低，同樣是非常重要的。倘若一個剪枝的判斷效果非常好，但是它卻需要耗費大量的時間來判斷、比較，結果整個程序運行起來也跟沒有優化過的沒什麼區別，這樣就太得不償失了。
綜上所述，我們可以把剪枝優化的主要原則歸結為六個字：正確、准確、高效。
剪枝演算法按照其判斷思路可大致分成兩類：可行性剪枝及最優性剪枝。
對於分支定界演算法,上界是已求得的可行解的目標函數值中的最小者,分為初始上界和在探測過程中產生的動態上界.分支定界法在求最優解的迭代過程中, 若某結點估計的下界不小於已知的上界, 則不必從該節點往下繼續搜索. 因此若能產生一個較好的上界, 可以消除許多不必要的列舉計算.
分支定界演算法的實現
在描述分支定界演算法步驟之前, 先對演算法涉及到的有關術語進行定義如下:
p —— 分支層數;
C*—— 當前最優目標函數值;
P*—— 相應於C*的工件順序;
P1—— 當前節點(現在需要進行分支的節點)所對應的部分序列.
分支定界演算法的實施步驟如下:
步驟1 初始化: 設置p = 0, P 1 = Á (空集) , C* = ∞.設當前節點總是與P 1 相對應. 此時, 當前節點即根節點.
步驟2 計算從當前節點分支得到的各個子節點的下界, 並按下界值由小到大對各子節點排序. 令p ←p + 1.
步驟3 如果當前節點被探測盡, 令p ←p - 1, 轉步驟6. 否則, 設當前層(第p 層) 各活動子節點中具有最小下界值的節點為Q , 則在P 1末尾加入Q 對應第p 位置上的工件, 此時的當前節點轉為Q , 轉步驟4.
步驟4 因為當前節點是同層同父節點具有最小下界值的節點, 如果當前節點下界值大於或等於C* , 則不必再搜索當前節點及其同層同父的活動節點, 這樣, 當前節點的上一層節點(父節點)被探測盡, p ←p - 1, 去掉P 1 中的最後一個工件,轉步驟6. 否則, 轉步驟5.
步驟5 如果p = n, 則得到一個較優順序.令P* = P 1, C* 是當前節點的下界值, p ←p - 1,去掉P 1 中最後一個工件, 轉步驟6; 否則轉步驟2.
步驟6 若p ≠ 0, 去掉P 1 中最後一個工件,轉步驟3; 否則, 演算法停止. C* 是最優的目標函數值, P* 是最優順序.
分支結構演算法的實現(編程基礎)
我現在學到了分支結構了。又遇到問題了，不知道你還在不在,可以幫我嗎?(可以，沒問題.)
1、用Pascal語言表示下列的條件表達式：
（1）：x小於10；
（2）：0<=y<=5;(『小於等於』不會打)
（3）：x大於5或x為負數；
（4）：ch在「A」和「Z」之間（包括「A」和「Z」）；
（5）：年齡（age)不小於18，國籍(natioality)不是中國「CHINA」,也不是朝鮮「KOREA」的男性公民(sex=`maie`);
（6）：正數，在2～100之間且不能被2，或3，或5整除。
2、試寫出下列各項的Pascal語句：
（1）：如果wage大於10000，便減去10%的wage.
（2）：如果Choice的值為1，則讀取x的值，並列印x的平方；否則讀取y的值，並列印y的平方。
9. 麻煩問下各路大牛 怎麼求無向圖中的最小環長度 萬分感謝
我用的是Dijsktra演算法進行的計算。假設一個環中有兩個頂點A,B，那麼走完這個環的最小路程是從A到B的最短路+去掉A到B的最短路上的所有路徑後的A到B（B到A）的最短路（就相當於是從A走到B再走到A的最短路）
因此，在外層枚舉A，算出A到各個點的最短路，同時記下路徑。然後枚舉每一個B，刪掉A到B上最短路徑所經過的邊，再算一次A到B的最短路徑，然後兩者相加，求得一個環的最短路。最後找一個最小的環的長度，輸出即可。時間復雜度到了O(n^4)，所以我有一組花了0.9s.
但是這道題的難點在於那個BT的INPUT-------從來都沒有見過的圖的輸入方式：告訴的是邊與邊的關系。
我是這樣解決的：找出所有的邊的兩個端點（不管是否重復），並把這些端點連了哪些邊記錄下來。然後去掉重復的頂點，剩下的就是圖的頂點。接著通過枚舉尋找任意兩個頂點是否都連了相同的邊，如果連了，說明這兩個頂點就是被這條邊所連，因此就可以在鄰接矩陣中記錄下來。時間復雜度O(n^3)
這一題是我一次AC的。。。難得在USACO Cheapter4 裡面一次AC哈。。
Cherry還有更好的O(n^3)的演算法，我也不知道怎麼做的。感興趣的去看一下子。
10. 無向圖用矩陣冪演算法如何求其連通分支數
設連通矩陣A，x->y若連通，則A[x][y]=1（當然也有A[y][x]=1），否則A[x][y]=0，特別地有A[x][x]=1
此時A[x][y]>0當且僅當x->y有直接連通的邊
再考慮A^2=A*A，A^2[x][y]>0當且僅當x->y有長度小於等於2條邊的通路
最後，A^n[x][y]>0當且僅當x->y有任意長度的通路（n是節點數目）
所以用快速冪求出A^n，然後將A^n作為鄰接矩陣，DFS一遍就可以了