---

前言

本帖子有一点长，请耐心看完。
练习会有一些来自其他网站的题目，如洛谷，没有账号的用户可以注册一下，或者只是看看题面有一个可行的思路即可。

实际上作者蛮喜欢图论的，感觉图论比动态规划简单（虽然有时候图论也要用到动态规划），动态规划还得自己动脑筋去推状态转移方程式，更要考虑到每个点的初始化，甚至于有时候会把贪心题目误判为动态规划题，我2025年CSP-S复赛的T1就是这样错的，可谓“一步错步步错”。

好久没发创作计划了，那么就先把之前写过一部分的图论算法合集补充完整。
正好赶上主要提供Python语法练习的ACGO嘻哈赛#1前后，也考虑到有部分学习Python的小伙伴也在ACGO刷题练习，在此也给出Python版本对应算法的代码。

文末有符号解释

---

正文

这个帖子是图论算法的合集，你会看到：

• 图的存储
• 图的遍历
• 并查集
• 最小生成树
• 最短路
• 拓扑排序

---

图的存储

图的存储分为两种：邻接表和邻接矩阵

邻接矩阵存图：

邻接矩阵存图思想很简单：
对于无权图，如果 $i$ 和 $j$ 有一条边相连，那么 $graph[i][j]=1$，否则 $graph[i][j]=0$
对于有权图，如果 $i$ 和 $j$ 有一条权值为 $k$ 的边相连，则 $graph[i][j]=k$，否则 $graph[i][j]=\infty$
【注意】，这里有权图中之所以设置为 $\infty$，一是因为防止出现边权为 $0$ 甚至于负数的情况，而是因为有些算法设置为 $\infty$ 比设置为 $0$ 更利于后面去操作，三是因为一本通上面是这样写的，当然，如果题目中明确说明边权不为 $0$，那么你设它是 $\infty$ 还是 $0$ 都可以。
C++模板代码：

const int N=5050,INF=0x3f3f3f3f;
int graph[N][N];
void Directed_Weighted_Graph(){ //有向带权图
    memset(graph,INF,sizeof(graph));
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u][v]=w;
    }
}
void Directed_Unweighted_Graph(){ //有向无权图
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u][v]=1;
    }
}
void Undirected_Weighted_Graph(){ //无向带权图
    memset(graph,INF,sizeof(graph));
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u][v]=w;
        graph[v][u]=w;
    }
}
void Undirected_Unweighted_Graph(){ //无向无权图
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u][v]=1;
        graph[v][u]=1;
    }
}

Python模板代码：

def Directed_Weighted_Graph(): #有向带权图
    graph = [[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u][v]=w
def Directed_Unweighted_Graph(): #有向无权图
    graph = [[0 for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u][v]=1
def Undirected_Weighted_Graph(): #无向带权图
    graph = [[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u][v]=w
        graph[v][u]=w
def Undirected_Unweighted_Graph(): #无向无权图
    graph = [[0 for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u][v]=1
        graph[v][u]=1

空间复杂度：$O(n^2)$
练习：
A358. 有向无权图1
A355. 有向带权图1
A352. 无向无权图1

邻接表存图：

我们会发现，邻接矩阵存图，对于稀疏图而言，浪费了太多空间在 $0$ 或 $\infty$ 上，这会导致当 $n$ 越来越大，但是图是稀疏图的时候，会开不下邻接矩阵，尤其是C++，你在本地都开不了那么大的空间。因此，我们可以把邻接矩阵中所有的 $0$ 或者 $\infty$ 去掉，变成邻接表，$adj[i]$ 变成一个（C++）向量或者（Python）列表动态添加边的信息。
C++模板：

#define pir pair<int,int>
#define x first
#define y second
#define pb push_back
const int N=2e5+10;
void Directed_Weighted_Graph(){ //有向带权图
    vector<pir>graph[N];
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u].pb({v,w});
    }
}
void Directed_Unweighted_Graph(){ //有向无权图
    vector<int>graph[N];
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u].pb(v);
    }
}
void Undirected_Weighted_Graph(){ //无向带权图
    vector<pir>graph[N];
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u].pb({v,w});
        graph[v].pb({u,w});
    }
}
void Undirected_Unweighted_Graph(){ //无向无权图
    vector<int>graph[N];
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
}

Python模板代码：

def Directed_Weighted_Graph(): #有向带权图
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u].append((v,w))
def Directed_Unweighted_Graph(): #有向无权图
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u].append(v)
def Undirected_Weighted_Graph(): #无向带权图
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u].append((v,w))
        graph[v].append((u,w))
def Undirected_Unweighted_Graph(): #无向无权图
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u].append(v)
        graph[v].append(u)

空间复杂度：$O(m)$
练习：
A351. 有向带权图2
A650. 有向无权图2

---

图的遍历

图的遍历，主要分为深度优先遍历和广度优先遍历，内容和深度优先搜索（$\tt{Depth\,\,First\,\,Search}$）与广度优先搜索（$\tt{Breadth\,\,First\,\,Search}$）几乎一样。

深度优先遍历：

以邻接表为例，深度优先遍历就是不走回头路，一直往下遍历，遍历到没有未访问的节点就返回。
C++模板代码：

