最小生成樹
給定一個無向圖，如果它的某個子圖中任意兩個頂點都互相連通并且是一棵樹，那么這棵樹就叫做生成樹。如果邊上有權值，那么使得權值最小的生成樹叫做最小生成樹。
Prim算法
Prim算法和Dijktra算法十分相似，都是從某個頂點出發(fā)，不斷添加邊的算法。不同的是Dijkstra算法每次添加的點在所有未添加的點中到原點的距離最小，Prim算法每次添加的點在所有未添加的點中到T中的點的距離最小
算法思路
首先，我們假設有一棵只包含一個頂點v的樹T。然后貪心的選取T和其他頂點之間相連的最小權值的邊，并把邊的另一節(jié)點加到T中。不斷進行這個操作就可以得到最小生成樹。
算法過程
-
初始化
原點的距離初始化為0，其他點的距離初始化為INF
-
循環(huán)
執(zhí)行以下循環(huán)過程，直到所有節(jié)點都包括在最小生成樹中
從未包括在最小生成樹的節(jié)點中選出距最小生成樹任意一點距離最小的節(jié)點
將選出的節(jié)點標記為已包括在最小生成樹
更新選出的節(jié)點的鄰居節(jié)點的距離($w_{vi}$表示(v, i)邊的權值)
$$
d[i] = min{d[i],w_{vi}}
$$
代碼
用鄰接矩陣表示圖
用優(yōu)先級隊列選出距離最小的節(jié)點
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> p;
struct mycmp{
bool operator()(p p1, p p2){
return p1.second > p2.second;
}
};
const int INF = 10000;
const int MAX_V = 100;
int g[MAX_V][MAX_V];//graph
int included[MAX_V];//included[i]=1 when node i is included in MST
int d[MAX_V];//current distance to T
int vNum;
int eNum;
int res;
void init(){
res = 0;
for(int i = 0; i < vNum; i++){
included[i] = 0;
d[i] = INF;
for(int j = 0; j < vNum; j++){
g[i][j] = INF;
}
}
}
void addEdge(int u, int v, int w){
g[u][v] = w;
g[v][u] = w;
}
void Prim(){
priority_queue<p, vector<p>, mycmp> q;
d[0] = 0;
q.push(make_pair(0, d[0]));
while(!q.empty()){
int u = q.top().first;
int du = q.top().second;
q.pop();
if(included[u]) continue;
res += du;
included[u] = 1;
printf("include:%d\n", u);
for(int i = 0; i < vNum; i++){
if(!included[i] && d[i] > g[u][i]){
d[i] = g[u][i];
q.push(make_pair(i, d[i]));
}
}
}
}
int main(){
scanf("%d %d", &vNum, &eNum);
init();
for(int i = 0; i < eNum; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}
Prim();
printf("%d\n", res);
return 0;
}
Kruskal算法
算法思路
Kruskal算法按照邊的權值從小到大的順序訪問邊，如果訪問的邊與當前生成樹不產(chǎn)生回路，就把這條邊添加到生成樹中。
算法實現(xiàn)
-
邊的數(shù)據(jù)結構
定義一個類Edge如下：
struct Edge{ int u, v, w; Edge(int u, int v, int w){ this->u = u; this->v = v; this->w = w; } bool operator < (const Edge &e){ return w < e.w; } };將邊的對象存放在容器vector中
vector<Edge> edges; -
排序
排序方法一
可以在類中重載運算符$<$
struct Edge{ ... bool operator < (const Edge &e){ return w < e.w; } };調(diào)用algorithm庫中sort方法對容器vector中的邊對象進行排序
sort(edges.begin(), edges.end());排序方法二
可以重新定義一個排序函數(shù)
bool mycmp(const Edge &e1, const Edge &e2){ return e1.w < e2.w; }將定義的排序函數(shù)作為參數(shù)調(diào)用sort函數(shù)
sort(edges.begin(), edges.end(), mycmp); -
判斷是否產(chǎn)生回路
并查集是維護是否屬于同一組的數(shù)據(jù)結構。在本算法中，并查集用來判斷兩個點是否屬于同一連通分量，
按照權值從小到大的順序訪問邊時，如果邊的兩個點不在同一個集合，就把這兩個點所在的集合合并；如果在同一個集合，說明說明這兩個點屬于同一連通分量，會使生成樹產(chǎn)生回路，跳過。
代碼
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_E = 10000;
const int MAX_V = 100;
struct Edge{
int u, v, w;
Edge(int u, int v, int w){
this->u = u;
this->v = v;
this->w = w;
}
bool operator < (const Edge &e){
return w < e.w;
}
};
/*bool mycmp(const Edge &e1, const Edge &e2){
return e1.w < e2.w;
}*/
vector<Edge> edges;
int vNum;
int eNum;
int res;
int p[MAX_V];
int r[MAX_V];
void init(){
for(int i = 0; i < vNum; i++){
p[i] = i;
}
}
int Find(int x){
if(x == p[x]) return p[x];
else return p[x] = Find(p[x]);
}
void Union(int x, int y){
int xRoot = Find(x);
int yRoot = Find(y);
if(r[x] < r[y]) p[xRoot] = yRoot;
else{
p[yRoot] = xRoot;
if(r[xRoot] == r[yRoot]) r[xRoot]++;
}
}
bool sameRoot(int x, int y){
return Find(x) == Find(y);
}
void Kruskal(){
vector<Edge>::iterator it;
for(it = edges.begin(); it != edges.end(); ++it){
int u = (*it).u;
int v = (*it).v;
int w = (*it).w;
printf("%d %d %d\n", u, v, w);
if(!sameRoot(u, v)){
Union(u, v);
res += w;
}
}
}
int main(){
scanf("%d %d", &vNum, &eNum);
init();
for(int i = 0; i < eNum; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
edges.push_back(Edge(u, v, w));
}
//sort(edges.begin(), edges.end(), mycmp);
sort(edges.begin(), edges.end());
Kruskal();
printf("%d\n", res);
return 0;
}
