并查集
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
遞歸技巧
鏈接, 在遞歸函數(shù)的開頭奸远，調(diào)用 printIndent(count++) 并打印關(guān)鍵變量劲适；然后在所有 return 語句之前調(diào)用 printIndent(--count) 并打印返回值。
// 全局變量惧笛，記錄遞歸函數(shù)的遞歸層數(shù)
int count = 0;
// 輸入 n葛菇，打印 n 個 tab 縮進(jìn)
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
# 防止走回頭路進(jìn)入死循環(huán)
if visited[v]:
return
# 前序遍歷位置甘磨，標(biāo)記節(jié)點(diǎn) v 已訪問
visited[v] = True
for neighbor in graph.neighbors(v):
traverse(graph, neighbor)
visited = []
# 另一種圖遍歷寫法
visited = []
def traverse(graph: Graph, v: int) -> None:
# 前序遍歷位置，標(biāo)記節(jié)點(diǎn) v 已訪問
visited[v] = True
for neighbor in graph.neighbors(v):
if not visited[neighbor]:
# 只遍歷沒標(biāo)記過的相鄰節(jié)點(diǎn)
traverse(graph, neighbor)
BFS
- BFS可以找到最短路徑, 但是空間復(fù)雜度高眯停，而 DFS 的空間復(fù)雜度較低
- 如果知道重終點(diǎn)在哪济舆，可以使用雙向BFS，從終點(diǎn)開始也搜索莺债。時間復(fù)雜度不變滋觉，運(yùn)行速度更快。
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() # 核心數(shù)據(jù)結(jié)構(gòu)
visited = set() # 避免走回頭路
q.append(start) # 將起點(diǎn)加入隊(duì)列
visited.add(start)
step = 0 # 記錄擴(kuò)散的步數(shù)
while q:
step += 1
size = len(q)
# 將當(dāng)前隊(duì)列中的所有節(jié)點(diǎn)向四周擴(kuò)散
for i in range(size):
cur = q.popleft()
# 劃重點(diǎn)：這里判斷是否到達(dá)終點(diǎn)
if cur == target:
return step
# 將cur相鄰節(jié)點(diǎn)加入隊(duì)列
for x in cur.neighbors:
if x not in visited:
q.append(x)
visited.add(x)
# 如果走到這里九府，說明在圖中沒有找到目標(biāo)節(jié)點(diǎn)
return -1
DFS （回溯算法）
多源最短路徑 Floyd
適用于加權(quán)有向圖椎瘟，能夠處理負(fù)權(quán)重的邊，但不能有回路侄旬。
Flyod是處理多源最短路徑（任意 2 點(diǎn)）肺蔚，時間復(fù)雜度為O（n^3） 空間復(fù)雜度為O（n ^ 2）;
如果是任意兩個點(diǎn)之間的最短路徑或者是負(fù)權(quán)圖，就用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算法是一種用于計(jì)算單源（從單獨(dú)s到其他任意node t宣羊，或給定某一個 node t）最短路徑的經(jīng)典算法璧诵。它適用于加權(quán)有向圖，但要求所有邊的權(quán)重為非負(fù)數(shù)仇冯。O(N^2)之宿，如果用堆優(yōu)化會更低（O((V+E)logV)）。
所以題目中如果是單源點(diǎn)正權(quán)圖苛坚，就用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比被，可以處理負(fù)權(quán)重。和dijkstra算法的區(qū)別是不使用小頂堆（本質(zhì)是個貪心）泼舱，B-F是個動態(tài)規(guī)劃等缀，要全部遍歷, 復(fù)雜度是 O(V*E)。
bellman-ford適合稠密的小圖娇昙，或者帶負(fù)權(quán)重的邊尺迂，dijkstra適合稀疏的大圖。
class Graph:
def __init__(self, vertices):
self.V = vertices # 頂點(diǎn)數(shù)
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
# 檢測負(fù)權(quán)環(huán)
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
# 打印結(jié)果
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算法
并查集基礎(chǔ)上冒掌，對edge排序噪裕，每次加入weight最小的，不連通的邊股毫。
prim算法
切分定理:
對于任意一種「切分」膳音，其中權(quán)重最小的那條「橫切邊」一定是構(gòu)成最小生成樹的一條邊。