const int N=2e5+10;
vector<int>graph[N]; //邻接表
bool vis[N]; //vis数组标记
void dfs(int u){
    cout<<u<<" "; //输出
    vis[u]=1; //标记
    for(const auto&v:graph[u]) //遍历所有能够到达的点
        if(!vis[v]) //没有标记过则访问，避免重复遍历
            dfs(v); //递归遍历
    return;
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
vis=[0 for i in range(n+1)] #列表生成式初始化标记数组
def dfs(u):
    print(u,end=" ") #输出
    vis[u]=1 #标记
    for v in graph[u]: #遍历所有能到达的点
        if not vis[v]: #没有标记过则访问，避免重复遍历
            dfs(v) #递归遍历
    return

广度优先遍历：

依然以邻接表为例，广搜像水流一样要流经所有节点，虽然搜索时比深搜效率快很多，但是在这里和深搜遍历就效率上来谈没什么大的区别。
C++模板代码：

const int N=2e5+10;
vector<int>graph[N]; //邻接表
bool vis[N]; //vis数组标记
void bfs(int u){
    queue<int>q; //广搜必备队列
    vis[u]=1; //标记
    q.push(u); //加入队列
    while(q.size()){ //循环直到队列中没有元素
        u=q.front(); //取出队首
        q.pop(); //弹出队首
        cout<<u<<" "; //输出
        for(const auto&v:graph[u]){ //遍历所有能够到达的点
            if(!vis[v]){ //没有标记过则访问，避免重复遍历
                vis[v]=1; //标记
                q.push(v); //加入队列
            }
        }
    }
    return;
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
vis=[0 for i in range(n+1)] #列表生成式初始化标记数组
def bfs(u):
    queue=[u] #创造队列
    vis[u]=1 #标记
    while len(queue): #循环直到队列中没有元素
        u=queue.pop(0) #取出并弹出队列
        print(u,end=" ") #输出
        for v in graph[u]: #遍历所有能够到达的点
            if not vis[v]: #没有标记过则访问，避免重复遍历
                vis[v]=1 #标记
                q.append(v) #加入队列
    return

时间复杂度：都是 $O(n)$
练习：
A4762. 关系网络

---

并查集：

并查集（$\tt{Union-Find}$）是一种用于管理‌不相交集合‌的高效数据结构，主要解决元素的‌分组、合并与连通性查询‌问题。主要分成查询（$Find$）和合并（$Unite$）两个操作。可以形象地想象成是认“义父”操作
C++模板代码：

const int N=5050;
int pa[N];
//核心代码
int find(int x){ //查找函数
    if(pa[x]==x)return x; //找到根源，即自己的祖先就是自己
    return pa[x]=find(pa[x]); //递归去寻找，将结果赋值给pa[x]进行路径压缩，防止超时
}
void unite(int a,int b){ //合并函数
    int ra=find(a),rb=find(b); //找到各自的祖先，判断是否为同一个祖先
    if(ra!=rb)pa[rb]=ra; //进行合并操作
}
//初始化
for(int i=1;i<=n;i++)
    pa[i]=i; //默认祖先是自己

Python模板代码：

pa=[i for i in range(n+1)] #列表生成式自带初始化
#核心代码
def find(x): #查找递归
    if pa[x]==x: #找到根源，自己的祖先是自己
        return x #返回结果
    pa[x]=find(pa[x]) #路径压缩
    return pa[x] #返回结果
def unite(a=int,b=int): #合并
    ra,rb=find(a),find(b) #利用元组特性进行赋值
    if ra!=rb: #祖先不同，进行合并
        pa[rb]=ra #朴素的合并操作

单次查找函数的时间复杂度：$O(\log E)$
总时间复杂度：$O(E\log E)$
练习：
A567. 亲戚1
A565. 亲戚2

---

生成树：

在连通图 $G$ 中，对于 $\forall u、v\in G.V$，有且仅有一条路，且生成树中不存在回路。

最小生成树：

是所有的生成树中边权值和最小的一棵生成树。常见算法有 $\tt{Kruskal}$ 和 $\tt{Prim}$

求最小生成树的方法：

· $\tt{Kruskal}$ 算法：

$\tt{Kruskal}$ 算法核心思想是贪心，选择当前最小的边加入生成树，从而找到最小生成树。
1、将所有的边按从小到大顺序排序
2、按排序顺序选择联通 $u,v$ 两个节点的边
3、通过并查集判断 $u,v$ 两个节点是否联通，如果不联通则合并两个节点
4、选到 $n-1$ 条边的时候，由于已经构成生成树，可以直接返回节省时间
C++模板代码：

struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
}e;
bool cmp(Edge a,Edge b){ //比较函数，因为权值和最小，所以按照边权值从小到大排序
    return a.w<b.w;
}
vector<Edge>edges; //存连通图的每条边
int n,m,c[N],ans,cnt;
int find(int x){ //并查集 查询函数
    if(c[x]==x)return x;
    return c[x]=find(c[x]); //路径压缩
}
void Kruskal(){
    for(int i=1;i<=n;i++)c[i]=i; //并查集初始化
    sort(edges.begin(),edges.end(),cmp); //按边的权值从小到大的顺序将边进行排序
    for(const auto&edge:edges){ //按顺序遍历数组
        int cu=find(edge.u),cv=find(edge.v); //找到两个节点所在的联通子图
        if(cu!=cv){ //两点并未联通
            c[cv]=cu; //合并两个节点，即并查集
            cnt++; //计数，可以在下面节约时间
            ans+=edge.w; //加上权值
        }
        if(cnt==n-1)return; //已经找到一棵最小生成树，退出循环
    }
}

Python模板代码：

edges=[] #存边，而非邻接表
pa=[i for i in range(n+1)] #列表生成式，并查集初始化
def find(x): #并查集的查找函数
    if pa[x]==x: #找到根源，自己的祖先是自己
        return x #返回结果
    pa[x]=find(pa[x]) #路径压缩
    return pa[x] #返回结果
def Kruskal():
    edges.sort(key=lambda x:x[2]) #按照边权从小到大排序进行贪心
    cnt=ans=0 #cnt计数，ans最小边权和
    for u,v,w in edges: #遍历
        cu,cv=find(u),find(v) #找到祖先
        if cu!=cv: #两个点未连通，进行边权添加，连入同一棵最小生成树
            cnt+=1 #选的边数+1
            ans+=w #更新答案
            pa[cv]=cu; #合并
        if cnt==n-1: #n个顶点n-1条边，选到了提前退出
            break

时间复杂度：$O(m\log m)$
空间复杂度：$O(n+m)$

· $\tt{Prim}$ 算法：

$\tt{Prim}$ 算法采用蓝白点思想，过程如下：
1、初始化距离数组为 $\infty$，选择初始节点，将其距离设为 $0$
2、遍历所有节点中未标记的节点，选择其中距离最小的节点，进行标记
3、从该节点出发，遍历其能够到达的所有节点，更新其距离
4、重复执行操作 $2$ 和 $3$ 直到全部顶点都被标记
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,u,v,w,ans,dist[N];
bool vis[N];
struct Node{
    int v,w; //v表示目标节点，w表示边权值
};
vector<Node>graph[N]; //邻接表存图
void prim(int u){
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    for(int i=1;i<=n;i++){ //重复执行n次，包括传入的参数u
        u=0; //和赋值为0的u比较
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<dist[u]) //通过比较找到距离最近的节点
                u=j; //更新u
        vis[u]=1; //标记为已到达
        for(const auto&[v,w]:graph[u]) //遍历其相邻节点
            if(!vis[v]) //一定要未被标记过，否则会重复
                dist[v]=min(dist[v],w); //更新，因为结果需要累加，所以只要保留w
    }
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
vis=[0 for i in range(n+1)] #列表生成式初始化
def prim(u): #核心函数
    dist[u]=0 #u到u距离为0
    for i in range(n): #循环n次找开始更新的点，包括u
        u=0 #和赋值为极大值的0号节点比较，且0号节点不参与更新
        for j in range(1,n+1): #遍历
            if not vis[j] and dist[j]<dist[u]: #通过比较找到距离最近的节点
                u=j #更新u
        vis[u]=1 #标记为已到达
        for v,w in graph[u]: #遍历从当前节点出发的每一条边
            if not vis[v]: #未标记过以防重复
                dist[v]=min(dist[v],w) #更新，结果是累加的，所以只保留w

时间复杂度：$O(n^2)$
空间复杂度：$O(n+m)$

· $\tt{Prim}$ 算法的优化：

不难发现，$\tt{Prim}$ 算法之所以时间复杂度为 $O(n^2)$，是因为外层循环中嵌套了一个内层循环去寻找距离最近的点。为了优化时间复杂度，可以利用 $\tt{STL}$ 容器的特性。
一个合适的方法是利用优先队列（堆）来动态获取最小值，从而降低时间复杂度。
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
bool vis[N];
struct Node{
    int v,w;
    friend bool operator<(const Node&a,const Node&b){
    	return a.w>b.w; //重载运算符
	}
};
vector<Node>graph[N];
void dijkstra(int u){
	priority_queue<Node>q; //优先队列取最小值
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    q.push({u,0}); //初始节点加入队列
    while(q.size()){ //bfs思路
    	Node f=q.top(); //取出队首
    	q.pop(); //弹出队首
    	u=f.v;
    	if(vis[u])continue; //已被标记不再入队
        vis[u]=1; //标记为已到达
    	for(const auto&[v,w]:graph[u]) //遍历其相邻节点
    		if(dist[v]>w){
    			dist[v]=w; //更新
    			q.push({v,dist[v]}); //入队
			}
	}
}

Python模板代码：

graph=[[] for i in range(n+1)]
dist=[0x3f3f3f3f for i in range(n+1)]
vis=[0 for i in range(n+1)]
class Priority_Queue(): #手搓堆（优先队列），你也可以用heapq库
    def __init__(self):
#堆就是完全二叉树，利用完全二叉树的性质，父节点编号为i，子节点编号为2i和2i+1，用列表建堆
        self.heap=[(0,0)] #堆的主要结构，强制变成1-based
        self.size=0 #记录堆的大小
    def push(self,val): #插入
        self.size+=1
        self.heap.append(val) #插入到末尾
        son=self.size
        while son>1: #向上比较
            pa=son//2
            if self.heap[pa][1]<=self.heap[son][1]: #无法继续向上爬则退出
                break
            self.heap[pa],self.heap[son]=self.heap[son],self.heap[pa] #交换
            son=pa
    def pop(self): #移除
        self.heap[1]=self.heap[self.size] #变成堆顶
        self.heap.pop(self.size) #弹出末尾
        self.size-=1
        pa=1
        while pa*2<=self.size: #向下比较
            son=pa*2
            if son<self.size and self.heap[son+1][1]<=self.heap[son][1]:
                son+=1 #更新成更小的子节点
            if self.heap[pa][1]<=self.heap[son][1]: #无法向下爬则退出
                break
            self.heap[pa],self.heap[son]=self.heap[son],self.heap[pa] #交换
            pa=son
    def top(self): #取堆顶元素
        return self.heap[1]
def prim(u):
    pq=Priority_Queue() #小根堆动态取最小值
    dist[u]=0 #u到u距离为0
    pq.push((u,0)) #加入队列
    while pq.size: #bfs思路
        f=pq.top() #取出队首
        pq.pop() #弹出队首
        u=f[0]
        if vis[u]: #已被标记不再入队
            continue
        vis[u]=1 #标记
        for v,w in graph[u]: #遍历可到达节点
            if dist[v]>w: #可以松弛
                dist[v]=w #松弛更新
                pq.push((v,dist[v])) #加入队列

时间复杂度：$O((n+m)\log n)$
练习：
A555. 最小生成树

---

最短路算法：

即求从节点 $u$ 到节点 $v$ 所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定节点 $u$ 到所有其它节点$v$的算法，而多源最短路算法可以求 $\forall u \in G.V$ 作为起点到其它节点 $v$ 的最短路。

单源最短路算法：

常见的有 $\tt{Dijkstra}$、$\tt{Bellman\,\,Ford}$ 和 $\tt{SPFA}$ 三个算法。

求单源最短路的方法：

· $\tt{Dijkstra}$ 算法：

1、初始化距离数组为 $\infty$，将初始节点距离设为 $0$
2、遍历所有节点中未标记的节点，选择其中距离最小的节点，进行标记
3、从该节点出发，遍历其能够到达的所有节点，更新其距离
4、重复执行操作 $2$ 和 $3$ 直到全部顶点都被标记
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
bool vis[N];
struct Node{
    int v,w; //v表示目标节点，w表示边权值
};
vector<Node>graph[N]; //邻接表存图
void dijkstra(int u){
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    for(int i=1;i<n;i++){ //重复n-1次，类似冒泡排序，可以省最后一次
        u=0; //和赋值为0的无效u比较
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<dist[u]) //通过比较找到距离最近的节点
                u=j; //更新u
        vis[u]=1; //标记为已到达
        for(const auto&[v,w]:graph[u]) //遍历其相邻节点
            if(!vis[v]) //一定要未被标记过，否则会重复
                dist[v]=min(dist[v],dist[u]+w); //更新
                //和Prim不同的是这里是和dist[u]+w比较更新
    }
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
vis=[0 for i in range(n+1)] #列表生成式初始化
def dijkstra(u): #核心函数
    dist[u]=0 #u到u距离为0
    for i in range(n): #循环n次找开始更新的点，包括u
        u=0 #和赋值为极大值的0号节点比较，且0号节点不参与更新
        for j in range(1,n+1): #遍历
            if not vis[j] and dist[j]<dist[u]: #通过比较找到距离最近的节点
                u=j #更新u
        vis[u]=1 #标记为已到达
        for v,w in graph[u]: #遍历从当前节点出发的每一条边
            if not vis[v]: #未标记过以防重复
                dist[v]=min(dist[v],dist[u]+w) #更新，注意最短路里面就需要累加

时间复杂度：$O(n^2)$
空间复杂度：$O(n+m)$

· $\tt{Dijkstra}$ 算法的优化

根据上面代码，用 $O(n^2)$ 的时间复杂度取求最短路无疑是有点浪费时间的，时间都花在了找最小值上面。依然考虑利用 $\tt{STL}$ 容器的特性来优化 $\tt{Dijkstra}$ 算法，我们需要一个能够动态找最小值的容器。
因此，我们可以利用优先队列（堆）动态找到最小值来优化 $\tt{Dijkstra}$ 算法：
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
bool vis[N];
struct Node{
    int v,w;
    friend bool operator<(const Node&a,const Node&b){
    	return a.w>b.w; //重载运算符
	}
};
vector<Node>graph[N];
void dijkstra(int u){
	priority_queue<Node>q; //优先队列取最小值
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    q.push({u,0}); //初始节点加入队列
    while(q.size()){ //bfs思路
    	Node f=q.top(); //取出队首
    	q.pop(); //弹出队首
    	u=f.v;
    	if(vis[u])continue; //已被标记不再入队
        vis[u]=1; //标记为已到达
    	for(const auto&[v,w]:graph[u]) //遍历其相邻节点
    		if(dist[v]>dist[u]+w){
    			dist[v]=dist[u]+w; //更新
    			q.push({v,dist[v]}); //入队
			}
	}
}

Python模板代码：

graph=[[] for i in range(n+1)]
dist=[0x3f3f3f3f for i in range(n+1)]
vis=[0 for i in range(n+1)]
class Priority_Queue(): #手搓堆（优先队列），你也可以用heapq库
    def __init__(self):
#堆就是完全二叉树，利用完全二叉树的性质，父节点编号为i，子节点编号为2i和2i+1，用列表建堆
        self.heap=[(0,0)] #堆的主要结构，强制变成1-based
        self.size=0 #记录堆的大小
    def push(self,val): #插入
        self.size+=1
        self.heap.append(val) #插入到末尾
        son=self.size
        while son>1: #向上比较
            pa=son//2
            if self.heap[pa][1]<=self.heap[son][1]: #无法继续向上爬则退出
                break
            self.heap[pa],self.heap[son]=self.heap[son],self.heap[pa] #交换
            son=pa
    def pop(self): #移除
        self.heap[1]=self.heap[self.size] #变成堆顶
        self.heap.pop(self.size) #弹出末尾
        self.size-=1
        pa=1
        while pa*2<=self.size: #向下比较
            son=pa*2
            if son<self.size and self.heap[son+1][1]<=self.heap[son][1]:
                son+=1 #更新成更小的子节点
            if self.heap[pa][1]<=self.heap[son][1]: #无法向下爬则退出
                break
            self.heap[pa],self.heap[son]=self.heap[son],self.heap[pa] #交换
            pa=son
    def top(self): #取堆顶元素
        return self.heap[1]
def dijkstra(u):
    pq=Priority_Queue() #小根堆动态取最小值
    dist[u]=0 #u到u距离为0
    pq.push((u,0)) #加入队列
    while pq.size: #bfs思路
        f=pq.top() #取出队首
        pq.pop() #弹出队首
        u=f[0]
        if vis[u]: #已被标记不再入队
            continue
        vis[u]=1 #标记
        for v,w in graph[u]: #遍历可到达节点
            if dist[v]>dist[u]+w: #可以松弛
                dist[v]=dist[u]+w #松弛更新
                pq.push((v,dist[v])) #加入队列

时间复杂度：$O((n+m)\log n)$

· $\tt{Dijkstra}$ 不适用的情况：

根据 $\tt{Dijkstra}$ 算法的逻辑流程，可以进行简单模拟，易得 $\tt{Dijkstra}$ 算法不适用于出现 负边权 的情况。

· $\tt{Bellman\,\,Ford}$ 算法：

1、遍历所有的边
2、从边的起点到终点做松弛操作
优化：如果没有进行过松弛操作则退出循环
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
};
vector<Edge>graph; //存图的每条边
void Bellman_Ford(int u){
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    for(int i=1;i<n;i++){ //重复n-1次，和Dijkstra一样
        bool opt=0; //用于判断是否进行松弛操作
        for(const auto&[u,v,w]:graph) //按顺序遍历数组
            if(dist[u]+w<dist[v]) //注意这里是有向图，无向图还需交换u和v
                dist[v]=dist[u]+w,opt=1; //松弛操作后可以进行标记
        if(!opt)return; //如果这次没有操作，下次也不会有操作，退出节省时间
    }
}

