8.5最小生成樹
最小生成村樹有很多種解決方案，可以分為幾類：
1.創(chuàng)建并擴(kuò)展一些樹，使它們合并成更大的樹(Boruvka)
2.創(chuàng)建一個(gè)樹的集構(gòu)成一棵生成樹(Kruskal)
3.創(chuàng)建并擴(kuò)展一棵樹，為它添加新的樹枝(Prim)
4.創(chuàng)建并擴(kuò)展一棵樹，為它添加新的樹枝，也可能從中刪除一些樹枝(Dijkstra)

8.5.1 Boruvka算法：
最早的查找最小生成樹的算法可能是1926年Otakaar.Boruvka提出的。在這個(gè)方法中，我們從有|V|個(gè)頂點(diǎn)的樹的某個(gè)頂點(diǎn)開始，然后對每個(gè)頂點(diǎn)v查找所有從v向外的邊中權(quán)最小的edge(vu)并創(chuàng)建一個(gè)包括這些邊的最小的樹。然后，查找能夠?qū)⑦@些樹連接成一個(gè)大樹的權(quán)最小的邊。創(chuàng)建好一棵樹之后，程序結(jié)束。
BoruvkaAlgorithm(帶權(quán)連通無向圖 graph)
 令每一個(gè)頂點(diǎn)都成為一棵單頂點(diǎn)樹的根;
 while 單頂點(diǎn)樹的數(shù)量大于1
  for 每棵樹t
   e = 權(quán)值最小的邊(vu)，其中v在樹t中而u不屬于t;
   將樹t和包含頂點(diǎn)u的樹連接成一棵樹，如果它尚未創(chuàng)建的話;
說明：
在while循環(huán)珠每次重復(fù)中，每個(gè)現(xiàn)存的r樹和一條邊相連，得到至少一棵樹。最壞情況下，產(chǎn)生r/2棵樹；最好情況下，產(chǎn)生一棵樹。后來的重復(fù)中，有r/4棵樹等等。最壞情況下，需要lg|V|次重復(fù)，|V|是單頂點(diǎn)樹的初始值。Boruvka算法非常適合并行處理，因?yàn)閷τ诿恳豢脴洌仨毆?dú)立地找到最小邊。

8.5.2 Kruskal算法
先把所有的邊根據(jù)權(quán)排序，然后檢測這個(gè)排序序列中的每一條邊，看一下在構(gòu)造時(shí)，它能否考慮成為樹的一部分。如果加入它不產(chǎn)生環(huán)路就將它添加到樹中。
KruskalAlgorithm(帶權(quán)連通無向圖 graph)
 tree = null;
 edges = 按照權(quán)值大小排序的graph的全部邊;
 for (i = 1; i <= |E| and |tree| < |V| - 1; i++)
  if edges中的邊edges[i]和tree中的邊不產(chǎn)生環(huán)路
   將edges[i]加進(jìn)tree;
說明：
這個(gè)算法的復(fù)雜度是由所采用的排序復(fù)雜度確定的，對一個(gè)有效的排序的復(fù)雜度，對一個(gè)有效的排序的復(fù)雜度是O(|E|lg|E|)。它也依賴于環(huán)路檢測方法的復(fù)雜度。如果使用union()實(shí)現(xiàn)Kruskal算法，那么for循環(huán)變成
for (i = 1; i <= |E| and |tree| < |V| - 1; i++)
 union(edge[i] = edge(vu));
盡管union()可以被調(diào)用至多|E|次，在檢測到一個(gè)環(huán)路(第一次)之后它就退出并且執(zhí)行一個(gè)聯(lián)合，復(fù)雜度是O(|V|)，只將|V|-1條邊加入到tree中。因些KruskalAlgorithm的for循環(huán)的復(fù)雜度是O(|E| + (|V| - 1)|V|)，也就是O(|V|^2)。所以KruskalAlgorithm的復(fù)雜度取決于一個(gè)排序算法的復(fù)雜度O(|E|lg|E|)。

8.5.3 Jarnik.Prim算法
在這個(gè)方法中，開始時(shí)所有的邊都是排序的，但是準(zhǔn)備加入生成樹的邊不僅不會(huì)在樹中產(chǎn)生環(huán)路，而且也和樹中已經(jīng)有的一個(gè)頂點(diǎn)關(guān)聯(lián)。
JarnikPrimAlgorithm(帶權(quán)連通無向圖 graph)
 tree = null;
 edges = 按權(quán)值大小排序的graph的全部邊
 for i = 1 到|V| - 1
  for j = 1 到 |edges|
   if edges 中的邊edges[j]和tree中的邊不會(huì)產(chǎn)生回路并且和tree中的一個(gè)頂點(diǎn)關(guān)聯(lián)
    將edges[j]添加進(jìn)tree;
    break;

8.5.4 Dijkstra算法
JarnikPrimAlgorithm(帶權(quán)連通無向圖 graph)
 tree = null;
 edges = 未排序的graph全部邊;
 for j = 1 到 |edges|
  將edges[j]添加進(jìn)tree;
  if 在tree中有環(huán)路
   從這個(gè)環(huán)路中刪除權(quán)值最大的一條邊;