不好意思 時間比較短,下面應該還會有修訂的= = , 那段話是我復制過來的,覺得挺好的就用一下.

下面是講解(不理解一的時候 , 可以看看二 ,結合圖片):

一: ? 最小樹形圖，就是給有向帶權圖中指定一個特殊的點root，求一棵以root為根的有向生成樹T，并且T中所有邊的總權值最小。最小樹形圖的第一個算法是 1965年朱永津和劉振宏提出的復雜度為O(VE)的算法。
? ? ? ?判斷是否存在樹形圖的方法很簡單，只需要以v為根作一次圖的遍歷就可以了，所以下面的 算法中不再考慮樹形圖不存在的情況。
在所有操作開始之前，我們需要把圖中所有的自環全都清除。很明顯，自環是不可能在任何一個樹形圖上的。只有進 行了這步操作，總算法復雜度才真正能保證是O(VE)。
首先為除根之外的每個點選定一條入邊，這條入邊一定要是所有入邊中最小的。現在所有的最小 入邊都選擇出來了，如果這個入邊集不存在有向環的話，我們可以證明這個集合就是該圖的最小樹形圖。這個證明并不是很難。如果存在有向環的話，我們就要將這 個有向環所稱一個人工頂點，同時改變圖中邊的權。假設某點u在該環上，并設這個環中指向u的邊權是in[u]，那么對于每條從u出發的邊(u, i, w)，在新圖中連接(new, i, w)的邊，其中new為新加的人工頂點; 對于每條進入u的邊(i, u, w)，在新圖中建立邊(i, new, w-in[u])的邊。為什么入邊的權要減去in[u]，這個后面會解釋，在這里先給出算法的步驟。然后可以證明，新圖中最小樹形圖的權加上舊圖中被收縮 的那個環的權和，就是原圖中最小樹形圖的權。
? ? ? ? 上面結論也不做證明了。現在依據上面的結論，說明一下為什么出邊的權不變，入邊的權要減去in [u]。對于新圖中的最小樹形圖T，設指向人工節點的邊為e。將人工節點展開以后，e指向了一個環。假設原先e是指向u的，這個時候我們將環上指向u的邊 in[u]刪除，這樣就得到了原圖中的一個樹形圖。我們會發現，如果新圖中e的權w'(e)是原圖中e的權w(e)減去in[u]權的話，那么在我們刪除 掉in[u]，并且將e恢復為原圖狀態的時候，這個樹形圖的權仍然是新圖樹形圖的權加環的權，而這個權值正是最小樹形圖的權值。所以在展開節點之后，我們 得到的仍然是最小樹形圖。逐步展開所有的人工節點，就會得到初始圖的最小樹形圖了。
如果實現得很聰明的話，可以達到找最小入邊O(E)，找環 O(V)，收縮O(E)，其中在找環O(V)這里需要一點技巧。這樣每次收縮的復雜度是O(E)，然后最多會收縮幾次呢？由于我們一開始已經拿掉了所有的 自環，我門可以知道每個環至少包含2個點，收縮成1個點之后，總點數減少了至少1。當整個圖收縮到只有1個點的時候，最小樹形圖就不不用求了。所以我們最 多只會進行V-1次的收縮，所以總得復雜度自然是O(VE)了。由此可見，如果一開始不除去自環的話，理論復雜度會和自環的數目有關。

?

二: ? ? 最開始的圖，把所有的最小入邊都累加到ret里。至于為什么，因為這樣才能保證所得的ret有可能是最小樹形圖的解，當然，是在這些最小入邊集合不行成環得情況下。
如果有了環，ret肯定不是最終答案，因為環中間有的邊需要刪掉，而且環之間也要連接起來。現在我們無法得知刪除環中的哪些邊才行。這就需要建立新圖了。
? ? ? ? ? 舉個例子：某個圖的部分圖中， 1->2權值為3， 2->1權值為4， 3->1權值為9， 4->2權值為7。 那么可以看到，結點1和結點2是形成了一個環的。我們僅從其大小不知道刪除哪條邊比較好，這時看到3->1權值為9， 如果走這條邊，那么接下來只能刪除掉2->1這條邊，同理走4->2的話就要刪除掉1->2這條邊。 那么就不妨建立新圖， 將1和2縮成一點，3->1的權值就變成了9-4=5， 4->2的權值變成了7-3=4。 這樣的話，就相當于變相刪除了不需要走的邊了。形成新圖后，又變成了最小樹形圖的求解，就這樣循環下去，直到圖中的最小邊集沒有環為止。

? ? ??

下面是模板代碼:

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 const int MAXN = 1e4 , INF = 1e8; 7 int d[MAXN] , id[MAXN] , vis[MAXN] , pre[MAXN]; //d:除root點外每個點的最小入邊 id:下一次建圖新的節點號 vis:用來判斷是否成環 下面程序見 pre:點的前序節點 8 int V , E; // V:點的個數 E:邊的個數 9 struct node { 10 int u , v , cost; //邊的起點 終點 以及長度 11 }edge[MAXN]; 12 13 int zhuliu(int root) { 14 int res = 0; //最小樹形圖的長度 15 while(true) { 16 for(int i = 0 ; i < V ; i++) { 17 d[i] = INF; 18 } 19 for(int i = 0 ; i < E ; i++) { //尋找最小入邊 20 int u = edge[i].u , v = edge[i].v; 21 if(u != v && edge[i].cost < d[v]) { 22 pre[v] = u; 23 d[v] = edge[i].cost; 24 } 25 } 26 for(int i = 0 ; i < V ; i++) { 27 if(i != root && d[i] == INF) { //除了root之外 有別的點無最小入邊 28 return -1; 29 } 30 } 31 int cont = 0; 32 memset(id , -1 , sizeof(id)); 33 memset(vis , -1 , sizeof(vis)); 34 d[root] = 0; 35 for(int i = 0 ; i < V ; i++) { //找環 36 res += d[i]; 37 int v = i; 38 //vis[v] == i 表明找到一個環 id[v] != -1 表明這個點在循環中已經被下面的操作縮點(在環中) v == root 說明尋找到了根節點 39 while(vis[v] != i && id[v] == -1 && v != root) { //每個點尋找前序節點 要么找到根部 要么找到一個環 40 vis[v] = i; 41 v = pre[v]; 42 } 43 if(v != root && id[v] == -1) { //成環 縮點 44 for(int u = pre[v] ; u != v ; u = pre[u]) { 45 id[u] = cont; 46 } 47 id[v] = cont++; 48 } 49 } 50 if(cont == 0) { //無環 break 51 break; 52 } 53 for(int i = 0 ; i < V ; i++) { 54 if(id[i] == -1) { //沒有成環的點 55 id[i] = cont++; 56 } 57 } 58 for(int i = 0 ; i < E ; i++) { //重新建圖 重新標記 59 int u = edge[i].u , v = edge[i].v; 60 edge[i].u = id[u] , edge[i].v = id[v]; 61 if(id[v] != id[u]) { 62 edge[i].w -= d[v]; //理解上面的文字描述 > . < !(特別是二) 63 } 64 } 65 V = cont; 66 root = id[root]; //新的根 67 } 68 } 69 70 int main() 71 { 72 73 }

寫的(盜用的)有些匆忙...

?

轉載于:https://www.cnblogs.com/Recoder/p/5008678.html

總結

以上是生活随笔為你收集整理的最小树形图(朱刘算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。