图论算法 | 北海の小站

0x01 Dijkstra算法（寻找有权图最短路径）

看视频的讲解实现的，P4（视频地址）

这里默认源点是1，之后再改改自定义源点的，

这个算法的大致思路是，从一个源点开始，把他压入优先队列（小的先出），然后给存储最短路径的dis数组全部初始化无穷大，接着就可以开始循环了。只要队列不为空，我们就一直取队列里的元素，然后判断由这个节点到下个节点的路径是不是最小的，如果是就把下个节点压入队列，若不是就不压入。每个节点到源点的最短路径是递归而来的。

算法就是一直在完善这个表。由于有优先队列存在，省去了无意义的路线判断，很大程度上一次就可以寻得最短路径，因为是从小权重的边开始寻路的。

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF = 0x7fffffff;
int m,n;//m是边权方向设定数，n是顶点数
int x,y,w,temp_n,temp_w;//顶点坐标xy，边权数w
int mat[100][100];
int dis[100];
class info{
    public:
        info(int node, int weight){
            this->node = node;
		    this->weight = weight;
        }
        friend bool operator<(const info &info1, const info &info2){
            return info1.weight > info2.weight;
        }
        int node;
        int weight;
};
priority_queue<info> q;
//求从源点1到各个顶点的最短路径
void Dijkstra(int n){
    //初始化操作，dis初始化
    dis[1] = 0;
    for(int i=2;i<=n;i++){
        dis[i] = INF;
    }
    q.emplace(1,dis[1]);//源点进入队列
    while(!q.empty()){
        temp_n = q.top().node, temp_w = q.top().weight;
        q.pop();
        for(int i=1;i<=n;i++){    
            if(mat[temp_n][i] != INF && temp_n != i){
                if(temp_w + mat[temp_n][i] < dis[i]){
                    dis[i] = temp_w + mat[temp_n][i];
                    q.emplace(i,dis[i]);
                }  
            }             
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j){
                mat[i][j] = 0;
            }
            else{
                mat[i][j] = INF;
            }
        }
    }
    for(int i=1;i<=m;i++){
        cin >> x >> y >> w;
        mat[x][y] = w;//由x指向y，边权为w
    }
    Dijkstra(n);
    for(int i=1;i<=n;i++){
        cout << dis[i] << " ";
    }
    return 0;   
}

0x03 Prim算法（寻找最小生成树）

首先记录一下什么是生成树，生成树是在一个连通的，无回环的无向图中，寻找能构成树的节点和边。

n个节点的图中，生成树必须是n个节点，n-1条边的。

最小生成树就是生成树中边权重之和最小的数。

最小生成树简单的应用在于修路问题，在原有的道路的基础上，铺设新的道路，最省钱，又能全部连通，这时候就要用到最小生成树了。

先记录一下Prim算法，算法的大致思路就是从一个源点开始，将他标记为树的节点，然后从树与剩余图连接的边中选择权重最小的边，将与该边连接的节点也纳入树中，以此类推，知道全部节点都成为树的一部分。

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF = 0x7fffffff;
int m,n;//m是边权方向设定数，n是顶点数
int x,y,w,ans = 0,temp_w,temp_n;//顶点坐标xy，边权数w
//temp_w暂时存储边权，temp_n暂时存储节点
int mat[100][100];
int dis[100];//存储某个节点到树的距离
bool book[100];
void Prim(int n){
    dis[1] = 0;
    book[1] = true;
    for(int i=2;i<=n;i++){//初始化dis
        dis[i] = min(dis[i], mat[1][i]);//只有结点1的数，初始化设定到1的距离
    }
    for(int i = 2;i<=n;i++){
        temp_w = INF, temp_n = -1;
        for(int j=2;j<=n;j++){
            if(!book[j] && dis[j] < temp_w){
                //找到离树边权最小的节点
                temp_n = j, temp_w = dis[j];
            }
        }
        if(temp_n == -1){//若为-1，代表找不到节点，无法构成树
            ans = INF;
            return;
        }
        book[temp_n] = true;//找到后把节点纳入树中
        ans += temp_w;//计算边权和
        for(int j=2;j<=n;j++){//更新节点离树的边权，未被访问到的节点dis为INF
            dis[j] = min(dis[j], mat[temp_n][j]);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j){
                mat[i][j] = 0;
            }
            else{
                mat[i][j] = INF;
            }
            dis[i] = INF;//给dis全设置为正无穷
        }
    }
    for(int i=1;i<=m;i++){
        cin >> x >> y >> w;
        mat[x][y] = mat[y][x] = w;
    }
    Prim(n);
    cout << ans;
    return 0;  
  
}

0x04 Kruskal算法（寻找最小生成树）

