python 图论算法模板

拓扑排序 求有向图的拓扑序列 时间复杂度 O(n+m), n 表示点数, m 表示边数

# in_deg[n] 各点的入度; adj=defaultdict(list) 字典存邻接表
def toposort() -> bool:
    for i in range(1, n+1):
        if in_deg[i] == 0: q.append(i)
    while q:
        node = q.popleft(); ans.append(node)
        for j in adj[node]:
            in_deg[j] -=1
            if in_deg[j] == 0:
                q.append(j)
    return len(ans) == n  # 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。

最短路算法

## 朴素 Dijkstra 求n号点到1号点的距离; 复杂度 O(n^2) 适用于非负权边稠密图
# grid邻接矩阵存储非负权边
def dijkstra() -> int:
    dist = [float('inf')] * (n+1); dist[1] = 0 # 初始化各点到1号点的距离
    st = [False] * (n+1) # 所有点都可分为两类: 已确定最短路的和未确定的
    for _ in range(n):
        t=-1
        for j in range(1,n+1):  # 找出本轮距离最小的点，并将其归为已确定的
            if not st[j] and (t==-1 or dist[t]>dist[j]):  t = j
        st[t] = True
        for j in range(1,n+1): # 用该点去更新其他点的距离
            dist[j] = min(dist[j], dist[t]+grid[t][j])
    if dist[n] >= float('inf')/2:  return -1  # 判断有解无解
    return dist[n]

# 添加有向有权边(a指向b,权重为c), 使用邻接表存储
def add(a,b,c): ##全局变量 h, idx, w, e, ne = [-1]*nn, 0, [0]*m, [0]*m, [-1]*m
    e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx; idx+=1
## 堆优化 Dijkstra 复杂度 O(mlogn) 适用于非负权边稀疏图(邻接表存储边)
def dijkstra() -> int: # inf=float('inf'); nn=n+1
    dist = [inf] * nn; dist[1] = 0
    heap = [(0,1)]
    while heap:
        d, ver = heappop(heap) # 使用刚更新的最短距离的点去更新其他点
        cur = h[ver]
        while cur!=-1:
            j = e[cur]
            if dist[j] > d + w[cur]: 
                dist[j] = d + w[cur]
                heappush(heap, (dist[j],j)) # 只有距离变小的点才会用于更新其他点
            cur = ne[cur]
    if dist[n] >= inf/2: return -1  # 判断有解无解
    return dist[n]

## Bellman-Ford 复杂度O(mn) 适用于带负权边图的最短路, 使用结构体存边 edges=[(a,b,w),...]
# 当要求不超过k条边的最短路，则只能用 Bellman-Ford
def bellman_ford() -> int:
    dist = [inf] * nn; dist[1] = 0
    for _ in range(k): # 求 1->n 的不超过k条边的最短路
        backup = dist.copy()
        for a,b,w in edges: dist[b] = min(dist[b], backup[a]+w)
    if dist[n] >= inf/2: return -1 # 不存在k条边以内的最短路
    return dist[n]
## SPFA 复杂度一般为O(n), 最差O(mn), 适用于带负权边图的最短路(邻接表存储边)
# 也称队列优化的Bellman-Ford算法, 同样可用于判断负环
def spfa() -> int: ##全局变量 h, idx, w, e, ne = [-1]*nn, 0, [0]*m, [0]*m, [-1]*m
    dist = [inf] * nn; dist[1] = 0
    q=deque(); q.append(1)
    st=[False]*nn; st[1]=True
    while q:
        ver = q.popleft(); st[ver]=False
        cur = h[ver]
        while cur!=-1:
            j = e[cur]
            if dist[j]>dist[ver]+w[cur]:
                dist[j]=dist[ver]+w[cur]
                if not st[j]: q.append(j); st[j]=True
            cur = ne[cur]
    if dist[n] >= inf/2: return -1 # 不存在 1->n 的最短路
    return dist[n]
## Floyd 复杂度O(n^3) 适用于多源汇最短路问题, 邻接矩阵更新到最后为两点间最短路
# g[N][N] 为邻接矩阵, 其中g[i][i]=0
def floyd() -> None:
    for k in range(1,nn):
        for i in range(1,nn):
            for j in range(1,nn):
                g[i][j] = min(g[i][j], g[i][k]+g[k][j])

最小生成树算法

## 朴素 Prim 算法 O(n^2 + m) 适用于稠密图, 邻接矩阵grid存边
def prim(): # dist[N]存储其他点到当前最小生成树的距离; st[N]存储每个点是否已经在生成树中
    dist=[inf]*nn; st=[False]*nn
    res=0 # 最小生成树的树边权重之和
    for i in range(n):
        t=-1 # 每一轮找到树外距离最近的点t, 用t更新树外的点到当前树的距离
        for j in range(1,nn): 
            if not st[j] and (t==-1 or dist[j]<dist[t]): t = j
        st[t]=True
        if i and dist[t]==inf: return inf # 不连通,没有最小生成树
        if i: res +=dist[t]
        for j in range(1,nn): # 用该点去更新树外的点到当前树的距离
            dist[j] = min(dist[j], grid[t][j])
    return res
## Kruskal 算法 O(mlogm)
def kruskal() -> int:
    edges.sort(key=lambda x:x[2])
    cnt=0; res=0
    for a,b,w in edges: # 按边权从小到大遍历
        a=find(a); b=find(b)
        if a!=b:  # 如果两节点不连通, 则添加连边
            p[a]=b; cnt+=1; res+=w
    if cnt!=n-1: return -1 # 最小生成树应该有n-1条边
    return res

二分图判定

$\mathcal{G}$是二分图当且仅当$\mathcal{G}$中不存在奇数环。二分图的各连通块是二分图。

# 染色法判定二分图 O(n+m) 邻接表存边
def bfs(u) -> bool:
    q=deque()
    color[u] = 0
    q.append([u,0])
    while q:
        i,c = q.popleft()
        cur=h[i]
        while cur!=-1: # 遍历点i的所有子节点,并染上相反的颜色
            j=e[cur]
            if color[j]==-1:
                color[j]=1-c; q.append([j,1-c])
            elif color[j]==c: return False
            cur=ne[cur]
    return True
flag=True
for i in range(1,nn): # 非连通图也可能是二分图
    if color[i]==-1: # 该连通块没有被染色过
        if not bfs(i):
            flag=False

匈牙利算法 O(nm) 求二分图的最大匹配

st=[False]*(n2+1); match=[0]*(n2+1) # match[j] 存右边点j的匹配对象
def find(u) -> bool: # 左边节点u能否匹配到右边节点
    cur=h[u]
    while cur!=-1:
        j=e[cur]
        if not st[j]:
            st[j] = True
            if not match[j] or find(match[j]): # 右边j没匹配过 或j的匹配对象match[j]可以找到下家
                match[j]=u; return True
        cur=ne[cur]
    return False
res=0
for i in range(1,n1+1):
    st=[False]*(n2+1)
    if find(i): res+=1