图论

作者: CristianoC | 来源:发表于2020-07-09 11:52 被阅读0次

<<数学之美>> part5
《宇宙猜想》目录
《数学之美》笔记图论与网络爬虫
美团 EasyReact 源码剖析：图论与响应式编程
2020-04-03
计划
图论
图论
图论
图论

并查集是解决集合类问题，比如朋友问题道路联通问题等等，本质上是利用树形结构来加快区分集合的算法，简单来说就是每有两个结点就判断他们的父亲是不是同一个（判断是否联通），如果不是则通过把其中一个父亲变成另一个的父亲的方式让他们联通，注意其中路径压缩的小技巧。

#include <iostream>
using namespace std;
const int maxn = 1005;
int father[maxn];
int find(int x){
    if(x == father[x])
        return x;
    father[x] = find(father[x]);
    return father[x];
}
int main(){
    int N,M;
    while (cin>>N){
        if(N == 0)
            break;
        cin>>M;
        for(int i = 1;i <= N;i++)
            father[i] = i;
        int sum = 0;
        for(int i = 0;i < M;i++){
            int x,y;
            cin>>x>>y;
            int fx = find(x);
            int fy = find(y);
            if(fx != fy){
                father[fx] = fy;
                //这种难理解一点
                //sum++;
            }
        }
        for(int i = 1;i <= N;i++){
            if(father[i] == i)
                sum++;
        }
        cout<<sum - 1<<endl;
        //cout<<N - sum - 1<<endl;
    }
    return 0;
}

最小生成树
最小生成树的经典应用就是给出一些路径以及权重，求最短加权路径和，一般用kruskal算法都可以ac，思想是先按照权重把所有路径从小到大排序，然后从小到大开始连通，连通与否的判断标准和上面并查集一样，看他们的父亲是否相同，记得最后要判断一下连通的边数是否大于等于结点-1，否则不能生成树。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int father[maxn];
struct node{
    int u,v,w;
}edge[maxn * maxn];
bool cmp(node A, node B){
    return A.w < B.w;
}
int findfather(int x){
    if(father[x] == x) return x;
    father[x] = findfather(father[x]);//路径压缩
    return father[x];
}
int main(){
    int city,road;
    while (cin>>road>>city){
        if (road == 0)
            break;
        for(int i = 1;i <= city;i++)
            father[i] = i;
        for(int i = 0;i < road;i++)
            cin>>edge[i].u>>edge[i].v>>edge[i].w;
        sort(edge,edge + road,cmp);
        int sum = 0;
        int total = 0;
        for(int i = 0;i < road;i++) {
            int father_1 = findfather(edge[i].u);
            int father_2 = findfather(edge[i].v);
            if (father_1 != father_2) {
                father[father_1] = father_2;
                sum += edge[i].w;
                total ++ ;
            }
        }
        if(total < city - 1)
            cout<<"?"<<endl;
        else
            cout<<sum<<endl;
    }
    return 0;
}

最短路径
最短路径的问题分为多源最短路径和单源最短路径，分别掌握一种算法应对机试足以。多源最短路径一般用floyd算法，思想就是不断比较i到j的原始距离和i到中间结点再到j的距离，如果后者大则更新。我们要注意floyd算法的时间复杂度为O(N^3)，要求图的结点不大于200个结点。

#include <iostream>
using namespace std;
int map[101][101];
int main(){
    int n,m;
    while (cin>>n>>m){
        if(n == 0 && m == 0)
            break;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                map[i][j] = -1;//表示无穷大
            }
            map[i][i] = 0;
        }
        for(int i = 0;i < m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            map[a][b] = map[b][a] = c;//领接矩阵赋初值
        }
        for(int i = 1;i <= n;i++){//中间结点
            for(int j = 1;j <= n;j++){
                for(int k = 1;k <= n;k++){
                    if(map[j][i] == -1 || map[i][k] == -1)//若有一值为无穷 则无法更新
                        continue;
                    if(map[j][k] == -1 || (map[j][i] + map[i][k] < map[j][k]))
                        map[j][k] = map[j][i] + map[i][k];
                }
            }
        }
        cout<<map[1][n]<<endl;
    }
    return 0;
}

而对于单源最短路径问题，一般使用迪杰斯特拉算法Dijkstra，他的思想是从起点开始，不断遍历邻接但未遍历过的点，进行松弛操作，要注意代码的各种初始化操作别漏了。

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
const int N = 105;
bool visit[N];//是否已经被选作为基点
int dis[N], pre[N];//分别存储每个点到起点的距离，pre就是最短路径上，这个点的前一个点
struct node{
    //p:边另一边的断点 w:权值
    int p, w;
    node(int a, int b):p(a), w(b){}
    bool operator < (const node& b) const
    {
        return w > b.w;
    }
};
vector<node> g[N];//邻接矩阵
priority_queue<node> sup;//距离优化队列
void dijkstra(int start)
{
    memset(dis, 0x3f, sizeof(dis));//初始化每个点为一个大数
    memset(visit, false, sizeof(visit));
    dis[start] = 0; //起点到起点的距离为0
    pre[start] = start;//第一次直接把起点标记为基点   起点的前一个点设置为本身
    sup.push(node(start, 0));
    while (!sup.empty())
    {
        node front = sup.top();
        sup.pop();
        int tempv = front.p;//基点
        if (visit[tempv]) continue;
        visit[tempv] = true;
        for (int i = 0; i < g[tempv].size(); i++)
        {
            //遍历所有邻接结点
            int p = g[tempv][i].p;
            if (!visit[p] && dis[tempv]+g[tempv][i].w < dis[p])
            {
                dis[p] = dis[tempv]+g[tempv][i].w;
                pre[p] = tempv;
                sup.push(node(p, dis[p]));
            }
        }
    }
}
int main(){
    int n,m;
    while (cin>>n>>m){
        if (n == 0 && m == 0)
            break;
        for(int i = 0;i <= n;i++)
            g[i].clear();
        for(int i = 0;i < m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            g[a].push_back(node{b,c});
            g[b].push_back(node{a,c});
        }
        dijkstra(1);
        cout<<dis[n]<<endl;
    }
    return 0;
}