图论

参考：(107条消息) 疯子的算法总结(八) 最短路算法+模板_风骨散人Chiam的博客-CSDN博客

• 蓝桥公园- 蓝桥云课 (lanqiao.cn)
• 蓝桥王国 - 蓝桥云课 (lanqiao.cn)
• 随机数据下的最短路问题 - 蓝桥云课 (lanqiao.cn)

图论的基本概念

• 图：由点(node，或者vertex)和连接点的边(edge)组成。

• 图是点和边构成的网。

图的应用背景

• 地图：路口、道路、过路费…

• 计算机网络：路由协议

• 人际关系：“六度空间理论”。世界上任意两个人，最多通过五个中间人就能联系到。把人看成点，人和人之间的关系看成边，这就是一个图的连通性问题。

树：特殊的图

• 树，即连通无环图

• 树的结点从根开始，层层扩展子树，是一种层次关系，这种层次关系，保证了树上不会出现环路。

• 两点之间的路径：有且仅有一条路径。

• 最近公共祖先。

图的种类

（1）无向无权图，边没有权值、没有方向；

（2）有向无权图，边有方向、无权值；

（3）加权无向图，边有权值，但没有方向；

（4）加权有向图；

（5）有向无环图（Directed Acyclic Graph，DAG）。

图算法的复杂度

和边的数量E、点的数量V相关：

• O(V+E)：几乎是图问题中能达到的最好程度。

• O(VlogE)、O(ElogV)：很好的算法。

• O(V2)、O(E2)或更高：不算是好的算法。

图的存储

能快速访问：图的存储，能让程序很快定位结点u和v的边(u, v) 。

• 数组存边：简单、空间使用最少；无法快递定位

• 邻接矩阵：简单、空间使用最大；定位最快 dis[a][b]

• 邻接表：空间很少，定位较快

• 链式前向星：空间更少，定位较快

数组存边

优点：简单、最省空间。

缺点：无法定位某条边。

应用：bellman-ford算法、最小生成树的kruskal算法

struct Edge{ int from,to,dis;}e[M]; //结构体数组存边
cin>>n>>m;
for(int i=1;i<=m;++i)        
	cin>>e[i].from>>e[i].to>>e[i].dis;

邻接矩阵

二维数组： graph[NUM ][NUM ]

无向图：graph[i][j] = graph[j][i]。

有向图：graph[i][j] != graph[j][i]。

权值：graph[i][j]存结点i到j的边的权值。例如graph[1][2] = 3，graph[2][1] = 5等等。用graph[i][j] = INF表示i，j之间无边。

优点：

• 适合稠密图；
• 编码非常简短；
• 对边的存储、查询、更新等操作又快又简单。

缺点：

• 存储复杂度O(V²)太高。V=10000时，空间100M。

• 不能存储重边。

邻接表和链式前向星

应用场景：大稀疏图。

优点：

• 存储效率非常高，存储复杂度O(V+E)；

• 能存储重边。

1、最短路问题

问题	边权	算法	时间复杂度
一个起点，一个终点	非负数； 无边权（或边权为1）	A*	< O((m+n)logn)
		双向广搜	< O((m+n)logn)
		贪心最优搜索	< O(m+n)
一个起点到其他所有点	无边权（或边权为1）	BFS	O(m+n)
	非负数	Dijkstra(堆优化优先队列)	O((m+n)logn)
	允许有负数	SPFA	< O(mn)
所有点对之间	允许有负数	Floyd-Warshall	O(n3)

Floyd算法（多源、负权值，能判负圈）

• 最简单的最短路径算法，代码仅有4行

• 存图：最简单的矩阵存图

• 易懂，比暴力的搜索更简单易懂。

• 效率不高，不能用于大图

• 在某些场景下有自己的优势，难以替代。能做传递闭包问题（离散数学)

for(int k=1; k<=n; k++)         //floyd的三重循环
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)      // k循环在i、j循环外面
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); 

Floyd的特点

• Floyd算法：“多源”最短路算法，一次计算能得到图中每一对结点之间（多对多）的最短路径。

• Dijkstra、Bellman-Ford、SPFA算法：“单源”最短路径算法（Single source shortest path algorithm），一次计算能得到一个起点到其他所有点（一对多）的最短路径。

• 在截止目前的蓝桥杯大赛中，Floyd算法是最常见的最短路径算法。

Floyd算法思想：动态规划

