【机器学习】机器学习中用到的高等数学知识-8. 图论 (Graph Theory)
- 图的表示和遍历：用于处理社交网络、推荐系统等结构化数据。
图论是研究图（Graph）结构的数学分支，在处理网络、关系和结构化数据时起着至关重要的作用。本文将从图的基本表示、遍历算法及其在实际应用中的使用展开讨论，并配以代码和可视化示例。
1. 图的基本表示
1.1 定义
图由节点（顶点）和边组成。
- 无向图：边没有方向，如 (u, v) 表示节点 u 和 v 之间的连接。
- 有向图：边有方向，如 (u, v) 表示从节点 u 到 v 的连接。
1.2 表示方法
- 邻接矩阵：用 n × n 的矩阵表示，矩阵的元素表示节点之间是否有边。
- 邻接表：每个节点对应一个列表，存储与该节点相连的所有节点。
节点 1: [2, 3] 节点 2: [1, 4] 节点 3: [1]
1.3 Python 实现
import numpy as np
# 邻接矩阵
graph = np.array([
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0]
])
print("邻接矩阵:")
print(graph)
2. 图的遍历
2.1 深度优先搜索 (DFS)
DFS 按照深度优先的策略遍历节点，适用于寻找路径或检查连通性。
2.1.1 定义
深度优先搜索按照递归深入的方式访问节点，尽可能向深层的节点探索，直到无法继续，再回溯到上一层节点。
2.1.2 算法流程
- 从起始节点出发，标记为已访问。
- 访问其一个未访问的邻居节点。
- 对该邻居节点重复步骤 1 和 2。
- 如果当前节点的所有邻居都已访问，则回溯到上一个节点。
- 重复直到所有节点访问完毕。
2.1.3 Python 实现
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ") # 输出当前节点
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 示例图：邻接表表示
graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
print("深度优先搜索结果：")
dfs(graph, 1)
深度优先搜索结果：
1 2 4 3 5 2.1.4 应用案例
- 连通性检查：检查图是否是一个连通图。
- 路径探索：用于迷宫或网络中的路径查找。
2.1.5 可视化
import networkx as nx
import matplotlib.pyplot as plt
# 构建图
G = nx.Graph()
edges = [(1, 2), (1, 3), (2, 4), (3, 5)]
G.add_edges_from(edges)
# DFS 遍历
visited = []
def dfs_vis(graph, node):
if node not in visited:
visited.append(node)
for neighbor in list(graph.neighbors(node)):
dfs_vis(graph, neighbor)
dfs_vis(G, 1)
# 可视化
plt.figure(figsize=(6, 6))
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000)
nx.draw_networkx_nodes(G, pos, nodelist=visited, node_color='lightgreen')
plt.title("DFS Traversal")
plt.show()
2.2 广度优先搜索 (BFS)
BFS 按照层级优先的策略遍历节点，适用于寻找最短路径。
2.2.1 定义
广度优先搜索按照层级逐层访问节点，从起始节点出发，先访问所有直接邻居节点，再访问邻居的邻居，依次类推。
2.2.2 算法流程
- 从起始节点出发，将其加入队列并标记为已访问。
- 从队列中取出一个节点，访问并输出。
- 将该节点的所有未访问的邻居加入队列。
- 重复步骤 2 和 3，直到队列为空。
2.2.3 Python 实现
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start]) # 队列存储待访问节点
visited.add(start)
while queue:
node = queue.popleft() # 弹出队首节点
print(node, end=" ") # 输出当前节点
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 示例图：邻接表表示
graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
print("广度优先搜索结果：")
bfs(graph, 1)
广度优先搜索结果：
1 2 3 4 5 2.2.4 应用案例
- 最短路径搜索：寻找无权图中的最短路径。
- 社交网络分析：如推荐朋友、寻找关系链。
2.2.5 可视化
from collections import deque
import networkx as nx
import matplotlib.pyplot as plt
# 构建图
G = nx.Graph()
edges = [(1, 2), (1, 3), (2, 4), (3, 5)]
G.add_edges_from(edges)
# BFS 遍历
def bfs_vis(graph, start):
visited = []
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.append(node)
queue.extend(list(graph.neighbors(node)))
return visited
visited_bfs = bfs_vis(G, 1)
# 定义节点位置
pos = nx.spring_layout(G)
# 可视化
plt.figure(figsize=(6, 6))
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000)
nx.draw_networkx_nodes(G, pos, nodelist=visited_bfs, node_color='orange')
plt.title("BFS Traversal")
plt.show()
2.3 深度优先搜索 vs 广度优先搜索
| 特性 | 深度优先搜索 (DFS) | 广度优先搜索 (BFS) |
|---|---|---|
| 遍历策略 | 递归深入到最后再回溯 | 层级逐层访问 |
| 数据结构 | 栈（隐式递归栈） | 队列 |
| 实现难度 | 简单，递归实现 | 简单，队列实现 |
| 适用场景 | 连通性、路径探索 | 最短路径、层级分析 |
| 时间复杂度 | O(V + E) | O(V + E) |
| 空间复杂度 | O(V) | O(V) |
2.4 实际案例：寻找最短路径 (BFS 应用)
以下用 BFS 在无权图中寻找最短路径：
from collections import deque
def shortest_path_bfs(graph, start, end):
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
for neighbor in graph[node]:
if neighbor == end:
return path + [end]
elif neighbor not in path:
queue.append((neighbor, path + [neighbor]))
# 示例图
graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
print("最短路径:", shortest_path_bfs(graph, 1, 5))
最短路径: [1, 3, 5]最短路径: [1, 3, 5]
2.5 总结
- DFS：深入优先，适用于路径探索和检查连通性。
- BFS：层级优先，适用于最短路径和层次分析。
- 图的遍历在解决实际问题（如网络分析、导航优化）中有重要意义。
通过代码实现和可视化，你可以直观理解两种算法及其在不同场景下的适用性。
3. 图的可视化
3.1 用 NetworkX 可视化图
import networkx as nx
import matplotlib.pyplot as plt
# 创建图
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4)])
# 绘制图
plt.figure(figsize=(6, 6))
nx.draw(G, with_labels=True, node_color='skyblue', node_size=2000, edge_color='gray')
plt.title("Graph Representation")
plt.show()
4. 图的算法案例：最短路径
以 Dijkstra 算法为例，计算最短路径：
import heapq
def dijkstra(graph, start):
pq = []
heapq.heappush(pq, (0, start))
distances = {node: float('inf') for node in graph}
distances[start] = 0
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# 带权图
weighted_graph = {
1: [(2, 1), (3, 4)],
2: [(4, 2)],
3: [(4, 5)],
4: []
}
print("最短路径:", dijkstra(weighted_graph, 1))
最短路径: {1: 0, 2: 1, 3: 4, 4: 3}5. 实际应用详解
5.1 社交网络分析
应用背景
在社交网络中，每个用户可以被表示为一个节点，用户之间的好友关系、关注关系等用边表示。通过分析这种网络结构，可以实现好友推荐、影响力分析等功能。
实际举例
- 好友推荐
在 Facebook 或 LinkedIn 等平台中，利用图的遍历算法（如 BFS 或深度学习中的图神经网络），可以找到距离用户较近的未连接节点（共同好友多的用户），推荐为潜在朋友。
代码示例：好友推荐（BFS）
from collections import deque
def recommend_friends(graph, user):
visited = set()
queue = deque([user])
recommended = set()
while queue:
node = queue.popleft()
if node != user:
recommended.add(node)
for neighbor in graph[node]:
if neighbor not in visited and neighbor != user:
visited.add(neighbor)
queue.append(neighbor)
return recommended - set(graph[user])
# 社交网络图：节点表示用户，边表示好友关系
social_network = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
print("推荐好友:", recommend_friends(social_network, 'A'))
结果：
推荐好友: {'F', 'D', 'E'}5.2 推荐系统
应用背景
推荐系统利用用户的行为或偏好生成个性化内容推荐。在图中，节点可以表示用户或物品，边表示用户与物品的关联关系（如用户购买或点赞）。
实际举例
- 电影推荐
在 Netflix 中，用户和电影形成一个二部图，用户与电影的交互作为图的边。通过计算与用户兴趣相关的电影节点，可以实现推荐。
代码示例：兴趣图上的推荐
import networkx as nx
# 构建兴趣图
interest_graph = nx.Graph()
interest_graph.add_edges_from([
('User1', 'MovieA'), ('User1', 'MovieB'),
('User2', 'MovieB'), ('User2', 'MovieC'),
('User3', 'MovieA'), ('User3', 'MovieC')
])
# 推荐算法：找与用户连接节点共同邻居最多的节点
def recommend_movies(graph, user):
movies = set(graph.neighbors(user))
recommendations = {}
for movie in movies:
for neighbor in graph.neighbors(movie):
if neighbor != user and neighbor not in movies:
recommendations[neighbor] = recommendations.get(neighbor, 0) + 1
return sorted(recommendations, key=recommendations.get, reverse=True)
print("推荐电影:", recommend_movies(interest_graph, 'User1'))
结果：
推荐电影: ['User2', 'User3']5.3 最短路径问题
应用背景
最短路径问题广泛用于导航系统（如 Google Maps）、物流优化、通信网络等。在图中，节点表示位置或设备，边的权重表示距离或费用。
实际举例
- 导航系统
在 Google Maps 中，路网被表示为图，节点是路口，边是道路，权重是距离或时间。通过 Dijkstra 算法找到两个节点之间的最短路径。
代码示例：最短路径（Dijkstra 算法）
import heapq
def dijkstra(graph, start, end):
pq = [] # 优先队列
heapq.heappush(pq, (0, start)) # (距离, 节点)
distances = {node: float('inf') for node in graph}
distances[start] = 0
previous_nodes = {node: None for node in graph}
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node
heapq.heappush(pq, (distance, neighbor))
# 重建路径
path, node = [], end
while previous_nodes[node] is not None:
path.insert(0, node)
node = previous_nodes[node]
path.insert(0, start)
return path, distances[end]
# 路网图：节点表示路口，边权重表示距离
road_network = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
shortest_path, distance = dijkstra(road_network, 'A', 'D')
print("最短路径:", shortest_path)
print("路径距离:", distance)
结果：
最短路径: ['A', 'B', 'C', 'D']
路径距离: 45.4 总结
- 社交网络分析：通过 BFS 推荐潜在好友。
- 推荐系统：利用图算法分析用户兴趣关联，推荐内容。
- 最短路径问题：通过 Dijkstra 算法优化路径规划。
这些应用展示了图论在现实世界中的广泛用途，其背后依赖于高效的算法设计和图结构建模。
6. 总结
图论在机器学习中是强大的工具：
- 图表示学习：在图神经网络（GNN）中用于学习节点嵌入。
- 优化问题：如流量优化和任务调度。
- 复杂网络分析：如社区检测、页面排序等。
通过代码和图示，我们能更直观地理解图论，并将其用于各种实际场景中，进一步增强机器学习模型的表现力。