經典的最小生成樹例子，Prime演算法，具體的步驟及其注釋本人均在代碼中附加，請仔細閱讀與品味，要求，可以熟練的打出，
1 //Prime演算法基礎 2 #include<iostream> 3 using namespace std; 4 5 int main() 6 { 7 int n,m,i,j,k,min,t1,t2,t3; 8 int e[7][7],dis[7],book[7] = {0}; 9 int inf = 99999999; 10 int count = 0,sum = 0; 11 cin >> n >> m; 12 13 //初始化 用鄰接矩陣存盤 14 for(int i = 1;i <= n;i++) 15 for(int j = 1;j <= n;j++) 16 if(i == j) 17 e[i][j] = 0; 18 else 19 e[i][j] = inf; 20 21 //讀入邊 無向圖來回都得設定權值 22 for(int i = 1;i <= m;i++) 23 { 24 cin >> t1 >> t2 >> t3; 25 e[t1][t2] = t3; 26 e[t2][t1] = t3; 27 } 28 29 //初始化dis陣列，這里是第一個頂點到各個頂點的初始距離，因為當前生成樹中只有一個頂點 30 for(int i = 1;i <= n;i++) 31 dis[i] = e[1][i]; 32 33 //Prime核心部分 34 //將第一個頂點（即1號頂點）加入生成樹 35 book[1] = 1;//這里用book陣列來標記一個頂點是否已經加入生成樹 36 count++;//表示生成樹中已加入一個頂點 37 while(count < n) 38 { 39 min = inf; 40 41 //掃描找出距離當前根頂點相連接的最小權值的頂點 42 for(int i = 1;i <= n;i++) 43 { 44 if(book[i] == 0 && min > dis[i])//如果根節點未被標記并且根節點到剩下的n-1個頂點之間有直連線（就是相連著的邊） 45 { 46 min = dis[i];//就將這條邊的權值代替之前初始化時的無窮大 ，更新min的值，min的值更新只在此for回圈中有效，此for回圈目的是找出連接根節點權值最小的那個頂點j，再把min放入for回圈中，一直比較，直至找到最小的權值及連的頂點j 47 j = i;//同時將此時的頂點的編號記錄在臨時變數j中，以便接下來使用 48 } 49 } 50 book[j] = 1;//將上面for回圈中找到的最小權值的頂點j加入到生成樹中并標記 51 count++;//生成樹中的頂點加一 52 sum += dis[j];//將權值最小的邊都累加，最終得到最優解 53 54 //掃描當前頂點j所有的邊，再以j為中心點，更新生成樹到每一個非樹頂點的距離 55 for(k = 1;k <= n;k++) 56 { 57 if(book[k] == 0 && dis[k] > e[j][k])//e[k]表示第一個加入的根頂點到頂點k之間的權值（可能直接連接也可能間接連接），e[j][k]表示的是當前根頂點作為j，到與j頂點直接相連的頂點k的權值 58 dis[k] = e[j][k];//此回圈的目的是找出離j頂點最近的頂點 59 } 60 } 61 cout << sum; 62 return 0; 63 } 64 /* 65 6 9 66 2 4 11 67 3 5 13 68 4 6 3 69 5 6 4 70 2 3 6 71 4 5 7 72 1 2 1 73 3 4 9 74 1 3 2 75 19 76 */
運行結果：
Kruskal演算法，需要用到并查集，具體請看以下代碼
1 //Kruskal演算法 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 struct edge 6 { 7 int u; 8 int v; 9 int w; 10 }e[10];//為了方便排序，這里創建了一個結構體陣列來存盤邊的關系，陣列大小根據實際情況來設定，要比m的最大值大1 11 int n,m; 12 int f[7],sum = 0,countt = 0;//并查集需要用到的一些變數,f陣列大小根據實際情況來設定，要比n的最大值大1 13 14 ////這個也是快速排序，也可以替代sort函式 15 //void quicksort(int left,int right) 16 //{ 17 // int i,j; 18 // struct edge t; 19 // if(left > right) 20 // return; 21 // i = left; 22 // j = right; 23 // while(i != j) 24 // { 25 // //順序很重要，要先從右邊開始找 26 // while(e[j].w >= e[left].w && i < j) 27 // j--; 28 // //再從左邊開始找 29 // while(e[i].w <= e[left].w && i < j) 30 // i++; 31 // //交換 32 // if(i < j) 33 // { 34 // t = e[i]; 35 // e[i] = e[j]; 36 // e[j] = t; 37 // } 38 // } 39 // //最終將基準數歸位，將left和i互換 40 // t = e[left]; 41 // e[left] = e[i]; 42 // e[i] = t; 43 // 44 // quicksort(left,i - 1);//繼續處理左邊的，這里是一個遞回的程序 45 // quicksort(i + 1,right);//繼續處理右邊的，這里是一個遞回的程序 46 // return; 47 //} 48 49 //并查集尋找祖先的函式 50 int getf(int v) 51 { 52 if(f[v] == v) 53 return v; 54 else 55 { 56 //這里是路徑壓縮 57 f[v] = getf(f[v]); 58 return f[v]; 59 } 60 } 61 //并查集合并兩個子集合的函式 62 int merge(int v,int u) 63 { 64 int t1,t2; 65 t1 = getf(v); 66 t2 = getf(u); 67 if(t1 != t2)//判斷兩個點是否在同一個集合中 68 { 69 f[t2] = t1; 70 return 1; 71 } 72 return 0; 73 } 74 75 bool cmp(const edge &a,const edge &b) 76 { 77 return a.w < b.w; 78 } 79 80 int main() 81 { 82 //讀入頂點個數n和邊的條數m 83 cin >> n >> m; 84 //讀入邊，這里用結構體陣列來存盤邊的關系 85 for(int i = 1;i <= m;i++) 86 cin >> e[i].u >> e[i].v >> e[i].w; 87 // quicksort(1,m);//按照權值從大到小對邊進行快速排序 88 //快速排序權值 89 sort(e + 1,e + m + 1,cmp); 90 //并查集初始化 91 for(int i = 1;i <= n;i++) 92 f[i] = i; 93 94 //Kruskal演算法核心部分 95 for(int i = 1;i <= m;i++) 96 { 97 //判斷一條邊的兩個頂點是否已經連通，即判斷是否已在同一個集合中 98 if(merge(e[i].u,e[i].v))//如果目前不連通，則選用這條邊 99 { 100 countt++;//滿足條件將頂點加入生成樹 101 sum += e[i].w;//路徑累加和 102 } 103 if(countt == n - 1)//當頂點均加入到生成樹中時，結束回圈 104 break; 105 } 106 cout << sum << endl; 107 return 0; 108 }
運行結果：
并查集例題
下面是對并查集使用的代碼，并查集不太理解的可以看看下面的代碼
1 //并查集的使用 2 #include<iostream> 3 using namespace std; 4 int f[1000],n,m,k,sum; 5 6 //這是找爹的遞回函式，不停的去找爹，直到找到祖宗為止，即找到根節點，這個函式的目的是判斷兩個頂點是否屬于同一個集合 7 int getf(int v) 8 { 9 if(f[v] == v) 10 return v; 11 else 12 { 13 /*這里是路徑壓縮，每次在函式回傳的時候，順帶把同一個集合里面的元素都改為根節點的祖先編號，這樣可以提高今后找到樹的祖先的速度*/ 14 f[v] = getf(f[v]); 15 return f[v]; 16 } 17 } 18 //這里是合并兩子集合的函式,在合并函式中呼叫getf函式，看兩個頂點是否是屬于同一個集合，然后再決定是否執行合并操作 19 void merge(int v,int u) 20 { 21 int t1,t2; 22 t1 = getf(v); 23 t2 = getf(u); 24 if(t1 != t2)//根據呼叫getf的函式，判斷兩個頂點是否在同一個集合中，即是否為同一個祖先 25 { 26 f[t2] = t1; 27 } 28 } 29 30 int main() 31 { 32 int x,y; 33 cin >> n >> m; 34 //這里是初始化，非常的重要，陣列里面存的是自己陣列下標的編號就好了 35 for(int i = 1;i <= n;i++) 36 f[i] = i; 37 for(int i = 1;i <= m;i++) 38 { 39 cin >> x >> y; 40 merge(x,y);//將兩個頂點傳入合并集合函式中進行操作 41 } 42 for(int i = 1;i <= n;i++) 43 { 44 if(f[i] == i)//根節點的值依舊是原先的值，即判斷有幾個頂點的值不變即有幾個不同的集合 45 sum++; 46 } 47 cout << sum << endl; 48 return 0; 49 } 50 /* 51 10 9 52 1 2 53 3 4 54 5 2 55 4 6 56 2 6 57 8 7 58 9 7 59 1 6 60 2 4 61 3 62 */
運行結果：
?
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/87996.html
標籤：C++
上一篇：160. 相交鏈表
下一篇：POJ1852