图（Graph）是一种数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象及其关系。在计算机科学中，图广泛用于建模各种现实世界中的问题，如社交网络、交通路线、通信网络等。
图的数据结构
图可以分为以下几种类型：
- 无向图（Undirected Graph） ：边没有方向，即 (u, v) 与 (v, u) 是相同的。
- 有向图（Directed Graph or Digraph） ：边有方向，即 (u, v) 与 (v, u) 是不同的。
- 加权图（Weighted Graph） ：边带有权重（权值），用于表示距离、成本等。
图的表示方法有两种主要方式：
- 邻接矩阵（Adjacency Matrix） ：
-
- 用一个二维数组表示图，矩阵中的元素表示顶点之间是否有边（及边的权重）。
- 优点：快速查找任意两点间是否有边。
- 缺点：对于稀疏图（边远少于顶点平方），空间复杂度较高。
# 例子：无向图的邻接矩阵表示
graph = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
- 邻接表（Adjacency List） ：
-
- 用一个数组（或字典）表示图，每个数组元素（或字典值）是一个列表，列表中存储与该顶点相邻的顶点。
- 优点：对于稀疏图，空间复杂度低。
- 缺点：查找任意两点间是否有边较慢。
# 例子：无向图的邻接表表示
graph = {
0: [1],
1: [0, 2, 3],
2: [1, 3],
3: [1, 2]
}
图的算法
遍历算法
- 深度优先搜索（DFS, Depth-First Search） ：
-
- 使用栈（递归）实现，从起始顶点出发，沿着边深入探索，直到无法继续为止，然后回溯。
- 适用于寻找路径、连通分量等。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in set(graph[start]) - visited:
dfs(graph, next, visited)
return visited
# 使用例子
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
print(dfs(graph, 0)) # 输出：{0, 1, 2, 3}
- 广度优先搜索（BFS, Breadth-First Search） ：
-
- 使用队列实现，从起始顶点出发，逐层向外扩展，直到访问所有顶点。
- 适用于寻找最短路径（无权图）。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
return visited
# 使用例子
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
print(bfs(graph, 0)) # 输出：{0, 1, 2, 3}
最短路径算法
- Dijkstra算法：
-
- 适用于加权有向图，计算从起始顶点到所有其他顶点的最短路径。
- 要求边的权重为非负数。
import heapq
def dijkstra(graph, start):
queue = [(0, start)]
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
while queue:
current_distance, current_vertex = heapq.heappop(queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# 使用例子
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}
}
print(dijkstra(graph, 'A')) # 输出：{'A': 0, 'B': 1, 'C': 3, 'D': 4}
- Bellman-Ford算法：
-
- 适用于加权有向图，计算从起始顶点到所有其他顶点的最短路径。
- 允许负权边，但不允许负权回路。
def bellman_ford(graph, start):
distance = {vertex: float('infinity') for vertex in graph}
distance[start] = 0
for _ in range(len(graph) - 1):
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distance[vertex] + weight < distance[neighbor]:
distance[neighbor] = distance[vertex] + weight
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distance[vertex] + weight < distance[neighbor]:
raise ValueError("Graph contains a negative-weight cycle")
return distance
# 使用例子
graph = {
'A': {'B': 1, 'C': 4},
'B': {'C': -2, 'D': 2},
'C': {},
'D': {'B': 1}
}
print(bellman_ford(graph, 'A')) # 输出：{'A': 0, 'B': 1, 'C': -1, 'D': 3}
最小生成树算法
- Kruskal算法：
-
- 适用于加权无向图，找到一棵包含所有顶点的最小生成树。
- 使用并查集（Union-Find）结构来检测环。
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 != root2:
if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
elif self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
else:
self.parent[root2] = root1
self.rank[root1] += 1
def kruskal(graph):
edges = sorted(graph['edges'], key=lambda edge: edge[2])
uf = UnionFind(graph['vertices'])
mst = []
for u, v, weight in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, weight))
return mst
# 使用例子
graph = {
'vertices': 4,
'edges': [
(0, 1, 10),
(0, 2, 6),
(0, 3, 5),
(1, 3, 15),
(2, 3, 4)
]
}
print(kruskal(graph)) # 输出：[(2, 3, 4), (0, 3, 5), (0, 1, 10)]
- Prim算法：
-
- 适用于加权无向图，找到一棵包含所有顶点的最小生成树。
- 使用优先队列（最小堆）来选择最小权重的边。
import heapq
def prim(graph, start):
mst = []
visited = set([start])
edges = [
(weight, start, to)
for to, weight in graph[start].items()
]
heapq.heapify(edges)
while edges:
weight, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, weight))
for to_next, weight in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (weight, to, to_next))
return mst
# 使用例子
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}
}
print(prim(graph, 'A')) # 输出： [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1)]
以上是图数据结构及相关算法的基本介绍和实现示例。这些算法在计算机科学中有着广泛的应用，理解它们的原理和实现对于解决实际问题非常有帮助。