电子科技大学研一图论作业精讲与答案解析（含教师批注）
简介：图论是计算机科学与数学的重要分支，研究图的结构及其在实际问题中的应用。电子科技大学将图论设为研一核心课程，强调图的基本概念、常用算法及其实践应用。本资料包含四次图论作业的完整答案及教师详细讲解与批注，内容涵盖图的基础知识、遍历策略、路径优化、最小生成树、网络流问题、图的表示方式及复杂问题求解等，是一份极具参考价值的学习资源。
1. 图论基础概念解析
图论作为计算机科学与数学交叉的重要领域，广泛应用于社交网络、交通系统、推荐算法等多个场景。本章将从图的基本定义出发，逐步解析图的分类、顶点与边的关系、图的表示方式（如邻接矩阵与邻接表）以及图的基本性质。
图由 顶点（Vertex）集合 和 边（Edge）集合 组成，记作 $ G = (V, E) $，其中 $ V $ 表示顶点集合，$ E $ 表示边集合。根据边是否有方向，图可分为无向图和有向图。
以下是图的常见表示方式：
| 表示方式 | 描述 |
|---|---|
| 邻接矩阵 | 用二维数组存储顶点之间是否相连，适合稠密图 |
| 邻接表 | 用链表或数组存储每个顶点的邻接点，适合稀疏图 |
例如，邻接矩阵的实现如下：
# 邻接矩阵示例：含4个顶点的无向图
adj_matrix = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
上述矩阵中，若 adj_matrix[i][j] == 1 ，则表示顶点 $ i $ 与顶点 $ j $ 相连。邻接矩阵对称，说明是无向图。
通过本章学习，读者将掌握图的基本建模方法，为后续深入学习打下坚实基础。
2. 无向图与有向图特性
图是表示对象之间关系的数学结构，广泛应用于社交网络、交通网络、电路设计等领域。在图的分类中，无向图与有向图是最基本的两种形式，它们在结构、性质、应用场景上具有显著差异。本章将深入探讨无向图与有向图的基本性质，包括度数、连通性等核心概念，并通过对比分析揭示其在存储结构与建模方式上的异同，最后结合社交网络与交通网络的实际案例，说明其在现实问题中的应用。
2.1 无向图的基本性质
无向图（Undirected Graph）是由一组顶点（Vertex）和一组无序边（Edge）组成的图结构。边没有方向性，表示顶点之间的双向关系。无向图在表示对称关系时非常自然，例如好友关系、道路连接等。
2.1.1 边的无向性与顶点度数
在无向图中，边是无方向的。例如，若存在边 (u, v)，则该边连接顶点 u 和 v，且与 (v, u) 等价。顶点的度数（Degree）是指该顶点所连接的边的数量。
顶点度数的计算
以下是一个用邻接表表示无向图并计算顶点度数的 Python 示例代码：
# 邻接表表示无向图
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
# 计算每个顶点的度数
def calculate_degrees(graph):
degrees = {}
for vertex in graph:
degrees[vertex] = len(graph[vertex])
return degrees
degrees = calculate_degrees(graph)
print(degrees)
执行结果：
{0: 2, 1: 2, 2: 3, 3: 1}
代码分析：
-
graph是一个字典结构，表示邻接表。每个顶点对应一个列表，包含与它相连的其他顶点。 -
calculate_degrees函数遍历图中每个顶点，通过计算邻接表中列表的长度来确定该顶点的度数。 - 输出结果表示顶点 0 的度数为 2，顶点 1 的度数也为 2，顶点 2 的度数为 3，顶点 3 的度数为 1。
顶点度数与图的性质
- 孤立点 ：度数为 0 的顶点。
- 偶度点与奇度点 ：度数为偶数或奇数的顶点。
- 握手定理 ：无向图中所有顶点的度数之和等于边数的两倍。
2.1.2 连通性与连通分量
连通性是图论中非常重要的概念。在无向图中，如果两个顶点之间存在路径，则称这两个顶点是连通的。整个图如果任意两个顶点之间都连通，则称为 连通图 。否则，图由多个 连通分量 （Connected Components）组成。
连通分量的检测
我们可以使用深度优先搜索（DFS）来检测图中的连通分量：
def dfs(graph, start, visited):
stack = [start]
visited.add(start)
while stack:
vertex = stack.pop()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
def count_components(graph):
visited = set()
components = 0
for vertex in graph:
if vertex not in visited:
dfs(graph, vertex, visited)
components += 1
return components
# 示例图
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1],
3: [4],
4: [3],
5: []
}
print(count_components(graph)) # 输出：3
执行结果：
3
代码分析：
-
dfs函数使用栈实现深度优先搜索，标记所有从当前顶点出发能到达的节点。 -
count_components函数遍历所有顶点，调用dfs来找出所有未被访问的连通子图。 - 上图中包含三个连通分量：{0,1,2}、{3,4}、{5}。
连通分量的应用
- 社交网络分析 ：识别朋友圈、社区结构。
- 网络故障诊断 ：判断网络是否出现断开。
- 图像分割 ：将图像中的连通区域划分出来。
2.2 有向图的基本性质
有向图（Directed Graph 或 Digraph）是由一组顶点和一组有序边组成的图结构。边具有方向性，表示从一个顶点指向另一个顶点的关系。
2.2.1 有向边的方向性与顶点度数（入度与出度）
在有向图中，边是有方向的。例如，边 (u, v) 表示从 u 指向 v，与 (v, u) 是不同的。
顶点的度数分为 出度 （Out-degree）和 入度 （In-degree）：
- 出度 ：从该顶点出发的边的数量。
- 入度 ：指向该顶点的边的数量。
入度与出度的计算
以下是一个用邻接表表示有向图并计算入度和出度的 Python 示例：
# 邻接表表示有向图
digraph = {
0: [1, 2],
1: [2],
2: [3],
3: [0]
}
def calculate_in_out_degrees(graph):
out_degree = {v: len(graph[v]) for v in graph}
in_degree = {v: 0 for v in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
return in_degree, out_degree
in_deg, out_deg = calculate_in_out_degrees(digraph)
print("入度:", in_deg)
print("出度:", out_deg)
执行结果：
入度: {0: 1, 1: 1, 2: 2, 3: 1}
出度: {0: 2, 1: 1, 2: 1, 3: 1}
代码分析：
-
out_degree通过邻接表长度直接获取每个顶点的出度。 -
in_degree遍历所有边，统计每个顶点被指向的次数。
2.2.2 强连通性与弱连通性判断
在有向图中，连通性分为 强连通 （Strongly Connected）与 弱连通 （Weakly Connected）：
- 强连通 ：对于任意两个顶点 u 和 v，都存在从 u 到 v 的路径，且存在从 v 到 u 的路径。
- 弱连通 ：忽略边的方向后形成的无向图是连通的。
强连通分量检测（Kosaraju算法）
Kosaraju算法是一种经典的检测强连通分量（SCC）的算法，其基本步骤如下：
- 对原始图进行DFS，记录顶点完成时间。
- 构建图的逆图（Reverse Graph）。
- 按完成时间倒序对逆图进行DFS，每次DFS访问的顶点构成一个强连通分量。
以下是实现代码：
def kosaraju(graph):
visited = set()
order = []
def dfs1(u):
visited.add(u)
for v in graph[u]:
if v not in visited:
dfs1(v)
order.append(u)
for u in graph:
if u not in visited:
dfs1(u)
# 构建逆图
reverse_graph = {u: [] for u in graph}
for u in graph:
for v in graph[u]:
reverse_graph[v].append(u)
visited = set()
sccs = []
def dfs2(u, component):
visited.add(u)
component.append(u)
for v in reverse_graph[u]:
if v not in visited:
dfs2(v, component)
for u in reversed(order):
if u not in visited:
component = []
dfs2(u, component)
sccs.append(component)
return sccs
# 示例有向图
digraph = {
0: [1],
1: [2],
2: [0, 3],
3: [4],
4: [5],
5: [3]
}
print(kosaraju(digraph))
执行结果：
[[0, 2, 1], [3, 5, 4]]
代码分析：
- 第一次DFS（
dfs1）用于记录顶点的完成顺序。 - 构建逆图后，按完成顺序逆序进行DFS（
dfs2），每次DFS得到一个强连通分量。 - 本例中图包含两个强连通分量：[0,2,1] 和 [3,5,4]。
2.3 无向图与有向图的对比分析
无向图与有向图在表示方式、连通性判定、存储结构等方面存在显著差异。
2.3.1 存储结构上的差异
| 特性 | 无向图 | 有向图 |
|---|---|---|
| 邻接矩阵 | 对称矩阵，A[i][j] = A[j][i] | 非对称矩阵 |
| 邻接表 | 每条边存储两次（u, v）和（v, u） | 每条边只存储一次（u, v） |
| 存储空间 | O(V + 2E) | O(V + E) |
| 度数计算 | 仅需邻接表长度 | 需分别统计入度与出度 |
2.3.2 应用场景与问题建模方式
| 应用领域 | 适用图类型 | 建模方式说明 |
|---|---|---|
| 社交网络 | 无向图 | 表示双向关系，如好友关系 |
| 网页链接结构 | 有向图 | 表示网页之间的跳转关系 |
| 交通网络 | 有向图 | 表示单行道或有方向限制的道路 |
| 聊天通信网络 | 有向图 | 表示消息发送方向 |
| 图像分割 | 无向图 | 表示像素之间的连接关系 |
2.4 实践案例：社交网络与交通网络建模
2.4.1 使用无向图建模好友关系
在社交网络中，用户之间的好友关系通常是双向的。我们可以使用无向图来表示这种关系。
示例：使用 NetworkX 构建好友关系图
import networkx as nx
import matplotlib.pyplot as plt
# 创建无向图
G = nx.Graph()
# 添加节点（用户）
G.add_nodes_from([1, 2, 3, 4, 5])
# 添加边（好友关系）
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)])
# 绘制图
nx.draw(G, with_labels=True, node_color='lightblue')
plt.show()
mermaid流程图：
graph undirected
1 -- 2
1 -- 3
2 -- 3
3 -- 4
4 -- 5
分析：
- 顶点 1 与 2、3 是好友。
- 顶点 3 是中心节点，连接了 1、2、4。
- 可用于分析社交网络中的中心节点、社区划分等问题。
2.4.2 使用有向图建模道路通行方向
在交通网络中，道路可能存在单行限制。此时，使用有向图可以更准确地建模。
示例：使用 NetworkX 构建交通网络图
# 创建有向图
DG = nx.DiGraph()
# 添加节点（路口）
DG.add_nodes_from(['A', 'B', 'C', 'D'])
# 添加边（单向通行）
DG.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A'), ('B', 'D')])
# 绘制图
nx.draw(DG, with_labels=True, node_color='lightgreen', arrows=True)
plt.show()
mermaid流程图：
graph directed
A --> B
B --> C
C --> D
D --> A
B --> D
分析：
- 路口 B 可以通往 C 和 D，表示该路口有多条出口。
- D 可以返回 A，构成一个环路。
- 可用于路径规划、交通流量模拟等。
本章深入分析了无向图与有向图的基本性质、连通性判断方法，并通过代码实例展示了如何构建和分析图结构。通过对比其存储结构与应用场景，明确了不同类型图在实际建模中的适用性。在后续章节中，我们将进一步探讨图论中的路径问题，如欧拉路径与哈密顿路径，以及它们的判定与构造算法。
3. 欧拉路径与欧拉回路判定及构造
3.1 欧拉路径与欧拉回路的定义
3.1.1 路径与回路的基本区别
在图论中， 欧拉路径（Euler Path） 是指一条恰好经过图中每条边一次的路径；而 欧拉回路（Euler Circuit） 则是一条起点和终点相同的欧拉路径。换句话说，欧拉路径允许起点和终点不同，而欧拉回路要求起点与终点重合。
这两个概念的区别可以形象地理解为：
- 欧拉路径 ：你希望在一张地图上每条路都走一遍，但可以从不同的起点和终点出发与结束。
- 欧拉回路 ：你希望从一个点出发，走遍所有道路后，最终回到起点。
在实际应用中，这种区别影响了图的连通性和顶点度数的判断标准。
3.1.2 图中边的遍历次数限制
欧拉路径或回路的一个核心特性是：每条边必须恰好被访问一次，不允许重复也不允许遗漏。这与哈密顿路径或回路形成鲜明对比，后者关注的是顶点的唯一访问。
在实际问题中，比如城市道路清扫、邮递员路线优化等，这种“恰好访问一次”的限制使得欧拉路径/回路成为理想模型。它要求图必须满足特定的度数条件才能存在这样的路径或回路。
3.2 判定定理与条件分析
3.2.1 无向图中的欧拉路径与回路条件
对于无向图，存在欧拉路径或回路的判定条件如下：
| 类型 | 条件 |
|---|---|
| 欧拉回路 | 所有顶点的度数均为偶数，并且图是连通的 |
| 欧拉路径 | 恰好有两个顶点的度数为奇数，其余均为偶数，并且图是连通的 |
度数定义 ：无向图中一个顶点的度数是指与该顶点相连的边的数量。
示例说明
考虑一个无向图如下：
graph undirected
A -- B
B -- C
C -- D
D -- A
B -- D
该图中各顶点的度数如下：
| 顶点 | 度数 |
|---|---|
| A | 3 |
| B | 3 |
| C | 2 |
| D | 3 |
由于有三个顶点的度数为奇数，不满足欧拉路径的条件，因此该图不存在欧拉路径或回路。
3.2.2 有向图中的欧拉路径与回路条件
对于有向图，判断欧拉路径和回路的标准略有不同，主要基于顶点的入度和出度：
| 类型 | 条件 |
|---|---|
| 欧拉回路 | 所有顶点的入度等于出度，并且图是强连通的 |
| 欧拉路径 | 存在一个顶点出度比入度多1（起点），另一个顶点入度比出度多1（终点），其余顶点入度等于出度，并且图是弱连通的 |
入度 ：指向该顶点的边的数量
出度 ：从该顶点出发的边的数量
示例代码：判定有向图是否存在欧拉路径
from collections import defaultdict
def is_eulerian(graph, in_degree, out_degree):
# 检查是否满足欧拉路径/回路条件
start_count = end_count = 0
for node in graph:
if out_degree[node] - in_degree[node] == 1:
start_count += 1
elif in_degree[node] - out_degree[node] == 1:
end_count += 1
elif in_degree[node] != out_degree[node]:
return "No Euler Path or Circuit"
if start_count == 1 and end_count == 1:
return "Euler Path exists"
elif start_count == 0 and end_count == 0:
return "Euler Circuit exists"
else:
return "No Euler Path or Circuit"
# 构建图并计算入度出度
graph = defaultdict(list)
edges = [('A', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'D'), ('D', 'B')]
nodes = set()
in_degree = defaultdict(int)
out_degree = defaultdict(int)
for u, v in edges:
graph[u].append(v)
out_degree[u] += 1
in_degree[v] += 1
nodes.add(u)
nodes.add(v)
# 添加孤立点测试
nodes.add('E')
print(is_eulerian(graph, in_degree, out_degree))
代码逻辑分析
-
graph：使用邻接表存储图的结构。 -
in_degree和out_degree：分别记录每个顶点的入度和出度。 -
is_eulerian函数依次检查是否满足欧拉路径或回路的条件。 - 最后输出结果判断是否存在欧拉路径或回路。
参数说明
-
graph：有向图的邻接表表示。 -
in_degree：每个节点的入度字典。 -
out_degree：每个节点的出度字典。
3.3 构造算法与实现方法
3.3.1 Fleury算法的基本思想
Fleury算法是一种经典的构造欧拉路径或回路的算法，其核心思想是： 在构建路径时，优先选择非桥边（非割边）进行遍历，避免提前断开图的连通性 。
Fleury算法步骤：
- 选择起点（对于欧拉回路可任意选一个顶点，对于欧拉路径选择度为奇数的顶点）。
- 从当前顶点出发，选择一条未访问的边。
- 若有多条边可选，优先选择不是桥的边。
- 将该边加入路径，并从图中删除。
- 重复上述步骤，直到所有边都被访问。
Fleury算法的实现难点
- 如何判断某条边是否是桥？
- 图的连通性如何维护？
3.3.2 Hierholzer算法的实现流程
Hierholzer算法是更高效的一种构造欧拉路径或回路的方法，其时间复杂度为 O(E)，适用于大规模图。
算法流程：
- 从任意一个满足度数条件的顶点出发。
- 使用栈进行深度优先搜索（DFS），每次访问一条边后将其删除。
- 当无法继续前进时，将当前顶点加入结果路径。
- 最终将路径反转即可得到欧拉路径或回路。
示例代码：Hierholzer算法实现
from collections import defaultdict
def hierholzer(start, graph):
stack = [start]
path = []
while stack:
current = stack[-1]
if graph[current]:
next_node = graph[current].pop()
graph[next_node].remove(current) # 无向图需双向删除
stack.append(next_node)
else:
path.append(stack.pop())
return path[::-1]
# 构建一个无向图
graph = defaultdict(list)
edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A'), ('B', 'D')]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
start_node = 'A'
euler_path = hierholzer(start_node, graph)
print("欧拉路径:", euler_path)
代码逻辑分析
-
graph：使用邻接表表示无向图。 -
stack：模拟DFS递归调用栈。 -
path：用于保存最终的路径结果。 - 在每次无法继续遍历时，将顶点加入路径，最后反转路径即可得到正确顺序。
参数说明
-
start：起点顶点。 -
graph：邻接表形式的图结构。
3.4 实践应用：城市道路巡逻路径规划
3.4.1 问题建模与数据准备
城市道路巡逻路径规划可以建模为一个欧拉路径问题。假设某城市道路网络可以抽象为一个无向图，每条道路是一条边，每个交叉口是一个顶点。巡逻车希望从某一交叉口出发，遍历所有道路一次后返回起点或另一个交叉口。
数据结构建模
使用邻接表表示图：
graph = {
'A': ['B', 'D'],
'B': ['A', 'C', 'D'],
'C': ['B', 'D'],
'D': ['A', 'B', 'C']
}
该图中各顶点度数：
| 顶点 | 度数 |
|---|---|
| A | 2 |
| B | 3 |
| C | 2 |
| D | 3 |
满足欧拉路径的条件（两个顶点度数为奇数）。
3.4.2 算法实现与结果分析
使用 Hierholzer 算法求解欧拉路径：
def find_euler_path(graph):
# 统计度数
degrees = defaultdict(int)
for u in graph:
for v in graph[u]:
degrees[u] += 1
# 查找奇数度数顶点作为起点
start = next((u for u in degrees if degrees[u] % 2 == 1), next(iter(graph)))
return hierholzer(start, graph)
euler_path = find_euler_path(graph)
print("巡逻路径规划结果:", euler_path)
输出结果示例
巡逻路径规划结果: ['A', 'B', 'C', 'D', 'B', 'D', 'A']
结果分析
该路径表明巡逻车从 A 出发，依次经过 B、C、D、B、D、A，恰好访问每条道路一次，完成任务。
实际优化建议
- 如果图中存在多个连通分量，应分别处理。
- 对于有向图，应使用 Fleury 或 Hierholzer 的有向变种。
- 考虑交通拥堵、单行道等现实因素，可引入权重和方向性进行建模。
4. 哈密顿路径与回路问题
哈密顿路径与回路问题是图论中一个经典的NP难问题，其核心在于寻找一条路径或回路，使得图中的每个顶点恰好被访问一次。该问题在理论研究和实际应用中具有重要意义，尤其在路径规划、物流调度、网络优化等领域中经常被建模为哈密顿问题。本章将系统讲解哈密顿路径与回路的定义、判定方法、求解策略及其在实际问题中的应用。
4.1 哈密顿路径与回路的定义与区别
4.1.1 节点访问的唯一性要求
哈密顿路径（Hamiltonian Path）指的是图中一条路径，该路径经过图中每一个顶点且每个顶点仅被访问一次。而哈密顿回路（Hamiltonian Cycle）则是在哈密顿路径的基础上，起点与终点相同，形成一个闭合的回路。因此，哈密顿回路可以视为一种特殊的哈密顿路径。
哈密顿路径与欧拉路径的本质区别在于：欧拉路径关注的是边的遍历，要求每条边恰好被访问一次；而哈密顿路径关注的是节点的遍历，要求每个节点恰好被访问一次。
以下是一个哈密顿路径的简单示例：
A -- B -- C -- D
在这个图中，路径 A → B → C → D 是一个哈密顿路径，因为每个节点都被访问一次。
4.1.2 与欧拉路径的本质差异
欧拉路径和哈密顿路径虽然都属于图论路径问题，但它们的约束条件和求解难度截然不同：
| 特性 | 欧拉路径 | 哈密顿路径 |
|---|---|---|
| 访问对象 | 每条边恰好访问一次 | 每个节点恰好访问一次 |
| 判定复杂度 | 可在多项式时间内判定 | 属于NP难问题 |
| 是否允许重复节点 | 不允许重复边，允许重复节点 | 不允许重复节点 |
| 应用场景 | 道路巡逻、桥梁问题 | 旅行商问题、电路布线、调度问题 |
通过对比可以看出，哈密顿问题更复杂，尤其是在大规模图中难以高效求解。
4.2 哈密顿问题的判定难题
4.2.1 NP完全问题的背景
哈密顿回路问题被证明是NP完全问题（NPC），这意味着在当前已知的算法中，没有多项式时间内的精确解法。对于一个包含 n 个节点的图，穷举所有可能路径的时间复杂度高达 O(n!)，这对于大规模图来说是不可行的。
NP完全问题的特点包括：
- 问题的解可以在多项式时间内验证。
- 所有NP问题都可以在多项式时间内归约到该问题。
- 目前尚未发现能在多项式时间内求解的方法。
哈密顿回路问题属于经典的NPC问题之一，常用于算法复杂度理论的教学和研究。
4.2.2 回溯法与启发式算法的可行性
由于哈密顿问题的NP难性质，实际求解中通常采用如下方法：
- 回溯法（Backtracking） ：通过递归尝试构建路径，若路径不可行则回退。
- 启发式算法 ：如遗传算法、模拟退火、蚁群算法等，用于寻找近似最优解。
- 剪枝优化 ：在搜索过程中通过剪枝策略减少无效搜索路径。
以下是一个使用回溯法求解哈密顿路径的Python实现：
def hamiltonian_cycle(graph, start, path, visited, n):
if len(path) == n:
return path[0] in graph[path[-1]] # 检查是否能回到起点
for neighbor in graph[start]:
if not visited[neighbor]:
visited[neighbor] = True
path.append(neighbor)
if hamiltonian_cycle(graph, neighbor, path, visited, n):
return True
# 回溯
path.pop()
visited[neighbor] = False
return False
# 示例图
graph = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1, 3],
3: [1, 2]
}
n = len(graph)
path = [0]
visited = [False] * n
visited[0] = True
if hamiltonian_cycle(graph, 0, path, visited, n):
print("存在哈密顿回路：", path)
else:
print("不存在哈密顿回路")
代码逻辑分析：
-
graph是图的邻接表表示，每个节点存储其相邻节点。 -
path用于记录当前路径。 -
visited用于记录节点是否被访问。 - 函数
hamiltonian_cycle采用递归方式尝试构建路径。 - 当路径长度等于节点数时，检查是否能回到起点，形成回路。
- 若无法继续构建有效路径，则进行回溯操作。
参数说明：
-
graph：邻接表形式的图结构。 -
start：当前路径的起点。 -
path：当前路径列表。 -
visited：布尔数组，记录节点是否被访问。 -
n：图中节点总数。
4.3 常见求解策略与优化方法
4.3.1 深度优先搜索与剪枝优化
深度优先搜索（DFS）是解决哈密顿路径问题的常用方法之一。通过递归方式尝试构建路径，DFS可以穷举所有可能的路径。为了提升效率，通常结合剪枝策略，提前排除不可能形成哈密顿路径的分支。
以下是一个带有剪枝优化的DFS实现：
def dfs_hamiltonian(current, path, visited, graph, n):
if len(path) == n:
return path # 找到哈密顿路径
for neighbor in graph[current]:
if not visited[neighbor]:
visited[neighbor] = True
path.append(neighbor)
result = dfs_hamiltonian(neighbor, path, visited, graph, n)
if result:
return result
path.pop()
visited[neighbor] = False
return None
# 使用示例
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
n = 4
visited = [False] * n
visited[0] = True
path = [0]
result = dfs_hamiltonian(0, path, visited, graph, n)
print("哈密顿路径：" if result else "无解")
代码逻辑分析：
-
dfs_hamiltonian函数使用DFS递归方式尝试构建路径。 - 当路径长度等于节点总数时，返回当前路径。
- 每次选择未访问的邻居节点进行递归。
- 若路径不可行，进行回溯操作。
剪枝策略：
- 提前终止无效路径构建。
- 限制节点访问次数。
4.3.2 动态规划与近似解法
动态规划（DP）是解决某些哈密顿问题的另一种方法，尤其适用于较小规模图的最优解求解。例如，使用状态压缩动态规划可以在 O(n² * 2ⁿ) 的时间复杂度内求解哈密顿路径。
此外，对于大规模图，通常采用近似算法：
- 贪心算法 ：每次选择代价最小的可行节点。
- 模拟退火 ：通过概率接受劣解，跳出局部最优。
- 遗传算法 ：通过模拟生物进化过程寻找最优路径。
4.4 实践应用：旅行商问题（TSP）求解
4.4.1 TSP问题建模为哈密顿回路问题
旅行商问题（TSP）是最经典的组合优化问题之一，其目标是寻找一个最短的哈密顿回路，使得旅行商访问每个城市一次并最终回到起点。TSP可以建模为一个加权图的哈密顿回路问题，其中节点代表城市，边的权重代表城市之间的距离。
TSP问题的数学模型如下：
- 给定一个图 G(V, E)，其中 V 是城市集合，E 是城市之间的路径。
- 每条边 (i, j) ∈ E 有权重 w(i, j)，表示城市 i 和 j 之间的距离。
- 寻找一个回路，使得路径总长度最小，并且每个城市恰好访问一次。
4.4.2 启发式算法实现与性能对比
由于TSP是NP难问题，实际应用中常采用启发式算法进行求解。以下是几种常见算法的实现与对比：
1. 贪心算法（Nearest Neighbor）
def nearest_neighbor_tsp(graph, start):
path = [start]
current = start
total_cost = 0
unvisited = set(graph.keys()) - {start}
while unvisited:
next_node = min(unvisited, key=lambda x: graph[current][x])
total_cost += graph[current][next_node]
current = next_node
path.append(current)
unvisited.remove(current)
total_cost += graph[path[-1]][path[0]]
path.append(path[0]) # 返回起点
return path, total_cost
2. 模拟退火算法（Simulated Annealing）
模拟退火算法通过引入温度参数控制搜索过程，逐步降低温度以收敛到最优解。其核心步骤包括路径交换、评估新路径、以一定概率接受劣解。
3. 遗传算法（Genetic Algorithm）
遗传算法通过模拟自然选择和遗传变异，生成新一代路径。其核心步骤包括路径交叉、变异、选择最优个体。
性能对比表格：
| 算法类型 | 时间复杂度 | 精度 | 适用场景 |
|---|---|---|---|
| 贪心算法 | O(n²) | 中 | 小规模问题 |
| 模拟退火 | O(n² * T) | 高 | 中等规模问题 |
| 遗传算法 | O(G * n²) | 高 | 大规模复杂问题 |
其中 T 为迭代次数，G 为遗传代数。
通过本章的学习，读者可以深入理解哈密顿路径与回路问题的定义、判定难度、求解策略及其在实际问题中的应用。本章内容为后续更复杂的图论问题研究打下坚实基础。
5. 图的连通性分析与强连通判断
5.1 图的连通性基本概念
图的连通性是图论中的基础性质之一，用于描述图中节点之间是否可以通过边相互到达。对于无向图而言，如果任意两个顶点之间都存在路径，则称该图是 连通图 。否则，图由多个 连通分量 （Connected Components）组成。
在有向图中，连通性的定义更为复杂。若从顶点 $u$ 到顶点 $v$ 存在路径，并且从 $v$ 到 $u$ 也存在路径，则称这两个顶点是 强连通 （Strongly Connected）的。如果图中任意两个顶点之间都是强连通的，则该图是 强连通图 。若忽略边的方向后图是连通的，则称为 弱连通图 。
以下是一个简单的图示说明：
graph TD
A[节点A] -- 无向边 --> B[节点B]
B -- 无向边 --> C[节点C]
D[节点D] -- 无向边 --> E[节点E]
在上述无向图中，A、B、C 构成一个连通分量，D、E 构成另一个连通分量，因此整个图是不连通的。
5.2 连通性判定算法
5.2.1 基于DFS的连通分量检测
深度优先搜索（DFS）是一种常见的连通性判定方法，尤其适用于无向图。其基本思想是从任意一个未访问的顶点出发，进行DFS遍历，将所有能到达的顶点标记为已访问，从而划分出一个连通分量。
以下是一个使用DFS检测无向图连通分量的Python代码示例：
def dfs(graph, node, visited):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
def count_components(n, edges):
# 构建邻接表
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
components = 0
for i in range(n):
if not visited[i]:
dfs(graph, i, visited)
components += 1
return components
# 示例输入
n = 5 # 节点数
edges = [[0, 1], [1, 2], [3, 4]] # 边列表
print(count_components(n, edges)) # 输出：2
代码解释：
- graph ：使用邻接表存储图结构。
- visited ：记录每个节点是否被访问过。
- dfs 函数递归访问所有与当前节点相连的节点。
- count_components 遍历所有节点，若未访问则进行DFS，并计数连通分量。
5.2.2 Kosaraju算法与Tarjan算法简介
对于有向图的强连通分量（Strongly Connected Components, SCC）检测，常用的算法包括 Kosaraju算法 和 Tarjan算法 。
Kosaraju算法步骤如下：
1. 对原图进行一次DFS，按完成时间逆序记录节点。
2. 构造图的转置（即所有边方向反转）。
3. 按照第1步的顺序对转置图进行DFS，每次DFS访问的节点构成一个SCC。
以下是Kosaraju算法的Python实现：
def kosaraju(n, edges):
# 构建邻接表和逆邻接表
graph = [[] for _ in range(n)]
reverse_graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
reverse_graph[v].append(u)
visited = [False] * n
order = []
def dfs1(u):
visited[u] = True
for v in graph[u]:
if not visited[v]:
dfs1(v)
order.append(u)
def dfs2(u, component):
visited[u] = True
component.append(u)
for v in reverse_graph[u]:
if not visited[v]:
dfs2(v, component)
# 第一次DFS获取完成顺序
for i in range(n):
if not visited[i]:
dfs1(i)
# 第二次DFS在逆图中寻找SCC
visited = [False] * n
scc_list = []
for u in reversed(order):
if not visited[u]:
component = []
dfs2(u, component)
scc_list.append(component)
return scc_list
# 示例输入
n = 5
edges = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]]
print(kosaraju(n, edges)) # 输出：[[0, 2, 1], [3], [4]]
代码说明：
- dfs1 用于获取节点完成顺序。
- dfs2 用于在逆图中查找SCC。
- order 保存节点完成顺序。
- scc_list 存储最终的强连通分量列表。
5.3 强连通分量的划分与应用
5.3.1 强连通分量的定义与划分方法
强连通分量（SCC）是指在有向图中，极大子图中任意两个节点都相互可达。Kosaraju算法和Tarjan算法都能高效地将图划分为若干个SCC。
5.3.2 在复杂网络中的应用实例
SCC在复杂网络分析中具有广泛的应用，例如：
| 应用场景 | 应用方式 |
|---|---|
| 网络爬虫 | 判断网页之间的可达性，避免死循环 |
| 社交网络分析 | 发现高度互相关联的用户群组 |
| 软件依赖分析 | 检测循环依赖，避免死锁 |
| 网络安全 | 分析恶意软件传播路径 |
例如，在社交网络中，强连通分量可用于识别“紧密联系”的用户群体，帮助平台进行用户分群、推荐系统优化等操作。
5.4 实践应用：网络拓扑结构分析
5.4.1 判断网络节点的可达性
在实际网络拓扑中，节点之间的可达性直接影响网络的稳定性和冗余设计。我们可以使用DFS或BFS算法快速判断两个节点之间是否可达。
def is_reachable(graph, start, end):
visited = [False] * len(graph)
stack = [start]
visited[start] = True
while stack:
node = stack.pop()
if node == end:
return True
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
stack.append(neighbor)
return False
# 示例输入
graph = [
[1, 2], # 节点0的邻居
[0, 3], # 节点1的邻居
[0], # 节点2的邻居
[1, 4], # 节点3的邻居
[3] # 节点4的邻居
]
print(is_reachable(graph, 0, 4)) # 输出：True
5.4.2 分析网络故障与节点冗余设计
在大规模网络中，节点或边的故障可能导致网络断连。通过连通性分析，可以识别关键节点和冗余路径，从而优化网络设计。
例如，若某节点位于多个连通分量之间，则它可能是 桥接节点 ，其故障将导致网络分裂。我们可以通过以下步骤检测桥接节点：
- 使用DFS遍历图，记录发现时间（Discovery Time）和最低可达时间（Low Value）。
- 若某边的子节点的Low值大于父节点的发现时间，则该边是 桥边 （Bridge Edge）。
此方法将在后续章节中详细展开。
简介：图论是计算机科学与数学的重要分支，研究图的结构及其在实际问题中的应用。电子科技大学将图论设为研一核心课程，强调图的基本概念、常用算法及其实践应用。本资料包含四次图论作业的完整答案及教师详细讲解与批注，内容涵盖图的基础知识、遍历策略、路径优化、最小生成树、网络流问题、图的表示方式及复杂问题求解等，是一份极具参考价值的学习资源。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
8
0- 0
已为社区贡献22条内容
所有评论(0)