并查集
class UF:
def __init__(self, n):
self.parents = list(range(n))
self.count = n
def find(self, v):
if self.parents[v] !=v:
self.parents[v] = self.find(self.parents[v])
return self.parents[v]
def union(self, u, v):
parent_u = self.find(u)
parent_v = self.find(v)
if parent_u != parent_v:
self.parents[parent_v] = parent_u
self.count -= 1
def count(self):
return self.count
递归技巧
链接, 在递归函数的开头，调用 printIndent(count++) 并打印关键变量；然后在所有 return 语句之前调用 printIndent(--count) 并打印返回值。
// 全局变量，记录递归函数的递归层数
int count = 0;
// 输入 n，打印 n 个 tab 缩进
void printIndent(int n) {
for (int i = 0; i < n; i++) {
printf(" ");
}
}
# 二叉树遍历框架
def traverse(root):
if not root:
return
traverse(root.left);
traverse(root.right);
# 多叉树遍历框架
def traverse(root):
if not root:
return
for child in root.children:
traverse(child)
# 图遍历框架
def traverse(graph, v):
global visited
# 防止走回头路进入死循环
if visited[v]:
return
# 前序遍历位置，标记节点 v 已访问
visited[v] = True
for neighbor in graph.neighbors(v):
traverse(graph, neighbor)
visited = []
# 另一种图遍历写法
visited = []
def traverse(graph: Graph, v: int) -> None:
# 前序遍历位置，标记节点 v 已访问
visited[v] = True
for neighbor in graph.neighbors(v):
if not visited[neighbor]:
# 只遍历没标记过的相邻节点
traverse(graph, neighbor)
BFS
- BFS可以找到最短路径, 但是空间复杂度高，而 DFS 的空间复杂度较低
- 如果知道重终点在哪，可以使用双向BFS，从终点开始也搜索。时间复杂度不变，运行速度更快。
from typing import List, Set
from collections import deque
class Node:
def __init__(self, val: int):
self.val = val
self.neighbors = []
def BFS(start: Node, target: Node) -> int:
q = deque() # 核心数据结构
visited = set() # 避免走回头路
q.append(start) # 将起点加入队列
visited.add(start)
step = 0 # 记录扩散的步数
while q:
step += 1
size = len(q)
# 将当前队列中的所有节点向四周扩散
for i in range(size):
cur = q.popleft()
# 划重点：这里判断是否到达终点
if cur == target:
return step
# 将cur相邻节点加入队列
for x in cur.neighbors:
if x not in visited:
q.append(x)
visited.add(x)
# 如果走到这里，说明在图中没有找到目标节点
return -1
DFS （回溯算法）
多源最短路径 Floyd
适用于加权有向图，能够处理负权重的边，但不能有回路。
Flyod是处理多源最短路径（任意 2 点），时间复杂度为O（n^3） 空间复杂度为O（n ^ 2）;
如果是任意两个点之间的最短路径或者是负权图，就用Floyd；
# Floyd-Warshall Algorithm Implementation
# Define a large value for infinity
INF = float('inf')
def floyd_warshall(graph):
# Number of vertices in the graph
num_vertices = len(graph)
# Initialize the distance matrix with the same values as the graph matrix
dist = [[graph[i][j] for j in range(num_vertices)] for i in range(num_vertices)]
# Apply Floyd-Warshall algorithm
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
# Update the distance matrix
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# Example usage
graph = [
[0, 3, INF, INF],
[2, 0, INF, INF],
[INF, 7, 0, 1],
[6, INF, INF, 0]
]
shortest_paths = floyd_warshall(graph)
print("The shortest path matrix is:")
for row in shortest_paths:
print(row)
单源最短路径
Dijkstra算法是一种用于计算单源（从单独s到其他任意node t，或给定某一个 node t）最短路径的经典算法。它适用于加权有向图，但要求所有边的权重为非负数。O(N^2)，如果用堆优化会更低（O((V+E)logV)）。
所以题目中如果是单源点正权图，就用Dijkstra
import heapq
def dijkstra(graph, start, end):
# Priority queue to store (distance, vertex) tuples
pq = [(0, start)]
# Dictionary to store the shortest distance to each vertex
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
# Dictionary to store the shortest path to each vertex
previous_vertices = {vertex: None for vertex in graph}
while pq:
# Get the vertex with the smallest distance
current_distance, current_vertex = heapq.heappop(pq)
# If we have reached the end vertex, we can stop
if current_vertex == end:
break
# Explore neighbors
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# If a shorter path to the neighbor is found
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_vertices[neighbor] = current_vertex
heapq.heappush(pq, (distance, neighbor))
# Reconstruct the shortest path
path = []
current_vertex = end
while previous_vertices[current_vertex] is not None:
path.append(current_vertex)
current_vertex = previous_vertices[current_vertex]
path.append(start)
path.reverse()
return path, distances[end]
# Example usage
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_node = 'A'
end_node = 'D'
path, distance = dijkstra(graph, start_node, end_node)
print(f"The shortest path from {start_node} to {end_node} is: {path} with distance {distance}")
bellman-ford 算法
更加通用版本的 dijkstra，可以处理负权重。和dijkstra算法的区别是不使用小顶堆（本质是个贪心），B-F是个动态规划，要全部遍历, 复杂度是 O(V*E)。
bellman-ford适合稠密的小图，或者带负权重的边，dijkstra适合稀疏的大图。
class Graph:
def __init__(self, vertices):
self.V = vertices # 顶点数
self.edges = [] # 边的列表
def add_edge(self, u, v, weight):
self.edges.append((u, v, weight))
def bellman_ford(self, source):
# 初始化距离
dist = [float('inf')] * self.V
dist[source] = 0
# 松弛所有边 V-1 次
for _ in range(self.V - 1):
for u, v, weight in self.edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
# 检测负权环
for u, v, weight in self.edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
print("Graph contains a negative weight cycle")
return
# 打印结果
for i in range(self.V):
print(f"Distance from source {source} to vertex {i} is {dist[i]}")
# 示例用法
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 1, 1)
g.add_edge(3, 2, 5)
g.add_edge(4, 3, -3)
g.bellman_ford(0)
最小生成树
kruskal算法
并查集基础上，对edge排序，每次加入weight最小的，不连通的边。
prim算法
切分定理:
对于任意一种「切分」，其中权重最小的那条「横切边」一定是构成最小生成树的一条边。
