图的应用
4.1 拓扑排序
拓扑排序针对有向无环图的顶点进行线性排列的算法，使得对于任何来自顶点A指向顶点B的边，A都在序列中出现在B之前。这样的排序存在于有向无环图中，而对于非有向无环图则不存在拓扑排序。
拓扑排序也可以用来检测图中有无成环
4.2 最小生成树
生成树是连通图的极小连通子图，多一条边就会成环，少一条边即无法构成连通图
生成树的代价：
G=(V,E)是一个无向连通图，代价是生成树上各边的边权和
生成树代价=9+49+11+1+21=91
最小生成树即是代价最小的生成树
上图中代价min=1+7+10+7+5=30
最小生成树解析
4.2.1 Kruskal（加边）
将边从小到大排序
利用并查集 合并边
如果该边的加入不会成换，则加入，否则不加入
时间复杂度分析：边排序时间+并查集时间
蓝桥889
# n 个交叉路口 -- n个点 m条边 无向图
# 最小生成树
# 1≤n≤300，1≤m≤1e5 边>>点 稠密图 最好用Prmie
# Kruskal版
n,m = map(int,input().split())
# 存图
e = []
# m条边 连边
for i in range(m):
u,v,c = map(int,input().split())
e.append((c,u,v)) # 把分值c放第一位，方便后续排序
# 边排序
e.sort()
# 把所有的交叉路口直接或间接的连通起来 -- 并查集
p = list(range(n+1))
# 递归找根
def find_root(x):
if x != p[x]:
p[x] = find_root(p[x])
return p[x]
# 从小到大遍历所有边，进行合并 找最小的生成树
# sum记录边权和，max_val记录最大的边权
sum, max_val = 0,0
for w,u,v in e:
rootu = find_root(u)
rootv = find_root(v)
if rootv != rootu:
p[rootv] = rootu
# 合并次数+1 修路的条数+1
sum += 1
max_val = max(max_val,w)
print(sum,max_val)
4.2.2 Prime（加点）
算法流程：d[i]表示点i和集合的距离
选择一个初始点(随意)u加入集合S，d[u]=0
利用点u更新其它的点（加入离当前集合最近的点）
在d中选择最小未加入集合的点作为新一轮的u
重复上述至所有点加入集合（过程中有两个分区，一个是加入集合的点，另一个是还未加入的点）
# 蓝桥889
# n 个交叉路口 -- n个点 m条边 无向图
# 最小生成树
# 1≤n≤300，1≤m≤1e5 边>>点 稠密图 最好用Prmie
# Prime版
import math
n,m = map(int,input().split())
INF = math.inf
# 存图
mapp = [[INF]*(n+1) for _ in range(n+1)]
for _ in range(m):
u,v,w = map(int,input().split())
mapp[u][v] = mapp[v][u] = min(mapp[u][v],w)
# 定义集合d
d = [INF] * (n+1)
max_val = 0
# 初始化d[1]=0
u = 1
# 跑Prime加点
for i in range(n-1): # 除去第一个点，还有n-1个点
d[u] = 0
# 初始化下一个点，下一条边
next_u = 0
next_val = INF
for v in range(1,n+1):
if d[v] == 0: continue # 该点不与当前集合d连通
d[v] = min(d[v], mapp[u][v]) # mapp[u][v]点u到v的边权
# 第i次加点时找到离当前集合更近的点
if d[v] < next_val:
next_val = d[v]
next_u = v
# 基于上一轮扩大下一轮集合，更新d
u = next_u
max_val = max(next_val, max_val)
print(n-1, max_val)
4.3 最短路问题
最短路径是两个顶点之间经历的边上边权之和最小的可达路径
4.3.1 Floyed
用于处理多源最短路，从多个点出发到一个点的最短路，可以存在负权边。
蓝桥8336
# n点m边
# floyd 利用动态规划 三层循环
# 定义dp[k][i][j]表示点i到点j的路径(除去起点和终点)中编号最大不超过k的情况下，i到j的最短距离
# 当加入 第k个点 作为i到j的 中间点
# dp[k][i][j] = mian(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])
import math
n,m = map(int,input().split())
# 城市i的商品产量
a = [0] * (n+1)
# 城市i的商品生产成本
p = [0] * (n+1)
# 城市i的商品售卖单价
s = [0] * (n+1)
INF = math.inf
# 一件商品从城市i运往城市j的利润：gi,j=sj-pi-fij
# 其中fi,j是路径费用
f = [[INF] *(n+1) for _ in range(n+1)] # fij为INF表示不通路
g = [[0] *(n+1) for _ in range(n+1)]
# 输入a，p，s
for i in range(1,n+1):
a[i],p[i],s[i] = map(int,input().split())
# 输入图
for i in range(1,m+1):
u,v,w = map(int,input().split())
f[u][v] = f[v][u] = min(f[u][v],w)
# 对角线费用为0 n个点
for i in range(1,n+1):
f[i][i] = 0
# floyd 动态规划 三层循环 跑一遍多源全图最短路填f路费表
for k in range(1,n+1):
for i in range(1,n+1):
for j in range(1,n+1):
f[i][j] = min(f[i][j], f[i][k] + f[k][j])
# 填完路费 现在算利润 填g 把i城市生产的产品送到城市j卖
for i in range(1,n+1):
for j in range(1,n+1):
g[i][j] = s[j] - p[i] - f[i][j]
# 求全图的最大利润
max_g = 0
for i in range(1,n+1):
# 在第二层循环中作一个判断是否有交易的依据
max_s = -1
for j in range(1,n+1):
max_s = max(max_s,g[i][j])
max_g += max(0, max_s) * a[i] # 乘上产品数量
print(max_g)
4.3.2 Dijkstra
用于处理单源最短路，从一个点出发到一个点的最短路，不可以存在负权边。
# n点m边 有向图
# 从皇宫到每个建筑的最短路径是多少 -- 单源最短路
from queue import PriorityQueue
import math
INF = math.inf
# dijkstra ，s:起点
def dijkstra(s):
# 求从起点s出发到各个点i的最短路径
# d[i]表示从起点s出发到点i的最短的最短路径
d = [INF]*(n+1)
# vis[i]表示第i个点是否出队列
vis = [0]*(n+1)
# 创建优先队列
q = PriorityQueue()
# 起点初始化距离0
d[s] = 0
# 起点入队列
q.put((d[s],s))
# 当队列非空
while q.queue:
dis,u = q.get()
# 每个点只有第一次出队列有效
if vis[u]:continue
vis[u] = 1
# 松弛 找离当前点在连通状态下的最近点
for v,w in G[u]:
if d[v] > d[u] + w:
d[v] = d[u] + w
q.put((d[v],v))
# 处理完成d数组后按题目要求不通的距离为视为-1
for i in range(n+1):
if d[i] == INF:
d[i] = -1
print(*d[1:],sep=' ')
n,m = map(int,input().split())
# 存图
G = [[] for i in range(n+1)]
for _ in range(m):
u,v,w = map(int,input().split())
G[u].append([v,w])
dijkstra(1)