連通圖：無向圖G中，若從頂點i到頂點j有路徑相連，則稱i,j是連通的；如果G是有向圖，那么連接i和j的路徑中所有的邊都必須同向；如果圖中任意兩點之間都是連通的，那么圖被稱作連通圖，
強連通圖：有向圖G中，對于任意的兩個點之間x,y，都存在x到y的路徑，為強連通圖；
弱連通圖：將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖，如果一個有向圖的基圖是連通圖，則有向圖是若連通圖；
單向連通：G=V,E;是有向圖，對于任意u,v屬于V，從u到達v或者v可達u,則稱G為單向連通圖；
連通分量：無向圖的一個極大連通圖子圖稱為G的一個連通分量；連通圖只有一個連通分量；
極大連通子圖：（無向圖）
- 連通圖只有一個極大連通子圖，就是它本身；
- 非連通圖有多個極大連通子圖（非連通圖的極大連通子圖叫做連通分量，每個分量都是一個連通圖）；
- 極大連通子圖中，加入任何一個不在圖點集中的點都會導致它不再連通；
- 下圖為非連通圖，圖中有兩個極大連通子圖（連通分量）：
極小連通子圖：（無向圖）
- 一個連通圖的生成樹是該連通圖的極小連通子圖；（同一個連通圖有不同的生成樹，所以生成樹不是唯一的，最小生成樹是唯一的）；
- 極小連通子圖是個連通圖；
- 極小連通子圖中，頂點個數為n, 則邊的個數為n-1;
- 如果在生成樹上添加一條邊，一定會構成一個環；
- 極小連通子圖的每條邊都不可少，如果去掉一條邊，則變成兩個連通分量；
- 生成樹：一個連通圖的最小連通子圖，無回路；
極大強連通子圖：（有向圖）
- 強連接圖的極大強鏈接圖為其本身；唯一；
- 非強連接圖有多個極大強連通子圖，非強連通圖的極大連通子圖叫做強連通分量；
最小生成樹：一個有n個節點的連通圖的生成樹是原圖的極小連通子圖，且包含了原圖中的所有n個節點，并且有保持圖連通的最少的邊；最少生成樹可以使用Kruskal演算法和Prim演算法求出；
Prim演算法：此演算法可以稱為加點法，使用貪心思想進行求解，Vnew Vold-new 之間，代價最小的邊對應的點，加入到Vnew之中；演算法從任意一節點開始，知道Vnew中包含所有的點；
- 圖中所有頂點集合V, 初始結合Vnew = {s}, Vold-new = V-Vnew;
- 在兩個集合Vnew和Vold-new 組成的邊中，選擇代價最小的邊（vnew, vold-new）,加入到生成樹；并把vold-new加入到Vnew之中；
- 重復上述步驟，直到Vnew包含所有的點；
- 證明：假設權值最小的邊不在最小生成樹中，此時將權值最小的邊加入生成樹中，必然會構成一個回路，去掉回路中權值最大的邊，構成一個新的最小生成樹，這時權值最小的邊在最小生成樹中，與原有假設構成矛盾，所以權值最小的邊一定在最小生成樹中；所以prim每次選入權值最小的邊的點加入的策略是正確的，
Kruskal演算法：此演算法可稱為加邊法；初始生成樹邊數為0，每次就選擇一條滿足條件的最小代價的邊，加入到生成樹的邊集合中；
- 把圖中的所有邊按代價從小到大排序；
- 把圖中的n個頂點，看成獨立的n棵樹組成的森林；
- 按照權值從小到大選擇邊，所選邊的頂點u,v應該屬于兩顆不同的樹；則成為最小生成樹的一條邊，并將這兩顆樹合并為一棵樹；
- 重復上述操作，直到當前邊集合中包括n-1課樹為止；
演算法實作參考：https://github.com/yaowenxu/codes/tree/master/最小生成樹演算法
保持更新，轉載請注明出處；更多內容請關注cnblogs.com/xuyaowen;
參考鏈接：
https://www.cnblogs.com/zhchoutai/p/8687614.html
極大連通子圖與極小連通子圖
最小生成樹（Kruskal和Prim演算法）
圖論——最小生成樹
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67596.html
標籤：其他
上一篇：spark啟動
下一篇：hadoop寫入檔案自動改變