本文目录导读：
我来详细介绍Python中图算法的实现方法,包括图的表示和核心算法。
图的表示方法
邻接矩阵
class AdjMatrix:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0] * vertices for _ in range(vertices)]
def add_edge(self, u, v, weight=1):
self.graph[u][v] = weight
self.graph[v][u] = weight # 无向图
# 使用示例
g = AdjMatrix(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
邻接表（推荐）
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v, weight=1):
self.graph[u].append((v, weight))
# 无向图加上：self.graph[v].append((u, weight))
def display(self):
for vertex in self.graph:
print(f"{vertex}: {self.graph[vertex]}")
# 使用示例
g = Graph()
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 3)
g.add_edge(1, 2, 1)
图的遍历算法
广度优先搜索 (BFS)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print()
# 使用示例
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
bfs(graph, 0) # 输出: 0 1 2 3
深度优先搜索 (DFS)
def dfs_recursive(graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# 迭代版本
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
print(vertex, end=" ")
stack.extend(reversed(graph[vertex]))
# 使用示例
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
dfs_recursive(graph, 0) # 输出: 0 1 3 2
最短路径算法
Dijkstra算法（单源最短路径）
import heapq
def dijkstra(graph, start):
# 初始化距离字典
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
pq = [(0, start)] # (距离, 顶点)
while pq:
current_distance, current_vertex = heapq.heappop(pq)
# 如果当前距离大于已知距离，跳过
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(pq, (distance, neighbor))
return distances
# 使用示例
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
'D': {'B': 5, 'C': 8, 'E': 2},
'E': {'C': 10, 'D': 2}
}
distances = dijkstra(graph, 'A')
print(f"最短路径: {distances}") # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}
Floyd-Warshall算法（所有顶点对最短路径）
def floyd_warshall(graph):
n = len(graph)
dist = [[float('inf')] * n for _ in range(n)]
# 初始化
for i in range(n):
for j in range(n):
if i == j:
dist[i][j] = 0
elif j in graph[i]:
dist[i][j] = graph[i][j]
# 动态规划
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
最小生成树算法
Kruskal算法
class UnionFind:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, vertex):
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]
def union(self, v1, v2):
root1, root2 = self.find(v1), self.find(v2)
if root1 != root2:
if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
elif self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
else:
self.parent[root2] = root1
self.rank[root1] += 1
def kruskal_mst(graph):
edges = []
for u in graph:
for v, w in graph[u].items():
edges.append((w, u, v))
edges.sort()
vertices = list(graph.keys())
uf = UnionFind(vertices)
mst = []
for weight, u, v in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, weight))
return mst
# 使用示例
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
'D': {'B': 5, 'C': 8, 'E': 2},
'E': {'C': 10, 'D': 2}
}
mst = kruskal_mst(graph)
print(f"最小生成树: {mst}")
# [('B', 'C', 1), ('A', 'C', 2), ('D', 'E', 2), ('B', 'D', 5)]
拓扑排序
from collections import defaultdict, deque
def topological_sort(vertices, edges):
# 构建图的入度
in_degree = {v: 0 for v in vertices}
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# 将所有入度为0的顶点加入队列
queue = deque([v for v in vertices if in_degree[v] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != len(vertices):
print("图中存在环！")
return None
return result
# 使用示例
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('D', 'E')]
order = topological_sort(vertices, edges)
print(f"拓扑排序: {order}") # ['A', 'C', 'B', 'D', 'E']
完整案例：社交网络分析
class SocialNetwork:
def __init__(self):
self.graph = defaultdict(set)
def add_friendship(self, person1, person2):
self.graph[person1].add(person2)
self.graph[person2].add(person1)
def friends_count(self, person):
return len(self.graph[person])
def shortest_path(self, start, end):
"""使用BFS找最短路径"""
visited = {start}
queue = deque([(start, [start])])
while queue:
person, path = queue.popleft()
for friend in self.graph[person]:
if friend == end:
return path + [friend]
if friend not in visited:
visited.add(friend)
queue.append((friend, path + [friend]))
return None
def find_communities(self):
"""查找连通分量"""
visited = set()
communities = []
for person in self.graph:
if person not in visited:
community = []
queue = deque([person])
visited.add(person)
while queue:
current = queue.popleft()
community.append(current)
for friend in self.graph[current]:
if friend not in visited:
visited.add(friend)
queue.append(friend)
communities.append(community)
return communities
def suggest_friends(self, person, max_suggestions=5):
"""基于共同好友推荐"""
if person not in self.graph:
return []
suggestions = defaultdict(int)
# 遍历朋友的朋友
for friend in self.graph[person]:
for friend_of_friend in self.graph[friend]:
if (friend_of_friend != person and
friend_of_friend not in self.graph[person]):
suggestions[friend_of_friend] += 1
# 按共同好友数量排序
sorted_suggestions = sorted(suggestions.items(),
key=lambda x: x[1],
reverse=True)
return sorted_suggestions[:max_suggestions]
# 使用示例
network = SocialNetwork()
network.add_friendship("Alice", "Bob")
network.add_friendship("Alice", "Charlie")
network.add_friendship("Bob", "David")
network.add_friendship("Charlie", "David")
network.add_friendship("David", "Eve")
# 查找最短路径
path = network.shortest_path("Alice", "Eve")
print(f"Alice到Eve的最短路径: {path}")
# 朋友推荐
suggestions = network.suggest_friends("Alice")
print(f"为Alice推荐的朋友: {suggestions}")
性能优化建议
# 使用NumPy加速矩阵操作
import numpy as np
def floyd_warshall_fast(adj_matrix):
n = len(adj_matrix)
dist = np.array(adj_matrix, dtype=float)
for k in range(n):
dist = np.minimum(dist,
dist[:, np.newaxis, k] + dist[k, :])
return dist
# 使用缓存的DFS
from functools import lru_cache
@lru_cache(maxsize=None)
def adjacency_list(vertex):
# 缓存邻接列表计算
pass
这些Python图算法实现涵盖了常见的图处理需求,可以根据具体场景选择合适的算法和数据结构。