• 动态规划：求图上两点i、j之间的最短距离，按“从小图到全图”的步骤，在逐步扩大图的过程中计算和更新最短路。

• 定义状态：dp[k][i][j]，i、j、k是点的编号，范围1 ~ n。状态dp[k][i][j]表示在包含1 ~ k点的子图上，点对i、j之间的最短路。

• 状态转移方程：从子图1 ~ k-1扩展到子图1 ~ k

  • dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

计算过程：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

1. 虚线圆圈：包含1 ~ k-1点的子图。

2. dp[k-1][i][j]：虚线子图内的点对i、j的最短路；

3. dp[k-1][i][k] + dp[k-1][k][j]：经过k点的新路径的长度，即这条路径从i出发，先到k，再从k到终点j。

4. 比较：不经过k的最短路径dp[k-1][i][j]和经过k的新路径，较小者就是新的dp[k][i][j]。

5. k从1逐步扩展到n：最后得到的dp[n][i][j]是点对i、j之间的最短路径长度。

6. 初值dp[0][i][j]：若i、j是直连的，就是它们的边长；若不直连，赋值为无穷大。

7. i、j是任意点对：计算结束后得到了所有点对之间的最短路。

Floyd方程简化

原方程：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

用滚动数组简化： dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

for(int k=1; k<=n; k++)         //floyd的三重循环
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) // k循环在i、j循环外面
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                  //比较：不经过k、经过k

Floyd算法总结

（1）在一次计算后求得所有结点之间的最短距离。

（2）代码极其简单，是最简单的最短路算法。

（3）效率低下，计算复杂度是O(n³)，只能用于n < 300的小规模的图。

（4）存图用邻接矩阵dp[][]。因为Floyd算法计算的结果是所有点对之间的最短路，本身就需要n²的空间，用矩阵存储最合适。

（5）能判断负圈。

• 负圈：若图中有权值为负的边，某个经过这个负边的环路，所有边长相加的总长度也是负数，这就是负圈。在这个负圈上每绕一圈，总长度就更小，从而陷入在负圈上兜圈子的死循环。

• Floyd算法很容易判断负圈，只要在算法运行过程出现任意一个dp[i][i] < 0就说明有负圈。因为dp[i][i]是从i出发，经过其他中转点绕一圈回到自己的最短路径，如果小于零，就存在负圈。

Dijkstra算法（单源、权值为非负）

• Dijkstra：单源最短路径问题。

• 优点：非常高效而且稳定。

• 缺点：只能处理不含有负权边的图。

• 思路：贪心思想+优先队列。

Dijkstra算法思想

1. Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

2. 为什么是每次都是找最小的？

   • 因为最小边的不会被其它的点松弛，只有可能最小边去松弛别人。
   • 如果存在一个点K能够松弛ab的话那么一定有ak距离加上kb的距离小于ab,已知ab最短，所以不存在ak+kb<ab。

Dijkstra算法特点

1. Dijkstra算法应用了贪心法的思想，即“抄近路走，肯定能找到最短路径”。

2. 算法高效稳定：

   • Dijkstra的每次迭代，只需要检查上次已经确定最短路径的那些结点的邻居，检查范围很小，算法是高效的；
   • 每次迭代，都能得到至少一个结点的最短路径，算法是稳定的

使用优先队列

• 每次往队列中放新数据时，按从小到大的顺序放，采用小顶堆的方式，复杂度是O(logn)，保证最小的数总在最前面；

• 找最小值，直接取B的第一个数，复杂度是O(1)。

• 复杂度：用优先队列时，Dijkstra算法的复杂度是O(m*logn)，是最高效的最短路算法。

Dijkstra算法实现流程

维护两个集合：已确定最短路径的结点集合A、这些结点向外扩散的邻居结点集合B。

（1）把起点s放到A中，把s所有的邻居放到B中。此时，邻居到s的距离就是直连距离。

（2）从B中找出距离起点s最短的结点u，放到A中。

（3）把u所有的新邻居放到B中。显然，u的每一条边都连接了一个邻居，每个新邻居都要加进去。其中u的一个新邻居v，它到s的距离dis(s, v)等于dis(s, u) + dis(u, v)。

（4）重复(2)、(3)，直到B为空时，结束。

边权不能为负

• Dijkstra的局限性是边的权值不能为负数

• Dijkstra基于BFS，计算过程是从起点s逐步往外扩散的过程，每扩散一次就用贪心得到到一个点的最短路。

