最小生成树算法

最小生成树

给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树。如果边上有权值，那么使得权值最小的生成树叫做最小生成树。

---

Prim算法

Prim算法和Dijktra算法十分相似，都是从某个顶点出发，不断添加边的算法。不同的是Dijkstra算法每次添加的点在所有未添加的点中到原点的距离最小，Prim算法每次添加的点在所有未添加的点中到T中的点的距离最小

算法思路

首先，我们假设有一棵只包含一个顶点v的树T。然后贪心的选取T和其他顶点之间相连的最小权值的边，并把边的另一节点加到T中。不断进行这个操作就可以得到最小生成树。

算法过程

• 初始化

  原点的距离初始化为0，其他点的距离初始化为INF

• 循环

  执行以下循环过程，直到所有节点都包括在最小生成树中

  1. 从未包括在最小生成树的节点中选出距最小生成树任意一点距离最小的节点

  2. 将选出的节点标记为已包括在最小生成树

  3. 更新选出的节点的邻居节点的距离($w_{vi}$表示(v, i)边的权值)
     $$
     d[i] = min{d[i],w_{vi}}
     $$

代码

用邻接矩阵表示图

用优先级队列选出距离最小的节点

#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算法按照边的权值从小到大的顺序访问边，如果访问的边与当前生成树不产生回路，就把这条边添加到生成树中。

算法实现

• 边的数据结构

  定义一个类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;
    }
  };
  

  调用algorithm库中sort方法对容器vector中的边对象进行排序

  sort(edges.begin(), edges.end());
  

  排序方法二

  可以重新定义一个排序函数

  bool mycmp(const Edge &e1, const Edge &e2){
    return e1.w < e2.w;
  }
  

  将定义的排序函数作为参数调用sort函数

  sort(edges.begin(), edges.end(), mycmp);
  

• 判断是否产生回路

  并查集是维护是否属于同一组的数据结构。在本算法中，并查集用来判断两个点是否属于同一连通分量，

  按照权值从小到大的顺序访问边时，如果边的两个点不在同一个集合，就把这两个点所在的集合合并；如果在同一个集合，说明说明这两个点属于同一连通分量，会使生成树产生回路，跳过。

代码

#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;
}