Kruskal算法的和Prim算法的区别在于，他的核心点在于边和森林。一开始把图看成一个森林，然后选取边权最小的边事先合并，逐渐把森林连接成树。

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
class edge{//边类
    public:
        edge(int x,int y,int w){
            this->w = w, this->x = x, this->y = y;
        }
        int x,y,w;
};
bool cmp(edge &p1, edge &p2){//sort判断函数重载
    if(p1.w < p2.w){
        return true;
    }
    return false;
}
int n, m, x, y, w, ans=0, cnt=0;
vector<edge> T;//边容器T
vector<int> tree;//下标代表节点，值代表树
//比如tree[1] = 1, tree[2] = 1,说明节点1和节点2在同一颗树内，初始每个节点在不同树内
void Kruskal(int n){
    sort(T.begin(),T.end(),cmp);//根据边权排序，从小到大
    for(int i=0;i<=n;i++){//tree初始化
        tree.push_back(i);
    }
    for(int i=1;i<=m;i++){//遍历m条边
        if(tree[T[i].x] != tree[T[i].y]){//若不在同一树内
            ans += T[i].w;
            cnt++;
            for(int j=1;j<=n;j++){//遍历节点修改节点所属的树
                if(tree[j] == tree[T[i].y]){
                    tree[j] = tree[T[i].x];
                }
            }
        }
    }
    if(cnt != n-1){//如果构不成树
		cout << "error";
        ans = 0;
        return;
    }
}
    
int main(){
    cin >> n >> m;
    //由于这个算法主要是分析边的，这里就不读取mat了
    T.emplace_back(0,0,0);//占0下标，方便从1开始循环
    for(int i=1;i<=m;i++){
        //读取图的边
        cin >> x >> y >> w;
        T.emplace_back(x,y,w);
    }
    Kruskal(n);
    cout << ans;
    return 0;  
  
}

并查集优化

写完这个算法后，询问了一下大佬的意见，连接树这一部分可以用并查集算法优化。

同样设置一个tree数组，tree下标代表节点，这时候值则代表节点的双亲节点（parents[ ]）。

例如 tree[1] = 2，说明节点1往上查找是节点2。当数组值等于数组下标时，说明该节点是其所属树的根结点，因为无法再溯源了，很好理解（自己的双亲节点是自己，就是没有了）。

这时候查找一个节点的所属树时，只要找到他的根结点，跟另一个节点的根节点比较，若相同则说明两者有同一祖宗，不相等则不是，这时候把其中任意根结点的值改成另一根结点的值，使得两者有共同祖宗，就所属同一棵树了。

int find(int x){
    if(x != parents[x]){
        return find(parents[x]);
    }
    return x;
}

这个算法中，若该节点x不是根结点，继续回溯，判断x的双亲节点是不是根结点，直到找到后返回根结点。

虽然这个算法满足了回溯找祖宗的功能，但没有在过去的查找中逐渐优化树，让下一次的查找无需多次return。

如果能在每次查找中优化树结构，让本来由1 -> 2 -> 3 的树，变成1 -> 3 ，2 -> 3，的少层多孩子的树，能大大减少查找的时间，使得1无需经过两次回溯才能找到根节点。

int find(int x){
    if(x != parents[x]){
        parents[x] = find(parents[x]);
    }   
    return parents[x];
}

每次查找失败后，将双亲节点的值赋值为祖宗节点。

这里顺便把sort排序用于判断的小于号重载并用友元全局函数封装进edge类内，让整体感更强。

优化后的算法如下：

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
class edge{//边类
    public:
        edge(int x,int y,int w){
            this->w = w, this->x = x, this->y = y;
        }
        friend bool operator<(const edge &edge1,const edge &edge2){//重载小于号，方便sort排序
            return edge1.w < edge2.w;
        }
        int x,y,w;
};
int n, m, x, y, w, ans=0, cnt=0;
vector<edge> T;//边容器T
vector<int> parents;//下标代表节点，值代表双亲节点
int find(int x){
    if(x != parents[x]){
        parents[x] = find(parents[x]);
    }   
    return parents[x];
}
void Kruskal(int n){
    sort(T.begin(),T.end());//根据边权排序，从小到大
    for(int i=0;i<=n;i++){//tree初始化
        parents.push_back(i);
    }
    for(int i=1;i<=m;i++){//遍历m条边
        x = find(T[i].x), y = find(T[i].y);
        if(x != y){//若不在同一树内
            parents[x] = y;
            ans += T[i].w;
            cnt++;
        }
    }
    if(cnt != n-1){//如果构不成树
		cout << "error";
        ans = 0;
        return;
    }
}
    