• 扩散要求路径越来越长，如果遇到一个负权边，会导致路径变短，使扩散失效。

Dijkstra模板算法：

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL; 
//这样定义INF的好处是: INF <= INF+x
const int N= 3e5+2;
struct edge{
    int from, to; long long w; //起点，终点，权值。起点from并没有用到，e[i]的i就是from
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];          //用于存储图
struct s_node{
    int id; long long n_dis;   //id：结点；n_dis：这个结点到起点的距离
    s_node(int b,long long c){id=b; n_dis=c;}
    bool operator < (const s_node & a) const
    { return n_dis > a.n_dis;}
};
int n,m;
int pre[N];                                //记录前驱结点，用于生成路径
void print_path(int s, int t) {            //打印从s到t的最短路
    if(s==t){ printf("%d ", s); return; }  //打印起点
    print_path(s, pre[t]);                 //先打印前一个点
    printf("%d ", t);                      //后打印当前点。最后打印的是终点t
}
long long  dis[N];         //记录所有结点到起点的距离
void dijkstra(){
    int s = 1;             //起点s是1
    bool done[N]; //done[i]=true表示到结点i的最短路径已经找到
    for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; }    //初始化
    dis[s]=0;                           //起点到自己的距离是0
    priority_queue <s_node> Q;          //优先队列，存结点信息
    Q.push(s_node(s, dis[s]));          //起点进队列
    while (!Q.empty())   {
        s_node u = Q.top();             //pop出距起点s距离最小的结点u
        Q.pop();
        if(done[u.id])  continue;       //丢弃已经找到最短路径的结点。即集合A中的结点            
        done[u.id]= true;
        for (int i=0; i<e[u.id].size(); i++) {  //检查结点u的所有邻居
            edge y = e[u.id][i];         //u.id的第i个邻居是y.to
            if(done[y.to])  continue;    //丢弃已经找到最短路径的邻居结点                
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                Q.push(s_node(y.to, dis[y.to]));  //扩展新的邻居，放到优先队列中
                pre[y.to]=u.id;  //如果有需要，记录路径
            }
        }
    }
    // print_path(s,n);          //如果有需要，打印路径: 起点1，终点n
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)    e[i].clear();// 清除可能存在的元素
    while (m--) {
        int u,v,w;  scanf("%d%d%lld",&u,&v,&w);
        e[u].push_back(edge(u,v,w));
     // e[v].push_back(edge(v,u,w));    //本题是单向道路
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]>=INF)  cout<<"-1 ";
        else   printf("%lld ", dis[i]);
    }
}

Bellman-ford算法（负权值、负圈）

• 单源最短路径问题：给定一个起点s，求它到图中所有n个结点的最短路径。

Bellman-ford算法思想

• 图中每个点上站着一个“警察”。

• 每个警察问邻居：走你这条路能到s吗？有多远？

• 反复问多次，最后所有警察都能得到最短路。

“问路”流程：

-第1轮，给所有n个人每人一次机会，问他的邻居，到s的最短距离是多少？

• 更新每人到s的最短距离。

• 特别地，在s的直连邻居中，有个t，得到了到s的最短距离。（注意，算法并没有查找是哪个t）

-第2轮，重复第1轮的操作。

• 更新每人到s的最短距离。

• 特别地，在s和t的直连邻居中，有个v，得到了到s的最短距离。

-第3轮，……

Bellman-ford算法复杂度

• 一共需要几轮操作？每一轮操作，都至少有一个新的结点得到了到s的最短路径。所以，最多只需要n轮操作，就能完成n个结点。

• 在每一轮操作中，需要检查所有m个边，更新最短距离。

• Bellman-Ford算法的复杂度：O(n*m)。

判断负圈

• Bellman-Ford能判断负圈。

• 没有负圈时，只需要n轮就结束。

• 如果超过n轮，最短路径还有变化，那么肯定有负圈。

SPFA算法：改进的Bellman-Ford（负权值、无负圈）

• SPFA = 队列处理+Bellman-Ford。

• Bellman-Ford算法有很多低效或无效的操作。其核心内容，是在每一轮操作中，更新所有结点到起点s的最短距离。

• 计算和调整一个结点u到s的最短距离后，如果紧接着调整u的邻居结点，这些邻居肯定有新的计算结果；而如果漫无目的地计算不与u相邻的结点，很可能毫无变化，所以这些操作是低效的。