Python模板代码：

edges=[] #存边，而非邻接表
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
def Bellman_Ford(u):
    dist[u]=0 #u到u距离为0
    for i in range(n): #一共枚举n次
        opt=0 #用于判断是否进行松弛操作
        for u,v,w in edges: #枚举所有边
            if dist[u]+w<dist[v]: #可以进行松弛
                dist[v]=dist[u]+w #松弛
                opt=1 #标记
        if not opt: #没有进行松弛，那么下一轮也不会松弛，退出循环
            break

时间复杂度：$O(nm)$
空间复杂度：$O(n+m)$

· $\tt{Bellman\,\,Ford}$ 算法变形——不超过 $k$ 条边的最短路

对于某些题目，要求走的边数不超过 $k$ 且求最短路，普通的 $\tt{Bellman\,\,Ford}$ 算法肯定行不通。此时，我们可以使用 $\tt{dp}$ 思想，来进行最短路的计算，如下：
C++模板代码：

#define pb push_back
#define int long long
const int MAXN=0x3f3f3f3f; //防止做加法超出int范围 
const int N=5050;
int n,m,k,u,v,w,dist[N][N]; //dist[i][j]表示选用i条边到达j的最短路
struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
};
vector<Edge>graph; //存图的每条边
void Bellman_Ford(int u){
    memset(dist,MAXN,sizeof(dist)); //初始化
    dist[0][u]=0; //以u为初始节点，距离为u到u的距离，即0
    for(int i=1;i<n;i++){ //重复n-1次，和Dijkstra一样
        bool opt=0; //用于判断是否进行松弛操作
        for(const auto&[u,v,w]:graph) //按顺序遍历数组
            if(dist[i-1][u]+w<dist[i][v]) //注意这里是有向图，无向图还需交换u和v
                dist[i][v]=dist[i-1][u]+w,opt=1; //松弛操作后可以进行标记
        if(!opt)return; //如果这次没有操作，下次也不会有操作，退出节省时间
    }
}

