Kruskal 算法 先將途中所有邊的權值進行從小到大排序，按照順序依次將邊的兩點加入最小生成樹的子圖中，若加入后產生圈，則舍棄這條邊，直到所有點在圖中為止
1).記Graph中有v個頂點，e個邊2).新建圖Graphnew，Graphnew中擁有原圖中相同的e個頂點，但沒有邊3).將原圖Graph中所有e個邊按權值從小到大排序4).循環(huán)：從權值最小的邊開始遍歷每條邊 直至圖Graph中所有的節(jié)點都在同一個連通分量中 如果 這條邊連接的兩個節(jié)點于圖Graphnew中不在同一個連通分量中就添加這條邊到圖Graphnew中#include<iostream>#include<vector>#include<algorithm>#include<cstdlib>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<string>#include<cstring>#include<map>#include<set>using namespace std;#define N 100#define INF 0x3f3f3f3f/*****************************************************/struct node{ int u, v, cost;};bool cmp(node a, node b){ return a.cost < b.cost;}node s[N];int par[N];int ranks[N];int V, E;void init_union_find(int v);int find(int x);void unite(int a, int b);bool same(int a, int b);int Kruskal();int main(){ cin >> V >> E; //輸入點、邊數 init_union_find(V); //初始化并查集 for (int i = 0; i < E; i++){ cin >> s[i].u >> s[i].v >> s[i].cost; } cout<<Kruskal();}int Kruskal(){ sort(s, s + E, cmp); //對邊的權值進行排序 int res = 0; for (int i = 0; i < E; i++){ node e = s[i]; if (!same(e.u, e.v)){ //判斷兩點是否在一個通路 unite(e.u, e.v); //合并兩個點 res += e.cost; } } return res;}void init_union_find(int v){ for (int i = 0; i <= V; i++) { par[i] = i; ranks[i] = 1; }}void unite(int a, int b){ a = find(a); b = find(b); if (a==b)return; if (ranks[a] < ranks[b]){ par[a] = b; } else{ if (ranks[a] == ranks[b]) { ranks[a]++; } par[b] = a; }}int find(int x){ if (par[x] == x)return x; return par[x] = find(par[x]);}bool same(int a, int b){ if (par[a] == par[b])return true; return false;}PRim算法 先建立一個最小生成樹的子圖。任取一點s最為子圖的初始點，標記。然后再子圖之外尋找與子圖中所有點距離最小的點，將這個點加入子圖的集合，并從這個點進行擴展求出相鄰點到子圖的最短距離
#define N 500+10#define INF 0x3f3f3f3f#define mem(arr,num) memset(arr,num,sizeof(arr))/**********************************************************/int minCost[N]; //某一點到子圖的最短距離int cost[N][N]; int V, E;bool used[N];int Prim(){ mem(used, 0); mem(minCost, 0x3f); int res = 0; minCost[1] = 0; while (1){ int v = -1; for (int i = 1; i <= V; i++){ if (!used[i] && (v == -1 || minCost[i] < minCost[v])) v = i; //找到到子圖權值最小的點 } if (v == -1)break; used[v] = true; res += minCost[v]; for (int i = 1; i <= V; i++){ minCost[i] = min(minCost[i], cost[v][i]); //求出該點周圍的點距離子圖權值的最小值 } } return res;}新聞熱點
疑難解答