• 改进：计算结点u之后，下一步只计算和调整它的邻居，能加快收敛的过程。

• 这些步骤用队列进行操作，这就是SPFA。

SPFA算法步骤

（1）起点s入队，计算它所有邻居到s的最短距离。把s出队，状态有更新的邻居入队，没更新的不入队。

（2）现在队列的头部是s的一个邻居u。弹出u，更新它所有邻居的状态，把其中有状态变化的邻居入队列。

（3）继续以上过程，直到队列空。这也意味着，所有结点的状态都不再更新。最后的状态就是到起点s的最短路径。

SPFA算法复杂度是不稳定的

• 弹出u之后，在后面的计算中，u可能会再次更新状态（后来发现，u借道别的结点去s，路更近）。所以，u可能需要重新入队列。

• 有可能只有很少结点重新进入队列，也有可能很多。这取决于图的特征。

• 所以，SPFA是不稳定的。

SPFA模板算法：

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3+10;
struct edge{
    int to;    long long w;
    edge(int tt,long long ww) {to = tt; w = ww;}
};
long long dist[N];
int inq[N];// 标记点i在队列中
vector<edge> e[N];
void spfa(int s){// s为起点
    memset(dist,0x3f,sizeof(dist));// 0x3f等价于INF
    dist[s] = 0;      //起点到自己的距离是0
    queue<int> q;
    q.push(s);        //从s开始，s进队列
    inq[s] = 1;       //起点在队列中
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;   //u已经不在队列中
        if(dist[u] == INF)     continue;
        for(int i = 0;i < e[u].size();i++) {   //遍历u的邻居
            int v = e[u][i].to;
            long long w = e[u][i].w;
            if(dist[v] > dist[u]+w) {         //u的第i个邻居v，它借道u，到s更近
                dist[v] = dist[u]+w;          //更新邻居v到s的距离
                if(!inq[v]) {      //邻居v更新状态了，但v不在队列中，放进队列
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
}
int main(){
    int n,m,s;cin>>n>>m>>s;
    for(int i = 1;i <= m;i++)    {
        int u,v; long long w;
        cin>>u>>v>>w;
        e[u].push_back(edge(v,w));
    }
    spfa(s);
    for(int i = 1;i <= n;i++) {
        if(dist[i]==INF)  cout << -1;
        else              cout << dist[i];
        if(i != n)        cout << " ";
        else              cout << endl;
    }
    return 0;
}

总结☀️

• Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)

• BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)

• SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).

• Floyd：每对节点之间的最短路径，负权值，能判断负圈。

单源最短路使用：

(1)当权值为非负时，用Dijkstra。

(2)当权值有负值，且没有负圈，则用SPFA。SPFA能检测负圈，但是不能输出负圈。

(3)当权值有负值，而且可能存在负圈需要输出，则用BellmanFord。能够检测并输出负圈。

多源最短路使用：Floyd（负权值，能判断负圈）

最小生成树

• 在无向图中，连通而且不含有圈（环路）的图，称为树。

• 最小生成树MST：一个有 n 个结点的连通图的生成树是原图的极小连通子图，包含原图中的所有 n 个结点，并且边的权值之和最小。

基于贪心的两种算法

（1）Prim算法。对点进行贪心操作：“最近的邻居一定在MST上”。

从任意一个点u开始，把距离它最近的点v加入到MST中；下一步，把距离{u, v}最近的点w加入到MST中；继续这个过程，直到所有点都在MST中。

（2）kruskal算法。对边进行贪心操作：“最短的边一定在MST上”。

从最短的边开始，把它加入到MST中；在剩下的边中找最短的边，加入到MST中；继续这个过程，直到所有点都在MST中。

kruskal算法

kruskal算法的2个关键技术：

（1）对边进行排序。

（2）判断圈，即处理连通性问题。这个问题用并查集简单而高效，并查集是kruskal算法的绝配。

kruskal算法步骤

（1）初始时最小生成树T为空。令S是以结点i为元素的并查集，开始的时候，每个点属于独立的集。

（2）加入第一个最短边(1-2)：T={1-2}。并查集S中，把结点2合并到结点1，也就是把结点2的集2改成结点1的集1。

（3）加入第二个最短边(3-4)：T={1-2, 3-4}。并查集S中，结点4合并到结点3。

