Kruskal 算法 先將途中所有邊的權(quán)值進(jìn)行從小到大排序，按照順序依次將邊的兩點(diǎn)加入最小生成樹的子圖中，若加入后產(chǎn)生圈，則舍棄這條邊，直到所有點(diǎn)在圖中為止
1).記Graph中有v個(gè)頂點(diǎn)，e個(gè)邊2).新建圖Graphnew，Graphnew中擁有原圖中相同的e個(gè)頂點(diǎn)，但沒(méi)有邊3).將原圖Graph中所有e個(gè)邊按權(quán)值從小到大排序4).循環(huán)：從權(quán)值最小的邊開(kāi)始遍歷每條邊 直至圖Graph中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中 如果 這條邊連接的兩個(gè)節(jié)點(diǎn)于圖Graphnew中不在同一個(gè)連通分量中就添加這條邊到圖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; //輸入點(diǎn)、邊數(shù) 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); //對(duì)邊的權(quán)值進(jìn)行排序 int res = 0; for (int i = 0; i < E; i++){ node e = s[i]; if (!same(e.u, e.v)){ //判斷兩點(diǎn)是否在一個(gè)通路 unite(e.u, e.v); //合并兩個(gè)點(diǎn) 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算法 先建立一個(gè)最小生成樹的子圖。任取一點(diǎn)s最為子圖的初始點(diǎn)，標(biāo)記。然后再子圖之外尋找與子圖中所有點(diǎn)距離最小的點(diǎn)，將這個(gè)點(diǎn)加入子圖的集合，并從這個(gè)點(diǎn)進(jìn)行擴(kuò)展求出相鄰點(diǎn)到子圖的最短距離
#define N 500+10#define INF 0x3f3f3f3f#define mem(arr,num) memset(arr,num,sizeof(arr))/**********************************************************/int minCost[N]; //某一點(diǎ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; //找到到子圖權(quán)值最小的點(diǎn) } 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]); //求出該點(diǎn)周圍的點(diǎn)距離子圖權(quán)值的最小值 } } return res;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