Python模板代码：

edges=[] #存边
dist=[[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)]
#dist[i][j]选i条边到j最短路
def Bellman_Ford(u):
    dist[0][u]=0 #u到u的距离为0
    for i in range(1,n): #重复n-1次
        opt=0 #是否进行松弛
        for u,v,w in edges: #按顺序便利数组
            if dist[i-1][u]+w<dist[i][v]: #可以进行松弛
                dist[i][v]=dist[i-1][u]+w #松弛，因为边数不超过k所以不可以降维
                opt=1 #标记
            if not opt:
                return #小优化

时间复杂度：$O(nm)$
空间复杂度：$O(n^2)$

· $\tt{SPFA}$ 算法：

$\tt{SPFA}$（$Shortest\,\,Path\,\,Faster\,\,Algorithm$）是 $\tt{Bellman\,\,Ford}$ 算法的进阶版本，通过队列来对其进行优化，只不过不常用而已。
C++模板代码：

const int N=5050;
const int MAXN=0x3f3f3f3f;
int n,m,k,u,v,w,dist[N],cnt[N];
bool vis[N];
struct node{
    int v,w; //v表示目标节点，w表示边权值
};
vector<node>graph[N]; //邻接表存图
void spfa(int u){
    for(int i=1;i<=n;i++)dist[i]=MAXN,vis[i]=0; //初始化
    queue<int>q;
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    q.push(u);
    while(q.size()){
        u=q.front(); //取出队首，同bfs
        q.pop(); //弹出队首，同bfs
        vis[u]=0; //撤销标记，因为spfa可以重复入队
        cnt[u]++; //计数
        if(cnt[u]>n)return; //和Bellman-Ford一样最多只能入队n次，大于n直接返回
        for(const auto&[v,w]:graph[u]) //按顺序遍历数组
            if(dist[v]>dist[u]+w){ //判断是否可以进行松弛操作
                dist[v]=dist[u]+w; //松弛
                if(!vis[v]){ //如果未被标记说明不在队伍中，标记入队
                    vis[v]=1; //标记
                    q.push(v); //入队
                }
            }
    }
}