int main(){
    cin >> n >> m;
    //由于这个算法主要是分析边的，这里就不读取mat了
    T.emplace_back(0,0,0);//占0下标，方便从1开始循环
    for(int i=1;i<=m;i++){
        //读取图的边
        cin >> x >> y >> w;
        T.emplace_back(x,y,w);
    }
    Kruskal(n);
    cout << ans;
    return 0;  
}

0x05 网络流问题Nework Flow

如图就是一个经典网络流问题，从起点S出发，流量不超过最大容量（边权），最多能有多少流量到终点T。

这里先介绍一种基础的计算网络流的办法，这种办法算出来不一定正确。

先找到一条从S到T的简单路径，然后各种短板效应找到通过该路径的最大流量，接着用容量减去流量计算出空闲量，更新上面的空闲量图

更新后如图，继续寻找从S到T的简单路径，直到找不到从S到T的路径。

这个算法当选择路径的顺序正确时，能够计算出最大流量，但多数时候路径的选择顺序是不固定的，选择的不是最优解也无法回头再来。

0x06 Ford-Fulkerson算法

这个算法一定能找到最大流，介绍一下大致思想，为下一个E-K算法做铺垫。

先创建一个residual graph，然后开始循环找从起点到终点的简单路径，和上节介绍的方法一样，但是在每次更新得到residual graph后，在原先的Flow上添加一条方向路径（如图绿色）

这条反向路径的在之后寻找从起点到终点的简单路径时是可以选择的，他的存在使得Flow的选择能够反悔，例如图中从S到T流向了三份水后，添加的反向路径使得水能够动态的从T流回S，之后若选择的路径通过的Flow不好，也可以通过反向路径流动水，一来一回相当于水没流动，修改路径上水的Flow。

时间复杂度

但是F-F算法选择路径的方式是随机的，最坏的情况下时间复杂度为O(f*m)（f是最大流量，m是边的数量）

O(m)用来寻找从起点到终点的路径，O(f)则是最坏情况下的循环找路径次数。

0x07 Edmonds-Karp算法（F-F算法特例）

基于F-F算法，E-K算法在寻找路径时添加了一条规则，优先选择最短路径（把图看成有向无权图）

最坏情况下时间复杂度为O(m m n)，时间复杂度与最大流无关（m是边的数量，n是节点数）

代码实现思路

先写一个无权图的最短路径BFS算法，根据这个算法，遍历每个节点，记录到源点的最短路径，节点的前驱节点，并且在计算的过程中，更新当前路径的最大容量。思路是先设置一个info节点类，维护节点编号、最短路径和前驱节点，然后设置一个mat图二维数组，存储residual图（初始是有向容量图），维护着图的各种路径，方向路径等。（邻接矩阵法）

先贴个网址，以后再补：最大流问题——Ford Fulkerson算法_fordfulkerson算法求最大流-CSDN博客

三种网络流（最大流）的实现算法讲解与代码 - Icys - 博客园 (cnblogs.com)

完结撒花，已经补全了，真是道阻且长！！

这里用的是新的链式前向星存储图的思路，重点在于找到最短路径并计算最大Flow这个操作，该算法巧妙的用一个数组last存储指向某个节点的边的编号，再通过反向路径编号=正向路径编号+1的存取方式，将正反向路径的to（指向的节点编号）联动起来，成功实现溯源，遍历路径节点的同时修改边权（边的容量剩余量）的操作，我觉得很妙，思路主要来源于第二篇文章。

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
class Edge{
    public:
        Edge(int to,int w,int next){
            //Next，表示与这个边起点相同的上一条边的编号
            //to，表示边指向的节点，w是边权（容量）
            this->next = next, this->to = to, this->w = w;
        }
        int to,w,next;
};
vector<Edge> edge;
int cnt = 1,head[100];//初始化-1
int n,m,x,y,w,s,t,INF = 0x7fffffff;
int last[100],flow[100];//last记录从S到T的完整路径，flow记录到该节点的流量

void add_edge(int u,int v,int w){//u起点，v终点，w边权
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];//以u为起点最后一条边的编号，也就是与这个边起点相同的上一条边的编号
    //这时候edge[cnt]变成以u起点的最后一条边，存储进head，然后cnt++
    head[u] = cnt++;
}    

void init(int m){//初始化head，m代表边数
    for(int i=1;i<=m;i++){
        head[i] = -1;
    }
}

