图论相关算法
原创大约 18 分钟
图论
图论是数学的一个分支，主要研究图（graph）的性质和应用。图由顶点（节点）和连接这些顶点的边（链接）组成，广泛应用于计算机科学、网络分析、交通规划等领域。以下是图论的一些基本概念和知识。
基本概念
图 (Graph)：
- 由顶点集合 ( V ) 和边集合 ( E ) 组成的二元组 ( G = (V, E) )。
无向图 (Undirected Graph)：
- 边没有方向，表示为无序对 ( e = {u, v} )，其中 ( u, v \in V )。
- 无向图的边是对称的。
有向图 (Directed Graph)：
- 边有方向，表示为有序对 ( e = (u, v) )，其中 ( u, v \in V )。
- 有向图的边是非对称的。
度 (Degree)：
- 无向图：顶点 ( v ) 的度是连接到 ( v ) 的边的数量，记为 ( \deg(v) )。
- 有向图：顶点 ( v ) 的入度是指向 ( v ) 的边的数量，记为 ( \deg^-(v) )。出度是从 ( v ) 出发的边的数量，记为 ( \deg^+(v) )。
路径 (Path)：
- 顶点和边的序列，其中每条边都连接前一个顶点和后一个顶点。
- 路径的长度是所经过的边的数量。
简单路径 (Simple Path)：
- 不包含重复顶点的路径。
环 (Cycle)：
- 起点和终点相同的路径，且除起点和终点外不包含重复顶点。
连通图 (Connected Graph)：
- 无向图中任意两个顶点间都有路径。
强连通图 (Strongly Connected Graph)：
- 有向图中任意两个顶点 ( u ) 和 ( v ) 间都有路径。
图的表示方法
- 邻接矩阵 (Adjacency Matrix)：
- 对于一个有 ( n ) 个顶点的图 ( G )，邻接矩阵是一个 ( n \times n ) 的矩阵 ( A )，其中：
- ( A[i][j] = 1 ) 表示存在一条从顶点 ( i ) 到顶点 ( j ) 的边。
- 无向图的邻接矩阵是对称的，有向图的邻接矩阵一般是非对称的。
- 对于一个有 ( n ) 个顶点的图 ( G )，邻接矩阵是一个 ( n \times n ) 的矩阵 ( A )，其中：
% 邻接矩阵示例
A = [0, 1, 0;
1, 0, 1;
0, 1, 0];- 邻接表 (Adjacency List)：
- 使用列表（或数组）表示每个顶点的邻接顶点。
- 更节省空间，适用于稀疏图。
% 邻接表示例（使用cell数组）
adjList = {[2], [1, 3], [2]};- 边列表 (Edge List)：
- 使用边的集合来表示图，其中每条边是顶点对。
% 边列表示例
edgeList = [1, 2;
1, 3;
2, 3];图的类型
平凡图 (Trivial Graph)：
- 只有一个顶点且没有边的图。
空图 (Empty Graph)：
- 没有边的图。
完全图 (Complete Graph)：
- 任意两个顶点之间都有一条边的图。一个有 ( n ) 个顶点的完全图记为 ( K_n )。
二分图 (Bipartite Graph)：
- 顶点集 ( V ) 可以分为两个不相交的子集 ( U ) 和 ( W )，使得每条边都连接 ( U ) 和 ( W ) 中的一个顶点。
树 (Tree)：
- 无环的连通图。
森林 (Forest)：
- 无环的无向图（即多棵树的集合）。
图论中的重要算法
深度优先搜索 (DFS)：
- 遍历或搜索图的一种算法，尽可能深地搜索图的分支。
广度优先搜索 (BFS)：
- 遍历或搜索图的一种算法，按层次搜索图。
最短路径算法：
- Dijkstra算法：用于边权重非负的图。
- Bellman-Ford算法：用于边权重可以为负的图。
- Floyd-Warshall算法：计算所有顶点对之间的最短路径。
最小生成树算法：
- Kruskal算法：按边权重从小到大添加边。
- Prim算法：按顶点扩展最小生成树。
拓扑排序 (Topological Sorting)：
- 对有向无环图 (DAG) 的顶点进行排序，使得对于每条边 ( (u, v) )，顶点 ( u ) 在 ( v ) 之前。
连通分量算法：
- 查找图中的连通子图。
MATLAB中图论的应用
MATLAB提供了丰富的函数库用于图论的研究和应用。以下是一些常用函数和示例：
创建图：
% 创建无向图
G = graph([1, 1, 2, 3], [2, 3, 3, 4]);
% 创建有向图
DG = digraph([1, 2, 3], [2, 3, 1]);绘制图：
% 绘制无向图
plot(G);
% 绘制有向图
plot(DG);图的属性和操作：
% 获取图的邻接矩阵
A = adjacency(G);
% 计算最短路径
dist = distances(G, 1, 4);
% 查找所有简单路径
allPaths = allpaths(G, 1, 4);
% 查找最小生成树
mst = minspantree(G);
% 计算连通分量
components = conncomp(G);例子
示例代码：
创建一个无向图，并使用Dijkstra算法计算最短路径：
% 定义邻接矩阵
adjMatrix = [0, 10, 6, 0, 0;
10, 0, 5, 15, 0;
6, 5, 0, 4, 7;
0, 15, 4, 0, 8;
0, 0, 7, 8, 0];
% 计算源点1到其他顶点的最短路径
[source] = 1;
[dist, path] = dijkstra(adjMatrix, source);
% 输出结果
disp('最短距离:');
disp(dist);
disp('路径:');
disp(path);创建一个无向图，并使用Kruskal算法计算最小生成树：
% 定义邻接矩阵
adjMatrix = [0, 10, 6, 0, 0;
10, 0, 5, 15, 0;
6, 5, 0, 4, 7;
0, 15, 4, 0, 8;
0, 0, 7, 8, 0];
% 计算最小生成树
[mstEdges, totalWeight] = kruskalMST(adjMatrix);
% 输出结果
disp('最小生成树的边:');
disp(mstEdges);
disp('最小生成树的总权重:');
disp(totalWeight);通过这些基本概念、算法和应用，图论为解决实际问题提供了强大的工具和方法。
最大流问题
最大流问题（Maximum Flow Problem）是图论中的一个经典问题，旨在找到从源点到汇点的最大可能流量。这个问题在网络流、交通、供应链等领域有广泛应用。
最大流问题的基本概念
流网络 (Flow Network)：
- 一个有向图，其中每条边都有一个非负容量（capacity），表示该边可以传输的最大流量。
源点 (Source)：
- 图中一个特殊的顶点，记为 ( s )，是流的起点。
汇点 (Sink)：
- 图中一个特殊的顶点，记为 ( t )，是流的终点。
流量 (Flow)：
- 分配给每条边的数值，表示通过该边的实际流量，必须满足容量限制和流量守恒条件。
容量限制 (Capacity Constraint)：
- 对于每条边 ( (u, v) )，流量 ( f(u, v) ) 必须满足 ( 0 \leq f(u, v) \leq c(u, v) )，其中 ( c(u, v) ) 是边的容量。
流量守恒 (Flow Conservation)：
- 除源点和汇点外，每个顶点的流入等于流出。
最大流的算法
Ford-Fulkerson算法：
- 通过增广路径（augmenting path）不断增加流量，直到没有更多增广路径为止。
- 增广路径可以通过深度优先搜索（DFS）或广度优先搜索（BFS）找到。
Edmonds-Karp算法：
- Ford-Fulkerson算法的实现之一，使用广度优先搜索（BFS）寻找增广路径。
- 时间复杂度为 ( O(VE^2) )。
Ford-Fulkerson算法
算法步骤：
- 初始化所有边的流量为0。
- 使用BFS或DFS寻找从源点 ( s ) 到汇点 ( t ) 的增广路径。
- 找到增广路径后，计算该路径的最小剩余容量（瓶颈容量）。
- 沿增广路径增加流量，并更新残余网络。
- 重复步骤2-4，直到没有增广路径。
MATLAB实现：
function max_flow = fordFulkerson(adjMatrix, source, sink)
% adjMatrix: 邻接矩阵，表示边的容量
% source: 源点
% sink: 汇点
% max_flow: 最大流
% 初始化残余图
residualGraph = adjMatrix;
numNodes = size(adjMatrix, 1);
max_flow = 0;
% BFS寻找增广路径
function [found, parent] = bfs(residualGraph, source, sink)
visited = false(1, numNodes);
parent = -1 * ones(1, numNodes);
queue = [source];
visited(source) = true;
while ~isempty(queue)
u = queue(1);
queue(1) = [];
for v = 1:numNodes
if ~visited(v) && residualGraph(u, v) > 0
queue(end + 1) = v; %#ok<AGROW>
parent(v) = u;
visited(v) = true;
if v == sink
found = true;
return;
end
end
end
end
found = false;
end
% Ford-Fulkerson算法
while true
[found, parent] = bfs(residualGraph, source, sink);
if ~found
break;
end
% 找到增广路径的瓶颈容量
path_flow = inf;
v = sink;
while v ~= source
u = parent(v);
path_flow = min(path_flow, residualGraph(u, v));
v = u;
end
% 增加流量并更新残余图
v = sink;
while v ~= source
u = parent(v);
residualGraph(u, v) = residualGraph(u, v) - path_flow;
residualGraph(v, u) = residualGraph(v, u) + path_flow;
v = u;
end
max_flow = max_flow + path_flow;
end
end使用示例：
% 定义邻接矩阵
adjMatrix = [0, 16, 13, 0, 0, 0;
0, 0, 10, 12, 0, 0;
0, 4, 0, 0, 14, 0;
0, 0, 9, 0, 0, 20;
0, 0, 0, 7, 0, 4;
0, 0, 0, 0, 0, 0];
% 源点和汇点
source = 1;
sink = 6;
% 计算最大流
max_flow = fordFulkerson(adjMatrix, source, sink);
% 输出结果
disp('最大流:');
disp(max_flow);Edmonds-Karp算法
Edmonds-Karp算法是Ford-Fulkerson算法的一个实现，使用广度优先搜索（BFS）来寻找增广路径。以下是MATLAB实现：
function max_flow = edmondsKarp(adjMatrix, source, sink)
% adjMatrix: 邻接矩阵，表示边的容量
% source: 源点
% sink: 汇点
% max_flow: 最大流
% 初始化残余图
residualGraph = adjMatrix;
numNodes = size(adjMatrix, 1);
max_flow = 0;
% BFS寻找增广路径
function [found, parent] = bfs(residualGraph, source, sink)
visited = false(1, numNodes);
parent = -1 * ones(1, numNodes);
queue = [source];
visited(source) = true;
while ~isempty(queue)
u = queue(1);
queue(1) = [];
for v = 1:numNodes
if ~visited(v) && residualGraph(u, v) > 0
queue(end + 1) = v; %#ok<AGROW>
parent(v) = u;
visited(v) = true;
if v == sink
found = true;
return;
end
end
end
end
found = false;
end
% Edmonds-Karp算法
while true
[found, parent] = bfs(residualGraph, source, sink);
if ~found
break;
end
% 找到增广路径的瓶颈容量
path_flow = inf;
v = sink;
while v ~= source
u = parent(v);
path_flow = min(path_flow, residualGraph(u, v));
v = u;
end
% 增加流量并更新残余图
v = sink;
while v ~= source
u = parent(v);
residualGraph(u, v) = residualGraph(u, v) - path_flow;
residualGraph(v, u) = residualGraph(v, u) + path_flow;
v = u;
end
max_flow = max_flow + path_flow;
end
end使用示例：
% 定义邻接矩阵
adjMatrix = [0, 16, 13, 0, 0, 0;
0, 0, 10, 12, 0, 0;
0, 4, 0, 0, 14, 0;
0, 0, 9, 0, 0, 20;
0, 0, 0, 7, 0, 4;
0, 0, 0, 0, 0, 0];
% 源点和汇点
source = 1;
sink = 6;
% 计算最大流
max_flow = edmondsKarp(adjMatrix, source, sink);
% 输出结果
disp('最大流:');
disp(max_flow);最小费用问题
最小费用问题（Minimum Cost Problem）通常出现在网络流理论和图论中，是指在一个加权有向图中找到一条从源点到汇点的最小费用路径。这里的费用通常是指路径上的边权重的总和。
1. 最小费用最大流问题
最小费用最大流问题是指在一个网络中找到一种流动方式，使得从源点到汇点的总流量最大且总费用最小。该问题常用于优化运输成本、网络流量管理等场景。
2. 主要算法
解决最小费用问题的主要算法包括：
Bellman-Ford 算法
Bellman-Ford 算法可以处理带有负权边的图，是一个较为经典的算法。其主要步骤如下：
- 初始化源点的距离为0，其余点的距离为正无穷。
- 对所有边进行 V-1 轮松弛操作，每轮尝试更新边的距离。
- 检查是否存在负权回路。
Dijkstra 算法
Dijkstra 算法用于非负权图的单源最短路径问题。主要步骤如下：
- 初始化源点的距离为0，其余点的距离为正无穷。
- 使用优先队列（如最小堆）选取当前距离最小的顶点进行扩展。
- 更新相邻顶点的距离，重复直到所有顶点都被访问。
SPFA（Shortest Path Faster Algorithm）
SPFA 算法是 Bellman-Ford 算法的改进版本，使用队列来优化松弛操作，平均情况下性能更好。
- 初始化源点的距离为0，并将源点入队。
- 从队列中取出顶点，松弛其所有相邻边，如果相邻顶点的距离被更新，则将该顶点入队。
- 重复上述过程直到队列为空。
3. 复杂度
- Bellman-Ford 算法的时间复杂度为 (O(VE))。
- Dijkstra 算法使用最小堆实现时的时间复杂度为 (O(E + V \log V))。
- SPFA 算法的时间复杂度在最坏情况下与 Bellman-Ford 相同，但通常在实际应用中更快。
4. 应用场景
- 物流和运输：优化货物从供应商到消费者的运输路径，降低运输成本。
- 网络路由：找到数据包在网络中传输的最优路径，减少延迟和费用。
- 生产调度：在制造过程中优化资源的分配和使用，降低生产成本。
如果你需要具体的代码示例或进一步的详细信息，可以告诉我你的需求，我会为你提供更多帮助。
背包问题
背包问题是计算机科学和优化领域中的经典问题，广泛应用于资源分配、调度等问题。背包问题可以分为以下几种：
- 0-1背包问题：
- 问题描述：给定n种物品和一个容量为V的背包，物品i的重量是w[i]，其价值为v[i]。问应如何选择装入背包的物品，使得背包内物品的总价值最大，同时不超过背包的容量限制。
- 特点：每种物品仅有一件，可以选择放入或不放入背包。
- 完全背包问题：
- 问题描述：与0-1背包问题类似，但每种物品有无限件可用。
- 特点：因为物品数量无限，所以对于每种物品，可以重复选择多次。
- 多重背包问题：
- 问题描述：给定n种物品和一个容量为V的背包，物品i的重量是w[i]，其价值为v[i]，数量为n[i]。问应如何选择装入背包的物品，使得背包内物品的总价值最大，同时不超过背包的容量限制。
- 特点：每种物品的件数是有限的。
- 分组背包问题：
- 问题描述：有N组物品和一个容量为V的背包，每组物品有若干个，同一组内的物品最多只能选一个，求解最大价值。
- 特点：物品被划分为若干组，从每一组中选取物品。
- 其它变种：
- 还有许多背包问题的变种，如背包问题中加入物品之间的依赖关系等。 解决方法：
- 动态规划：是解决背包问题的一种常见方法。以0-1背包问题为例，可以通过构建一个二维数组dp[i][j]，表示在前i件物品中选择，使得总重量不超过j的情况下，背包能够达到的最大价值。
- 回溯法：也可以解决背包问题，但其时间复杂度较高，通常不用于解决大规模问题。
- 分支限界法：适用于解的组合数量很大的情况，通过剪枝来减少搜索空间。 以下是一个0-1背包问题的简单动态规划算法伪代码：
// N为物品数量，V为背包容量，w[]为物品重量数组，v[]为物品价值数组
for i = 1 to N
for j = 1 to V
if j >= w[i]
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
else
dp[i][j] = dp[i-1][j]最终dp[N][V]的值即为背包能够达到的最大价值。根据需要，还可以通过dp数组来恢复出解的具体方案。
指派问题
指派问题（Assignment Problem）是运筹学中的一个经典问题，它涉及到如何以最低成本或最高效率将一组资源（如人员、机器、任务等）分配给一组任务。指派问题通常可以描述为：有n个工人和n个任务，每个工人完成每个任务都有一个特定的成本，目标是找到一个指派方案，使得总成本最小。 以下是解决指派问题的一种常用方法——匈牙利算法（Hungarian Algorithm）的步骤：
- 构建成本矩阵：
- 假设有n个工人和n个任务，构建一个n×n的成本矩阵，矩阵的元素c[i][j]表示工人i完成任务j的成本。
- 行减法：
- 对成本矩阵的每一行元素减去该行的最小值。这样做的目的是使每行至少有一个零元素。
- 列减法：
- 对成本矩阵的每一列元素减去该列的最小值。这样做的目的是使每列至少有一个零元素。
- 覆盖零元素：
- 用最少的直线（水平线和垂直线）覆盖矩阵中的所有零元素。如果覆盖零元素的直线数量等于矩阵的阶数n，则算法结束，否则进入下一步。
- 调整成本矩阵：
- 找出未被直线覆盖的最小元素，记为m。对于每一行，如果该行有被直线覆盖的零元素，则将该行的每个元素减去m；对于每一列，如果该列有被直线覆盖的零元素，则将该列的每个元素加上m。未被直线覆盖的元素保持不变。
- 重复步骤4和步骤5：
- 重复步骤4和步骤5，直到找到一个最优解，即覆盖零元素的直线数量等于矩阵的阶数n。
- 构建最优解：
- 根据最终的成本矩阵，选择一个零元素作为指派，确保每个工人和每个任务只被指派一次。最终的指派方案即为最优解。 下面是使用Python实现的匈牙利算法来解决指派问题：
import numpy as np
def hungarian_algorithm(cost_matrix):
n = len(cost_matrix)
# 初始化标记数组
row_covered = [False] * n
col_covered = [False] * n
# 初始化潜在收益数组
u = [0] * n
v = [0] * n
# Step 1: 对于每行，减去该行的最小值
for i in range(n):
cost_matrix[i] -= np.min(cost_matrix[i])
# Step 2: 对于每列，减去该列的最小值
for j in range(n):
cost_matrix[:, j] -= np.min(cost_matrix[:, j])
# Step 3: 覆盖所有零元素
while True:
# 初始化标记
marked_rows = [False] * n
marked_cols = [False] * n
marked_zeros = [(0, 0)] # 存储标记的零元素位置
for i in range(n):
for j in range(n):
if cost_matrix[i][j] == 0 and not row_covered[i] and not col_covered[j]:
marked_rows[i] = True
marked_cols[j] = True
marked_zeros.append((i, j))
# 检查是否完成
if len(marked_zeros) >= n:
break
# Step 4: 调整潜在收益
while True:
starred_zeros = [(i, j) for i, j in marked_zeros if not row_covered[i] and not col_covered[j]]
if len(starred_zeros) > 0:
i, j = starred_zeros[0]
row_covered[i] = True
col_covered[j] = True
else:
break
# 更新潜在收益
for k, l in marked_zeros:
if not row_covered[k] and not col_covered[l]:
cost_matrix[k][l] += min(u[k] + v[l] - cost_matrix[k][l], 0)
# 更新潜在收益
for i in range(n):
if not row_covered[i]:
u[i] += min(cost_matrix[i][j] for j in range(n) if not col_covered[j])
for j in range(n):
if not col_covered[j]:
v[j] -= min(cost_matrix[i][j] for i in range(n) if not row_covered[i])
# 构建最优解
assignment = [-1] * n
for i in range(n):
for j in range(n):
if cost_matrix[i][j] == 0 and not row_covered[i] and not col_covered[j]:
assignment[i] = j
row_covered[i] = True
col_covered[j] = True
break
return assignment
# 示例成本矩阵
cost_matrix = np.array([
[40, 60, 15],
[25, 30, 45],
[55, 30, 25]
])
# 解决指派问题
assignment = hungarian_algorithm(cost_matrix)
print("分配结果：")
for i, worker in enumerate(assignment):
print(f"工人 {i+1} 被分配给任务 {worker+1}")这段代码首先通过行和列减法将成本矩阵转换为至少包含一个零元素的形式。然后，它通过覆盖零元素和调整潜在收益来寻找最优解。最后，它构建了一个分配结果，其中每个工人都被分配了一个任务。
旅行商问题
旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题。问题描述如下： 给定一组城市和每两个城市之间的距离，求解一条最短的可能路径，使得从某一城市出发，访问每个城市恰好一次并返回出发城市。 旅行商问题是一个典型的NP-hard问题，这意味着随着城市数量的增加，问题的求解时间呈指数增长。以下是解决旅行商问题的几种方法：
- 暴力法（Brute Force）：
- 枚举所有可能的路径，并计算每条路径的长度，选择其中最短的一条。
- 时间复杂度为O((n-1)!)，只适用于城市数量非常小的情况。
- 动态规划（Dynamic Programming）：
- 使用动态规划解决TSP的方法是 Held-Karp 算法。
- 时间复杂度为O(n^2 * 2^n)，比暴力法更高效，但仍然只适用于较小的n。
- 分支限界法（Branch and Bound）：
- 通过系统地枚举候选解的集合，并剪枝掉不可能得到最优解的分支。
- 时间复杂度比暴力法低，但仍然很高。
- 遗传算法（Genetic Algorithm）：
- 使用遗传算法的启发式搜索来寻找近似最优解。
- 适用于大规模问题，但不保证找到最优解。
- 蚁群算法（Ant Colony Optimization）：
- 启发式搜索算法，模拟蚂蚁觅食行为来寻找路径。
- 适用于大规模问题，通常能找到较好的解。
- 模拟退火（Simulated Annealing）：
- 基于物理退火过程的启发式算法。
- 在一定时间内通常能找到较好的解，但不保证最优。 下面是一个简单的旅行商问题暴力法的Python实现：
import itertools
def calculate_distance(path, distances):
total_distance = 0
for i in range(len(path) - 1):
total_distance += distances[path[i]][path[i + 1]]
total_distance += distances[path[-1]][path[0]] # 返回到起点
return total_distance
def traveling_salesman_brute_force(distances):
n = len(distances)
cities = list(range(n))
shortest_path = None
shortest_distance = float('inf')
for path in itertools.permutations(cities):
path_distance = calculate_distance(path, distances)
if path_distance < shortest_distance:
shortest_distance = path_distance
shortest_path = path
return shortest_path, shortest_distance
# 示例距离矩阵
distances = [
[0, 20, 42, 25],
[20, 0, 30, 34],
[42, 30, 0, 10],
[25, 34, 10, 0]
]
shortest_path, shortest_distance = traveling_salesman_brute_force(distances)
print("最短路径:", shortest_path)
print("最短距离:", shortest_distance)