Python模板代码：

graph=[[] for i in range(n+1)]
queue=[]
vis=[0 for i in range(n+1)] #列表生成式给vis初始化
cnt=[0 for i in range(n+1)] #列表生成式给cnt初始化
# 注意：此处不可以写vis=cnt=[0 for i in range(n+1)]
# 因为这是浅拷贝，vis和cnt指向同一列表，修改一个另一个也会变，导致答案错误
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式给dist初始化
def spfa(u):
    queue.append(u) #入队
    dist[u]=0 #以u节点为初始节点，因此距离为u到u的距离，即0
    while len(queue):
        u=queue.pop(0) #取出并弹出队首（Python便捷之处）
        vis[u]=0 #撤销标记，因为spfa可以重复入队
        cnt[u]+=1 #计数
        if cnt[u]>n: #和Bellman-Ford一样最多只能入队n次，大于n次就结束
            return
        for v,w in graph[u]: #按顺序遍历列表
            if dist[u]+w<dist[v]: #判断是否可以进行松弛操作
                dist[v]=dist[u]+w #松弛
                if not vis[v]: #如果未标记说明不在队中，标记入队
                    vis[v]=1 #标记
                    queue.append(v) #入队

时间复杂度：$O(kn)$（$k$为常数，通常是在 $[2,3]$ 之间）
空间复杂度：$O(n+m)$
队列空间复杂度：$0\sim O(n)$ 之间