bool bfs(int s,int t,int n){//搜索从s到t的最短路径，找出最小容量，并生成一个last数组供查询
    int temp_n,dis[100];//dis用来寻找最短路径
    bool vis[100] = {false};//各点访问情况
    queue<int> q;
    for(int i=1;i<=n;i++){
        dis[i] = INF;//初始化INF
        last[i] = -1;
    }
    dis[s] = 0;
    q.push(s);
    flow[s] = INF;
    while(!q.empty()){
        temp_n = q.front();
        q.pop();
        if(temp_n == t){
            break;//找到终点t了，直接break
        }
        for(int i=head[temp_n];i!=-1;i=edge[i].next){
            if(!vis[edge[i].to] && edge[i].w>0){//节点未有水流过，且到达节点的边的容量不为0
                dis[edge[i].to] = dis[temp_n] + 1;//更新未访问过的点的路径（这里用不到，找最短路径用）
                last[edge[i].to] = i;//到edge[i].to这个点要走边i
                flow[edge[i].to] = min(flow[temp_n],edge[i].w);//记录当前节点的水量
                vis[edge[i].to] = true;//表示访问过
                q.push(edge[i].to);//入栈
            }
        }
    }
    return last[t]!=-1;//找到s到t的路径就返回true
}   
int max_flow(){
    int maxflow = 0;
    while(bfs(s,t,n)){
        maxflow += flow[t];
        for(int i=t;i!=s;i = edge[last[i]+1].to){//这个last[i]得到路径里指向i的边的编号，然后编号+1得到反向边，
        //接着取这条边的to，就是找到指向结点i的边的起点，这样一步步反向回溯路径直到起点s
            edge[last[i]].w -= flow[t];//减去流量得到边的容量剩余量
            edge[last[i]+1].w += flow[t];//添加反向路径
        }
    }
    return maxflow;
}


int main(){
    cin >> n >> m;
    edge.resize(100,Edge(0,0,0));
    init(m);//初始化head
    cin >> s >> t;//记录起点到终点
    for(int i=1;i<=m;i++){
        cin >> x >> y >> w;
        add_edge(x,y,w);//添加正向边，编号为奇数
        add_edge(y,x,0);//添加初始容量为0的反向边，编号是偶数
    }
    cout<< max_flow();

    return 0;  
}

0x08 Dinic’s算法（有点复杂但更快）

关键在于blocking graph，level graph和residual graph

该算法引入了level graph层级图这个概念，先记录一下层级图

Level Graph

层级图的构建，从起点S开始，能从S一步到达的节点为一层，从一层节点一步到达的节点为二层节点（访问过的节点不算），直到访问到终点T。

Blocking Graph

阻流图，其实就是0x05节介绍简单网络流问时，用于初步解决的简单算法得到的Flow graph，不一定是最大流，只要是把通往终点T的容量全部填满就好了。（在d算法中，阻塞流计算用于level graph）

Dinic’s算法流程

算法需要准备一个residual graph，每次循环都根据residual graph更新level graph，然后再在residual graph中减去level graph中的阻塞流，得到新的residual graph，然后再在residual中添加反向路径（和F-F算法中的思路一样），反向路径也算实际存在的路径，用于level graph的构建，一直循环知道level graph没法构建，算法就结束，这时候用Original graph（原图）的，和起点S相连边的容量减去它的residual（空闲量），就能得到最大流量。（公式：Original - Residual = Flow）

0x09 图的存储

邻接矩阵

邻接矩阵矩阵属于是好写但效率低的存储方式，挺实用的数据结构。

建立一个二维数组mat[x] [y]，表示x -> y，权值为数组mat的值weight，例如节点1到节点2的边权值为5，记为mat[1] [2] = 5。很好理解。

链式前向星

链式前向星的存储主体是边，是以【1，n】为起点的边的集合，例如将以1为起点的边的集合放在一起：

1：1 5 6，1 3 4，1 2 1，2： 2 3 2 …………

知道这个后，得先了解几个变量的含义：

Next，表示与这个边起点相同的上一条边的编号。

head[ i ]数组，表示以 i 为起点的最后一条边的编号（一般初始化为-1）。

cnt，用来记录边的编号（我习惯从1开始）

class Edge{
    public:
        Edge(int to,int w,int next){
            //Next，表示与这个边起点相同的上一条边的编号
            //to，表示边指向的节点，w是边权
            this->next = next, this->to = to, this->w = w;
        }
        int to,w,next;
};
vector<Edge> edge;
int cnt = 1,head[100];//初始化-1
void add_edge(int u,int v,int w){//u起点，v终点，w边权
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];//以u为起点最后一条边的编号，也就是与这个边起点相同的上一条边的编号
    //这时候edge[cnt]变成以u起点的最后一条边，存储进head，然后cnt++
    head[u] = cnt++;
}    
void init(int m){//初始化head，m代表边数
    for(int i=1;i<=m;i++){
        head[m] = -1;
    }
    edge.resize(100,Edge(0,0,0));//这里容器edge也要初始化一下
}