（4）加入第三个最短边(2-5)：T={1-2, 3-4, 2-5}。并查集S中，把结点5合并到结点2，也就是把结点5的集5改成结点2的集1。在集1中，所有结点都指向了根结点，这样做能避免并查集的长链问题。即使用了“路径压缩”的方法。

（5）第四个最短边(1-5)。检查并查集S，发现5已经属于集1，丢弃这个边。这一步实际上是发现了一个圈。并查集的作用就体现在这里。

（6）加入第五个最短边(2-4)。并查集S中，把结点4的集并到结点2的集。注意这里结点4原来属于集3，实际上修改的是：把结点3的集3改成1。

kruskal算法复杂度

• kruskal算法的复杂度包括两部分：对边的排序O(ElogE)，并查集的操作O(E)，一共是O(ElogE + E)，约等于O(ElogE)，时间主要花在排序上。

• 如果图的边很多，kruskal的复杂度要差一些。

• kruskal适用于稀疏图，prim适合稠密图。

Kruskal算法结合并查集代码：（以下代码能通过示例，但是无法AC，可能存在问题）

#include<bits/stdc++.h>
using namespace std;
// 聪明的猴子——Kruskal算法与并查集得到最小生成树 
const int N = 5e3+10;
const int NN = 1e6+10;
struct edge{
	int u, v;// 起点与终点 
	double w;// 两点之间的距离 
}; 

edge eg[N];
int monkey[NN], x[N], y[N];// 分别为猴子的跳跃能力、树的x坐标与y坐标(方便求两树之间的距离w) 
int parent[N];// 存储结点的父节点，并查集
int m, n; // 猴子的个数、树的棵树 

bool comp(edge a, edge b){// 根据w升序排序 
	return a.w<b.w;
}

// 并查集
int find(int x){// 查找根节点 
	if(x!=parent[x]){
		parent[x] = find(parent[x]);
	}
	return parent[x];
} 

void merge(int x, int y){// 合并集合——连接x与y的根节点 
	int xx = find(x);
	int yy = find(y);
	if(xx!=yy)parent[yy] = xx;// yy为新的根节点 
}

int main() {
	cin>>m;
	for(int i=1;i<=m;++i)cin>>monkey[i];
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x[i]>>y[i];
	}
	// 构建图结构
	int cnt = 0;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){// 避免重复计算距离 
			double w = sqrt(pow((x[i]-x[j]), 2)+pow((y[i]-y[j]), 2));// 计算距离
			eg[++cnt] = {i, j, w};// 初始化边数组 
		} 
	} 
	sort(eg+1, eg+1+cnt, comp);// 按照边权重升序排序 
	// 计算最小生成树以及MST中的最大边权重 
	for(int i=1;i<=n;++i){
		parent[i] = i;// 初始化根节点为本身 
	}
	int num = 0;// 存储最小生成树中结点的个数 
	double maxE = 0.0;// 存储MST中边权重的最大值 
	for(int i=1;i<=cnt;++i){// 遍历所有的边edge 
		if(find(eg[i].u)!=find(eg[i].v)){// 两个结点不具有相同的根节点 
			merge(eg[i].u, eg[i].v);// 合并
			num++;// 结点数量增加
			maxE = maxE>=eg[i].w?maxE:eg[i].w;// 更新MST中边的最大权重 
		}
		if(num==n-1)break;// n个结点组成MST之后只有n-1条边 
	} 
	int ans = 0;
	for(int i=1;i<=m;++i){
		if(monkey[i]>=maxE)ans++;// 满足要求的猴子数量+1 
	} 
	cout<<ans;
	return 0;
}

⭐️编码提示

0x3f

• 在代码中，0x3f经常被用作一个特殊的数值，比如在动态规划中，可以将dp数组初始化为0x3f，表示还没有任何状态值被更新过，相当于无限大的意思。(0x3f的十进制数为63)

• memset(dp, 0x3f, sizeof(dp));//初始化

• 对于八进制数，前缀通常是“0o”或“0”，但后者已经很少使用了。这个前缀中的“o”代表“octal”，意思是“八进制”的意思。

• 而对于十六进制数，前缀通常是“0x”。这个前缀中的“x”代表“hexadecimal”，意思是“十六进制”的意思。

INF

• 定义无穷大

• const long long INF = 0x3f3f3f3f3f3f3f3fLL; //这样定义INF的好处是: INF <= INF+x 防止溢出