· $\tt{SPFA}$ 算法变形——判负环

$\tt{SPFA}$ 算法有一个好处，在于其判断负环的便捷性。

假设起点为 $u$，当前节点为 $v$，若从 $u$ 到 $v$ 真实的最短路长度大于等于 $0$，将其记作为 $d$，则当 $\tt{SPFA}$ 算法更新 $dist[v]$ 成 $d$ 后，再次遍历到达节点 $v$ 时，更新的 $dist[v]$ 值依然不会变。
如果 $\exist d$ 且 $d<0$，说明存在一条负的路径可以到达 $v$，只不过不是一个负环，你依然可以在 $n$ 次及以内把 $dist[v]$ 更新为 $d$。

但如果不存在 $d$，说明存在负环，没走一次负环都会使 $dist[v]$ 变得更小，也就是不存在最小的 $dist[v]$，因而 $v$ 节点会被遍历超过 $n$ 次。

综上，只要在遍历过程中发现 $cnt[v]>n$，就说明存在负环。
C++模板代码：

const int N=5050;
const int MAXN=0x3f3f3f3f;
int n,m,k,u,v,w,dist[N],cnt[N];
bool vis[N];
struct node{
    int v,w; //v表示目标节点，w表示边权值
};
vector<node>graph[N]; //邻接表存图
bool spfa(int u){
    for(int i=1;i<=n;i++)dist[i]=MAXN,vis[i]=0; //初始化
    queue<int>q;
    dist[u]=0; //以u为初始节点，距离为u到u的距离，即0
    q.push(u);
    while(q.size()){
        u=q.front(); //取出队首，同bfs
        q.pop(); //弹出队首，同bfs
        vis[u]=0; //撤销标记，因为spfa可以重复入队
        cnt[u]++; //计数
        if(cnt[u]>n)return 1; //入队超过n次，说明存在负环，返回真
        for(const auto&[v,w]:graph[u]) //按顺序遍历数组
            if(dist[v]>dist[u]+w){ //判断是否可以进行松弛操作
                dist[v]=dist[u]+w; //松弛
                if(!vis[v]){ //如果未被标记说明不在队伍中，标记入队
                    vis[v]=1; //标记
                    q.push(v); //入队
                }
            }
    }
    return 0; //成功更新所有点，说明没有负环，返回假
}

Python模板代码：

