图论

· · 算法·理论

1.部分定义

(1)完全图：每个顶点都与其他点连边。

(2)稀疏图：边数远小于n(n-1)/2或小于nlog(n)

(3)稠密图：边的数量多，接近完全图。

2.图的连通性

(1)连通图：任意两个顶点之间都存在路径

(2)连通分量：无向图的极大连通子图

3.图的存储

(1)邻接矩阵：定义n*n的二维数组,g[i][j]!=0代表有边相连，g[i][j]=0代表无边。缺陷：存储稀疏图时浪费空间，无法储存带自环和重边的图。

(2)邻接表：

方法一：vector（个人常用） 无向有权图：对结构体使用vector。

方法二：链式前向星

struct node{
    int nxt;v,w
    int to;
    int w;
}edge[length];

其中，edge[i].to表示第i条边的终点，edge[i].nxt表示与第i条边同起点的下一条边的存在位置，edge[i].w表示第i条边的权值，每个顶点都会有一个头指针head[j]用于储存以顶点j建立链表开始的边位置。

4.最短路

(1)dijkstra

本质：维护一个已找到最短路的点集，在这个点集中，每次找离起点最近的点，看这个点所连的点能否通过与这个点连边而使当前的最短路更短。如果能的话加入已找到的点集，等待后续更新。

适用问题：单源最短路（没法有负边权，因为基于贪心）

代码：

#include <bits/stdc++.h>
using namespace std;
int n;
struct node{
    int to,dis;
};
vector<node> v[100005];
int dist[10005];
int m;
int main(){
    cin>>n>>m;
    memset(dist,10000,sizeof(dist));
    dist[1]=0;
    for (int i=1;i<=m;i++){
        int d1,d2,ds;
        cin>>d1>>d2>>ds;
        v[d1].push_back({d2,ds});
        v[d2].push_back({d1,ds});
    }
    priority_queue<pair<int,int>> q;
    q.push({0,1});
    while (!q.empty()){
        auto nd=q.top();
        q.pop();
        int mdis=-nd.first;
        int pos=nd.second;
        for (int i=0;i<v[pos].size();i++){
            node tos=v[pos][i];
            int di=tos.dis;
            int td=tos.to;
            if (mdis+di<=dist[td]){
                dist[td]=di+mdis;
                q.push({-dist[td],td});
            }
        }
    }
    for (int i=2;i<=n;i++){
        cout<<dist[i]<<" ";
    }
}

(2)SPFA(Bellman-Ford)

因为两种做法本质上一样，SPFA是Bellman-Ford的优化，所以只记录SPFA。

首先定义松弛操作：如果dis_u+w<dis_v ,那么dis_v 更新为 dis_u+w，这被称为一次“松弛”操作。

如果对所有边进行一次“松弛”操作，那么整张图中每一个点距离其真正的最短路都会靠近。

考虑每个点之间最短路的最大值，发现途径的边数绝对不会过 n ，所以只需要对整张图松弛 n 次即可求出最短路。

容易发现，一共有 n 轮松弛，每次松弛 m 条边，所以复杂度为 O(nm) 。

适用问题：单源最短路（可以有负边权），但是耗时间，慎用，容易被卡常。

代码：

#include <bits/stdc++.h>
using namespace std;
struct node{
    int to,jz;
};
int n,m,s;
int dis[100005];
vector<node> mp[100005];
int main(){
    cin>>n>>m>>s;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        node sp;
        sp.to=v;
        sp.jz=w;
        mp[u].push_back(sp);
    }
    memset(dis,0x3f3f3f3f,sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s]=0;
    while (!q.empty()){
        int p=q.front();
        q.pop();
        for (int index=0;index<mp[p].size();index++){
            if (dis[p]+mp[p][index].jz<dis[mp[p][index].to]){
                dis[mp[p][index].to]=dis[p]+mp[p][index].jz;
                q.push(mp[p][index].to);
            }
        }
    }
    for (int i=1;i<=n;i++){
        if (dis[i]!=0x3f3f3f3f)cout<<dis[i]<<" ";
        else{
            cout<<1024*1024*1024*2-1<<" ";
        }
    }
    return 0;
}

(3)Floyd算法

Floyd算法本质是动态规划。

我们设 dp[k][i][j] 表示图中顶点 v_i 到 v_j 只使用 v_1、v_2......v_k 作为中间节点集合时的最短路径长度。

状态 dp[k-1][i][j] 到状态 dp[k][i][j] 的转换，按顶点 v_i 到 v_j 的最短路径是否经过 v_k 分为两种情况：

1.最短路径不经过 k ，那么 dp[k][i][j]=dp[k-1][i][j] 。

2.最短路径经过 k ，显然一定有 dp[k][i][j]<dp[k-1][i][j] ，并且 dp[k][i][j]=dp[k-1][i][k]+dp[k-1][k+1][j] 。

所以转移方程如下：dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k+1][j]) 。

额外的，可以仿照动态规划的优化思想，将三维压缩成二维。

此时的转移方程：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) 。

适用问题：全源最短路

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v[105];
int dp[105][105][105];
int n,m;
signed main(){
    cin>>n>>m;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for (int i=1;i<=m;i++){
        int u,v1,w;
        cin>>u>>v1>>w;
        dp[0][u][v1]=min(dp[0][u][v1],w);
        dp[0][v1][u]=min(dp[0][v1][u],w);
        v[u].push_back(v1);
        v[v1].push_back(u);
    }
    for (int i=1;i<=n;i++){
        for (int k=0;k<=n;k++){
            dp[k][i][i]=0;
        }
    }
    //注意转移顺序，k需要在最外层枚举，因为dp[k][i][j]需要通过dp[k-1][i][j]推导。
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
            if (i==j) continue;
                dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            cout<<dp[n][i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}