最小生成树
n个顶点组成的带权无向图，其生成树，即包含全部n个顶点并有n-1条边的无向连通子图。
最小生成树即各边权值和最小的一棵生成树，求最小生成树有kruskal算法和prim算法
kruskal算法
- 建立一个并查集，每个顶点一个集合
- 把所有边，按照权值大小进行排序
- 按照权值从小到大遍历每一条边
- 若边的顶点<x,y>已经在同一个集合中，那么忽略
- 若边的顶点<x,y>不在同一个集合中，将该边的权值记录到总和中
对边进行排序
- 设计一个边类edge，包含两个顶点x,y，和边权重weight
- 设置一个边数组，以便排序
- 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算法
单源最短路径
- 定义一个数组dist[n]，记录当前最短路径，起点设为0，其他设置为无穷大：INT_MAX
- 遍历起点能够一次到达的所有边，更新dist数组
- 下一个结点选择：① dist最小 ② 未访问过（用小根堆存储）
- 循环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;
}