graph=[[] for i in range(n+1)]
queue=[]
vis=[0 for i in range(n+1)] #列表生成式给vis初始化
cnt=[0 for i in range(n+1)] #列表生成式给cnt初始化
# 注意：此处不可以写vis=cnt=[0 for i in range(n+1)]
# 因为这是浅拷贝，vis和cnt指向同一列表，修改一个另一个也会变，导致答案错误
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式给dist初始化
def spfa(u):
    queue.append(u) #入队
    dist[u]=0 #以u节点为初始节点，因此距离为u到u的距离，即0
    while len(queue):
        u=queue.pop(0) #取出并弹出队首（Python便捷之处）
        vis[u]=0 #撤销标记，因为spfa可以重复入队
        cnt[u]+=1 #计数
        if cnt[u]>n: #入队超过n次，说明存在负环，返回真
            return 1
        for v,w in graph[u]: #按顺序遍历列表
            if dist[u]+w<dist[v]: #判断是否可以进行松弛操作
                dist[v]=dist[u]+w #松弛
                if not vis[v]: #如果未标记说明不在队中，标记入队
                    vis[v]=1 #标记
                    queue.append(v) #入队
    return 0 #成功更新所有点，说明没有负环，返回假

练习：
A569. 单源最短路1
A551. 单源最短路2

多源最短路算法：

一般用 $\tt{Floyd\,\,Warshall}$ 算法（也有版本叫它 $\tt{Floyed\,\,Warshall}$）。

求多源最短路的方法：

· $\tt{Floyd\,\,Warshall}$：

$\tt{Floyd\,\,Warshall}$ 算法可能是大多数人最喜欢的方法，究其原因还是因为好写，直接暴力循环就完事了。其核心思想是动态规划，把每个节点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。
C++模板代码：

const int INF=0x3f3f3f3f; //极大值
int n,m,q,dp[110][110],u,v,w;
void Floyd_Warshall(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=i==j?0:INF; //初始化
    for(int k=1;k<=n;k++) //枚举所有的节点作为中转点
        for(int i=1;i<=n;i++) //枚举所有的节点作为起点
            for(int j=1;j<=n;j++) //枚举所有的节点作为终点
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); //动态规划计算最短路
}

Python模板代码：

dp=[[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)] #邻接矩阵初始化
for i in range(1,n+1):
    dp[i][i]=0 #u到u距离为0
def Floyd_Warshall():
    for k in range(1,n+1): #枚举所有的节点作为中转点
        for i in range(1,n+1): #枚举所有的节点作为起点
            for j in range(1,n+1): #枚举所有的节点作为终点
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) #动态规划计算最短路

时间复杂度：$O(n^3)$
空间复杂度：$O(n^2)$

· $\tt{Floyd\,\,Warshall}$【变形1】传递闭包：

给你一个图，问你能否从 $u$ 节点到达 $v$ 节点，一样可以用 $\tt{Floyd\,\,Warshall}$ 算法，其核心在于判断你从 $u$ 到 $v$ 的距离是否为初始化设置的无穷大。

当然，如果想要节约空间，我们可以利用布尔值来标记，即令 $dp[u][v]=1$ 表示 $u$ 能够到达 $v$，而 $dp[u][v]=0$ 表示 $u$ 无法到达 $v$。这样，我们可以利用布尔值的性质来传递闭包，转移方程式 dp[i][j]|=dp[i][k]&dp[k][j]。
C++模板代码：

const int INF=0x3f3f3f3f; //极大值
int n,m,q,u,v,w;
bool dp[110][110];
void Floyd_Warshall(){ //传递闭包
    for(int k=1;k<=n;k++) //枚举所有的节点作为中转点
        for(int i=1;i<=n;i++) //枚举所有的节点作为起点
            for(int j=1;j<=n;j++) //枚举所有的节点作为终点
                dp[i][j]|=dp[i][k]&dp[k][j]; //动态规划传递闭包
}

Python模板代码：

dp=[[False for i in range(n+1)] for i in range(n+1)] #邻接矩阵初始化
def Floyd_Warshall():
    for k in range(1,n+1): #枚举所有的节点作为中转点
        for i in range(1,n+1): #枚举所有的节点作为起点
            for j in range(1,n+1): #枚举所有的节点作为终点
                dp[i][j]=dp[i][j] or dp[i][k] and dp[k][j] #动态规划传递闭包
#考虑到Python中没有特别合适的按位运算符，可以利用max和min函数来保持它是一个0/1值
#当然，也可以像上面代码一样利用True/False来表示状态（and优先级高于or）

· $\tt{Floyd\,\,Warshall}$【变形2】最大边权最小化：

给你一个图，问你从 $u$ 节点到达 $v$ 节点的过程中，所需要经过的最大边权最小是多少。
一样的动态规划思想，令 $dp[u][v]$ 表示从节点 $u$ 到节点 $v$ 的最大边权的最小值，则转移方程式为 dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]))
C++模板代码：

const int INF=0x3f3f3f3f; //极大值
int n,m,q,dp[110][110],u,v,w;
void Floyd_Warshall(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=i==j?0:INF; //初始化
    for(int k=1;k<=n;k++) //枚举所有的节点作为中转点
        for(int i=1;i<=n;i++) //枚举所有的节点作为起点
            for(int j=1;j<=n;j++) //枚举所有的节点作为终点
                dp[i][j]|=min(dp[i][j],max(dp[i][k],dp[k][j])); //动态规划求最值
}

Python模板代码：

dp=[[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)] #邻接矩阵初始化
for i in range(1,n+1):
    dp[i][i]=0 #u到u距离为0
