最小生成树

n个顶点组成的带权无向图，其生成树，即包含全部n个顶点并有n-1条边的无向连通子图。
最小生成树即各边权值和最小的一棵生成树，求最小生成树有kruskal算法和prim算法

kruskal算法

1. 建立一个并查集，每个顶点一个集合
2. 把所有边，按照权值大小进行排序
3. 按照权值从小到大遍历每一条边
   • 若边的顶点<x,y>已经在同一个集合中，那么忽略
   • 若边的顶点<x,y>不在同一个集合中，将该边的权值记录到总和中

对边进行排序

1. 设计一个边类edge，包含两个顶点x,y，和边权重weight
2. 设置一个边数组，以便排序
3. sort edge

例题——还是畅通工程

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
//#include <bits/stdc++.h>
using namespace std;
struct edge{
    int x;
    int y;
    int weight;
};

#define N 1000

int father[N];//存储每个元素父节点的下标
int height[N];//存储某个根的数的高度

void init(int n){
    //最开始的时候，每一个元素都要单独构建一个集合
    for (int i = 0; i < n; ++i) {
        //i的编号从0到n-1
        father[i]=i;//每个元素各自为根
        height[i]=1;//每个树的初始高度都是1
    }
}

int find(int x){
    if (x != father[x]){
        //递归向上找
//        return find(father[x]);
        //find路径压缩，找到祖先（爷爷）后先不返回，把他设为新的父亲
        father[x]= find(father[x]);

    }
    //x就是子树的根
    return father[x];
}

void _union(int x, int y, int weight, int &total){
    //合并两棵树，先要找到y的祖先，再把y祖先的父亲设为x的祖先
//    father[find(y)] = find(x);
    x = find(x);
    y = find(y);
    if (x!=y){
        total+=weight;
    }
    if (height[x]<height[y]){
        father[x]=y;
    } else if (height[x]>height[y]){
        father[y]=x;
    } else{
        father[y]=x;
        ++height[x];
    }
}
bool compare(edge lhs, edge rhs){
    return lhs.weight<rhs.weight;
}

int main() {
    int n;
    while (scanf("%d",&n)!=EOF){
        if (n==0){
            break;
        }
        init(n);
        vector<edge> vec;
        for (int i = 0; i < n*(n-1)/2; ++i) {
            edge e;
            scanf("%d%d%d",&e.x,&e.y,&e.weight);
            vec.push_back(e);
        }
        sort(vec.begin(),vec.end(), compare);
        int total=0;
        for (int i = 0; i < n*(n-1)/2; ++i) {
            _union(vec[i].x,vec[i].y,vec[i].weight,total);
        }
        printf("%d\n",total);
    }
    return 0;
}

dijkstra算法

单源最短路径

1. 定义一个数组dist[n]，记录当前最短路径，起点设为0，其他设置为无穷大：INT_MAX
2. 遍历起点能够一次到达的所有边，更新dist数组
3. 下一个结点选择：① dist最小 ② 未访问过（用小根堆存储）
4. 循环2.3.两步直至所有都访问过，得到最终的dist

例题——畅通工程续

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
//#include <bits/stdc++.h>
using namespace std;
#define N 300
struct edge{
    int y;
    int weight;
};
struct node{//小根堆专用的类
    int dist;//当前最短距离
    int x;//编号
};
bool operator <(node lhs, node rhs){
    return lhs.dist>rhs.dist;//运算符重载
}

vector<edge> graph[300];
int dijkstra(int s, int t, int n){
    int dist[N];//dist[序号]，表示s点到序号点的当前最小距离
    bool visited[N]={false};
    for (int i = 0; i < n; ++i) {
        dist[i] = INT_MAX;
    }
    //小根堆
    priority_queue<node> pq;//第一次访问到某个结点的时候再加入到优先队列中
    //第一个入队的结点是起点
    dist[s] = 0;//起点到起点距离是0
    node no;
    no.dist = dist[s];
    no.x = s;
    pq.push(no);//结点放入小根堆
    //遍历优先队列，每次取出最小的边，考察他的所有边，取出最短的
    //队列为空  时退出
    while(pq.empty()== false){
        int x = pq.top().x;//堆顶的编号（当前距离最小的一个点的编号）
        pq.pop();//出队
        if (visited[x]== true){//如果这个结点已经被访问过，那么就不需要访问它了，直接进入下次循环
            continue;
        }
        visited[x]= true;//未访问过，那么设为已访问
        for (int i = 0; i < graph[x].size(); ++i) {
            //遍历以x为起点的所有关联边
            int y = graph[x][i].y;//x为一端的边的另一端点
            int weight = graph[x][i].weight;//边的权值
            //如果起点到y的距离大于先到x再到y的距离
            if (dist[y]>dist[x]+weight){
                dist[y] = dist[x]+weight;
                no.dist = dist[y];
                no.x=y;
                pq.push(no);
            }
        }
    }
    if (dist[t]!=INT_MAX){
        return dist[t];//终点可达
    } else{
        return -1;//终点不可达，不存在路径
    }
}


int main() {
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF){
        for (int i = 0; i < n; ++i) {
            graph[i].clear();//清理每个链表中残留的边
        }
        for (int i = 0; i < m; ++i) {
            int x,y,weight;
            scanf("%d%d%d",&x,&y,&weight);
            //将边的信息填入链表
            edge e;
            e.y = y;
            e.weight = weight;
            graph[x].push_back(e);
            e.y = x;
            e.weight = weight;
            graph[y].push_back(e);
        }
        int s,t;
        scanf("%d%d",&s,&t);
        printf("%d\n", dijkstra(s,t,n));
    }
    return 0;
}