06图
06图
1. 定义与基本概念
- 无向图：边是顶点的无序对，即边没有方向性。
- 有向图：其边是顶点的有序对，即边有方向性。
- 连通分量：无向图中的极大连通子图。
- 连通图：如果对于无向图 G 中任意两个顶点都是连通的，则称 G 是连通图。
- 强连通分量：有向图中的极大强连通子图称作有向图的强连通分量。
- 生成树：一个连通图 G 的一个包含所有顶点的极小连通子图 T 是包含 G 的所有顶点 n 个，T 为连通子图，T 包含的边数最少。则 T 是一棵有 n 个顶点，n-1 条边的生成树。
2. 存储结构
2.1 顺序存储
邻接矩阵
graph = [[0] * n for _ range(n)]
2.2 链式存储
邻接表
graph = defaultdict(list)
graph[v].append(u)
3. 遍历
3.1 深度优先 DFS
递归实现
visited = set()
def dfs(v):
visited.add(v)
for u in graph[v]:
if u not in visited:
dfs(u)
栈实现
def dfs(start):
visited = set()
stack = [start]
while stack:
v = stack.pop()
if v not in visited:
visited.add(v)
for u in reversed(graph[v]):
if u not in visited:
stack.append(u)
3.2 广度优先 BFS
队列实现
def bfs(start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
v = queue.popleft()
for u in graph[v]:
if u not in visited:
visited.add(u)
queue.append(u)
4. 连通性问题
4.1 Prim 算法
def prim(start):
visited = set()
heap = [(0, start)]
total_weight = 0
while heap:
weight, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
total_weight += weight
for v, w in graph[u]:
if v not in visited:
heapq.heappush(heap, (w, v))
return total_weight
时间复杂度为 ，空间复杂度为 。
4.2 Kruskal 算法
需要使用并查集
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
def find(self, u):
if (par := self.parent[u]) != u:
self.parent[u] = self.find(par)
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
rank_u = self.rank[root_u]
rank_v = self.rank[root_v]
if rank_u > rank_v:
self.parent[root_v] = root_u
elif rank_v > rank_u:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal():
edges.sort(key=lambda x: x[-1])
total_weight = 0
uf = UnionFind()
for u, v, w in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
total_weight += w
return total_weight
时间复杂度为 ，空间复杂度为 。
5. 有向无环图及其应用
5.1 拓扑排序
def topo_sort(graph):
indegrees = {node: 0 for node in graph}
for neighbors in graph.values():
for n in neighbors:
indegrees[n] += 1
queue = deque(
node for node, indegree in indegrees.items() if indegree == 0
)
topo_order = []
while queue:
node = queue.popleft()
topo_order.append(node)
for neighbor in graph[node]:
indegrees[neighbor] -= 1
if indegrees[neighbor] == 0:
queue.append(neighbor)
return topo_order
时间复杂度为 ，空间复杂度为 。
5.2 判断是否有环
拓扑排序，判断 len(topo_order) == n 即可。
或者 DPS：
def has_cycle(graph):
def dfs(node):
if state[node] == ON_PATH:
return True
if state[node] == VISITED:
return False
state[node] = ON_PATH
for neighbor in graph[node]:
if dfs(neighbor):
return True
state[node] = VISITED
return False
state = {node: UNVISITED for node in graph}
for node in graph:
if state[node] == UNVISITED:
if dfs(node):
return True
return False
时间复杂度为 ，空间复杂度为 。
6. 最短路径
6.1 Dijkstra 算法
def dijkstra(start):
distance = [float("inf")] * n
distance[start] = 0
heap = [(0, start)]
while heap:
dist, u = heapq.heappop(heap)
if dist > distance[u]:
continue
for v, weight in graph[u]:
if (new_dist := distance[u] + weight) < distance[v]:
distance[v] = new_dist
heapq.heappush(heap, (v, new_dist))
return distance
时间复杂度为 ，空间复杂度为 。
6.2 Floyd 算法
def floyd():
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u in range(n):
for v, weight in graph[u]:
dist[u][v] = weight
for i in range(n):
for j in range(n):
for k in range(n):
if (new_dist := dist[i][k] + dist[k][j]) < dist[i][j]:
dist[i][j] = new_dist
return dist
时间复杂度为 ，空间复杂度为 。