def Floyd_Warshall():
    for k in range(1,n+1): #枚举所有的节点作为中转点
        for i in range(1,n+1): #枚举所有的节点作为起点
            for j in range(1,n+1): #枚举所有的节点作为终点
                dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j])) #动态规划求最值

练习：
A29680. 最短距离查询【Floyd模板】
P2245. 奶牛的比赛【Floyd传递闭包】
P2888 [USACO07NOV] Cow Hurdles S【Floyd最大边权最小化】

拓扑排序

图的拓扑排序定义：
对于有向无环图（简称 $DAG$）是将 $G$ 中所有顶点排成一个线性序列，使得 $\forall u,v\in G.V$，若边 $<u,v$ $>$ $\in G.E$，则 $u$ 在线性序列中出现在 $v$之前。
1、选择一个入度为0的顶点并输出
2、从图中删除此顶点及所有出边
3、重复操作 $1$ 和 $2$ 直到没有符合要求的点
C++模板代码：

const int N=5050;
vector<int>graph[N]; //存图
int n,m,u,v,in[N]; //in[N]存入度
vector<int>topo; //存储拓扑序列
void toposort(){
    queue<int>q; //队列存储当前入度为0的元素，便于后续操作
    for(int i=1;i<=n;i++)if(!in[i])q.push(i); //入度为0则可以入队
    while(q.size()){ //同bfs
        int u=q.front(); //取队首，同bfs
        q.pop(); //弹出，同bfs
        topo.push_back(u); //加入序列
        for(const auto&v:graph[u]) //遍历相邻节点
            if(!--in[v]) //入度-1，因为一个前驱节点已经被取出来，相当于删边
                q.push(v); //如果减少入度后入度为0则加入队列，同bfs
                //由于!运算符优先级比--运算符低，因此这里先自减后判非，可行
    }
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式初始化邻接表
degree=[0 for i in range(n+1)] #列表生成式初始化入度列表
topo=[] #存储拓扑序列
def toposort():
    queue=[] #队列存储当前入度为0的元素，便于后续操作
    for i in range(n):
        if not degree[i+1]: #入度为0可以入队
            queue.append(i+1) #入队
    while len(queue):
        u=queue.pop(0) #取队首并弹出
        topo.append(u) #加入序列
        for v in graph[u]: #遍历相邻节点
            degree[v]-=1 #入度-1，因为取出一个前驱节点，相当于删边
            if not degree[v]: #如果减少入度后入度为0则加入队列
                queue.append(v) #入队

拓扑排序判环

根据有向无环图的拓扑排序序列定义可以知道，只有当节点 $u$ 的入度为 $0$ 时，它才能够加入拓扑序列。
因此，一旦有向图存在环，则说明存在首尾相连的结构，不管再怎么删其它节点，这个环必然会留到最后，导致环上每一个节点入度都不为 $0$，从而无法加入拓扑序列。因此，只要拓扑序列长度小于节点个数，则说明有向图存在环路。
C++模板代码：

const int N=5050;
vector<int>graph[N]; //存图
int n,m,u,v,in[N]; //in[N]存入度
vector<int>topo; //存储拓扑序列
bool toposort(){
    queue<int>q; //队列存储当前入度为0的元素，便于后续操作
    for(int i=1;i<=n;i++)if(!in[i])q.push(i); //入度为0则可以入队
    while(q.size()){ //同bfs
        int u=q.front(); //取队首，同bfs
        q.pop(); //弹出，同bfs
        topo.push_back(u); //加入序列
        for(const auto&v:graph[u]) //遍历相邻节点
            if(!--in[v]) //入度-1，因为一个前驱节点已经被取出来，相当于删边
                q.push(v); //如果减少入度后入度为0则加入队列，同bfs
                //由于!运算符优先级比--运算符低，因此这里先自减后判非，可行
    }
    return topo.size()==n; //如果二者大小不等，则说明有向图中存在环
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式初始化邻接表
degree=[0 for i in range(n+1)] #列表生成式初始化入度列表
topo=[] #存储拓扑序列
def toposort():
    queue=[] #队列存储当前入度为0的元素，便于后续操作
    for i in range(n):
        if not degree[i+1]: #入度为0可以入队
            queue.append(i+1) #入队
    while len(queue):
        u=queue.pop(0) #取队首并弹出
        topo.append(u) #加入序列
        for v in graph[u]: #遍历相邻节点
            degree[v]-=1 #入度-1，因为取出一个前驱节点，相当于删边
            if not degree[v]: #如果减少入度后入度为0则加入队列
                queue.append(v) #入队
    return len(topo)==n #如果二者大小不等，说明有环的存在

时间复杂度：$O(n+m)$
空间复杂度：$O(n+m)$
练习：
A29684. 确定比赛名次
A29810. 拓扑排序和判环

---

备注：

符号解释：
$G$：表示一张图
$G.V$：指点的集合
$G.E$：指边的集合
$u,v$：表示两个特定节点
$w$：表示边权
$n$：表示点数
$m$：表示边数

下期预告：

图论算法合集会持续更新，只不过由于篇幅过长，会另外开几个帖子讲后续内容。
下期暂定内容为：

• 最短路径图
• 分层图
• 欧拉路径与欧拉回路
• 强连通分量
• 双连通分量和割点割边