最短路问题、最小生成树问题
原创大约 9 分钟
图论
图论是数学的一个分支，研究图的性质和应用。图由顶点（节点）和连接这些顶点的边（链接）组成。图论在计算机科学、网络分析、交通规划等领域有广泛应用。
图的基本概念
- 图 (Graph): 由顶点集合和边集合组成的二元组。
- 无向图 (Undirected Graph): 边没有方向。
- 有向图 (Directed Graph): 边有方向，表示为有序对。
- 顶点 (Vertex): 图中的点。
- 边 (Edge): 连接顶点的线。
- 度 (Degree): 与顶点相连的边的数量。在有向图中，有入度（指向该顶点的边数）和出度（从该顶点出发的边数）。
- 路径 (Path): 顶点和边的序列，其中每条边都连接前一个顶点和后一个顶点。
- 连通图 (Connected Graph): 任意两个顶点间都有路径。
- 环 (Cycle): 起点和终点相同的路径。
图的表示方法
邻接矩阵 (Adjacency Matrix):
- 二维数组，其中
A[i][j]表示顶点i到顶点j是否有边（无向图中对称，有向图中不对称）。
% 邻接矩阵示例 adjMatrix = [0, 1, 0; 1, 0, 1; 0, 1, 0];- 二维数组，其中
邻接表 (Adjacency List):
- 每个顶点有一个列表，包含所有与其相连的顶点。
% 邻接表示例（使用cell数组） adjList = {[2], [1, 3], [2]};
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);示例代码：
% 创建一个无向图
G = graph([1, 1, 2, 3], [2, 3, 3, 4]);
% 绘制图
figure;
plot(G);
title('无向图');
% 计算顶点1到顶点4的最短路径
dist = distances(G, 1, 4);
disp(['顶点1到顶点4的最短路径长度: ', num2str(dist)]);
% 查找所有从顶点1到顶点4的简单路径
allPaths = allpaths(G, 1, 4);
disp('所有简单路径:');
disp(allPaths);图论在许多实际应用中非常重要，例如网络路由优化、社交网络分析和生物网络研究。
最短路径
最短路径问题是图论中的一个经典问题，其目标是找到图中两个顶点之间的最短路径。该问题在许多实际应用中非常重要，例如地图导航、网络路由和物流优化。
最短路径算法
Dijkstra算法：
- 适用于边权重非负的图。
- 使用贪心策略，每次选择当前最短路径的顶点进行扩展。
Bellman-Ford算法：
- 适用于边权重可以为负的图。
- 可以检测负权环。
Floyd-Warshall算法：
- 适用于计算所有顶点对之间的最短路径。
- 使用动态规划思想，时间复杂度为 (O(n^3))。
Dijkstra算法
算法步骤：
- 初始化源点到自身的距离为0，其他点到源点的距离为无穷大。
- 使用一个优先队列（或最小堆）来存储顶点及其当前的最短距离。
- 每次从队列中取出当前距离最小的顶点，并更新其邻接顶点的距离。
- 重复步骤3，直到队列为空。
MATLAB实现：
function [dist, path] = dijkstra(adjMatrix, source)
% adjMatrix: 邻接矩阵
% source: 源点
% dist: 源点到其他所有点的最短距离
% path: 最短路径
numNodes = size(adjMatrix, 1);
dist = inf(1, numNodes);
dist(source) = 0;
visited = false(1, numNodes);
path = -1 * ones(1, numNodes);
while any(~visited)
% 找到当前未访问顶点中距离最小的顶点
[~, u] = min(dist + visited * inf);
visited(u) = true;
% 更新邻接顶点的距离
for v = 1:numNodes
if adjMatrix(u, v) > 0 && ~visited(v)
newDist = dist(u) + adjMatrix(u, v);
if newDist < dist(v)
dist(v) = newDist;
path(v) = u;
end
end
end
end
end使用示例：
% 定义邻接矩阵
adjMatrix = [0, 10, 0, 30, 100;
10, 0, 50, 0, 0;
0, 50, 0, 20, 10;
30, 0, 20, 0, 60;
100, 0, 10, 60, 0];
% 计算源点1到其他顶点的最短路径
[source] = 1;
[dist, path] = dijkstra(adjMatrix, source);
% 输出结果
disp('最短距离:');
disp(dist);
disp('路径:');
disp(path);Bellman-Ford算法
算法步骤：
- 初始化源点到自身的距离为0，其他点到源点的距离为无穷大。
- 对于每一条边，尝试更新其终点的距离。
- 重复步骤2，最多进行|V|-1次（|V|为顶点数）。
- 检查是否存在负权环。
MATLAB实现：
function [dist, path] = bellmanFord(adjMatrix, source)
% adjMatrix: 邻接矩阵
% source: 源点
% dist: 源点到其他所有点的最短距离
% path: 最短路径
numNodes = size(adjMatrix, 1);
dist = inf(1, numNodes);
dist(source) = 0;
path = -1 * ones(1, numNodes);
for i = 1:numNodes-1
for u = 1:numNodes
for v = 1:numNodes
if adjMatrix(u, v) ~= 0
newDist = dist(u) + adjMatrix(u, v);
if newDist < dist(v)
dist(v) = newDist;
path(v) = u;
end
end
end
end
end
% 检测负权环
for u = 1:numNodes
for v = 1:numNodes
if adjMatrix(u, v) ~= 0 && dist(u) + adjMatrix(u, v) < dist(v)
error('图中包含负权环');
end
end
end
end使用示例：
% 定义邻接矩阵（可以包含负权边）
adjMatrix = [0, -1, 4, 0, 0;
0, 0, 3, 2, 2;
0, 0, 0, 0, 0;
0, 1, 5, 0, 0;
0, 0, 0, -3, 0];
% 计算源点1到其他顶点的最短路径
[source] = 1;
[dist, path] = bellmanFord(adjMatrix, source);
% 输出结果
disp('最短距离:');
disp(dist);
disp('路径:');
disp(path);Floyd-Warshall算法
算法步骤：
- 初始化一个距离矩阵，将直接相连的顶点的距离设为边的权重，其他设为无穷大，自己到自己设为0。
- 依次选择每一个顶点作为中间顶点，更新其他所有顶点之间的最短路径。
MATLAB实现：
function dist = floydWarshall(adjMatrix)
% adjMatrix: 邻接矩阵
% dist: 所有顶点对之间的最短距离
numNodes = size(adjMatrix, 1);
dist = adjMatrix;
dist(dist == 0 & ~eye(numNodes)) = inf;
for k = 1:numNodes
for i = 1:numNodes
for j = 1:numNodes
if dist(i, j) > dist(i, k) + dist(k, j)
dist(i, j) = dist(i, k) + dist(k, j);
end
end
end
end
end使用示例：
% 定义邻接矩阵
adjMatrix = [0, 3, inf, 5;
2, 0, inf, 4;
inf, 1, 0, inf;
inf, inf, 2, 0];
% 计算所有顶点对之间的最短路径
dist = floydWarshall(adjMatrix);
% 输出结果
disp('最短距离矩阵:');
disp(dist);以上是最短路径问题的三种主要算法及其MATLAB实现。这些算法可以根据图的性质（如是否有负权边）来选择使用。
最小生成树
最小生成树（Minimum Spanning Tree，MST）是图论中的一个经典问题，其目标是在图中找到一棵包含所有顶点且边权重和最小的树。最小生成树在网络设计、路径优化和聚类分析等领域有广泛应用。
最小生成树的基本概念
- 无向图 (Undirected Graph)：最小生成树通常应用于无向图中。
- 生成树 (Spanning Tree)：一个包含图中所有顶点的子图，是一棵无环连通图。
- 最小生成树 (Minimum Spanning Tree, MST)：在所有可能的生成树中，边权重之和最小的生成树。
最小生成树的算法
Kruskal算法：
- 使用贪心策略，从权重最小的边开始逐渐构建生成树。
- 适用于稀疏图，边的数量少。
Prim算法：
- 使用贪心策略，从某个顶点开始，逐渐将与生成树相连的权重最小的边加入生成树。
- 适用于稠密图，顶点的数量多。
Kruskal算法
算法步骤：
- 将所有边按权重从小到大排序。
- 初始化一个空集合，用于存储生成树的边。
- 依次选择权重最小的边，如果这条边与生成树中的边不形成环，则将其加入生成树。
- 重复步骤3，直到生成树包含 ( V-1 ) 条边（( V ) 为顶点数）。
MATLAB实现：
function [mstEdges, totalWeight] = kruskalMST(adjMatrix)
% adjMatrix: 邻接矩阵
% mstEdges: 最小生成树的边
% totalWeight: 最小生成树的总权重
numNodes = size(adjMatrix, 1);
edges = [];
for i = 1:numNodes
for j = i+1:numNodes
if adjMatrix(i, j) > 0
edges = [edges; i, j, adjMatrix(i, j)];
end
end
end
% 按边的权重排序
edges = sortrows(edges, 3);
% 初始化并查集
parent = 1:numNodes;
rank = zeros(1, numNodes);
function root = find(x)
if parent(x) ~= x
parent(x) = find(parent(x));
end
root = parent(x);
end
function union(x, y)
rootX = find(x);
rootY = find(y);
if rootX ~= rootY
if rank(rootX) > rank(rootY)
parent(rootY) = rootX;
else
parent(rootX) = rootY;
if rank(rootX) == rank(rootY)
rank(rootY) = rank(rootY) + 1;
end
end
end
end
% Kruskal算法
mstEdges = [];
totalWeight = 0;
for k = 1:size(edges, 1)
u = edges(k, 1);
v = edges(k, 2);
weight = edges(k, 3);
if find(u) ~= find(v)
union(u, v);
mstEdges = [mstEdges; u, v, weight];
totalWeight = totalWeight + weight;
end
end
end使用示例：
% 定义邻接矩阵
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);Prim算法
算法步骤：
- 从任意一个顶点开始，将其加入生成树。
- 重复以下步骤直到所有顶点都加入生成树：
- 找到所有与生成树中的顶点相连的边中权重最小的边。
- 将该边及其相连的顶点加入生成树。
MATLAB实现：
function [mstEdges, totalWeight] = primMST(adjMatrix)
% adjMatrix: 邻接矩阵
% mstEdges: 最小生成树的边
% totalWeight: 最小生成树的总权重
numNodes = size(adjMatrix, 1);
inMST = false(1, numNodes);
dist = inf(1, numNodes);
parent = -1 * ones(1, numNodes);
dist(1) = 0; % 从第一个顶点开始
for i = 1:numNodes
% 找到不在MST中的最小距离顶点
[~, u] = min(dist + inMST * inf);
inMST(u) = true;
% 更新邻接顶点的距离
for v = 1:numNodes
if adjMatrix(u, v) > 0 && ~inMST(v) && adjMatrix(u, v) < dist(v)
dist(v) = adjMatrix(u, v);
parent(v) = u;
end
end
end
% 生成最小生成树的边和总权重
mstEdges = [];
totalWeight = 0;
for v = 2:numNodes
u = parent(v);
mstEdges = [mstEdges; u, v, adjMatrix(u, v)];
totalWeight = totalWeight + adjMatrix(u, v);
end
end使用示例：
% 定义邻接矩阵
adjMatrix = [0, 2, 0, 6, 0;
2, 0, 3, 8, 5;
0, 3, 0, 0, 7;
6, 8, 0, 0, 9;
0, 5, 7, 9, 0];
% 计算最小生成树
[mstEdges, totalWeight] = primMST(adjMatrix);
% 输出结果
disp('最小生成树的边:');
disp(mstEdges);
disp('最小生成树的总权重:');
disp(totalWeight);通过以上两个算法的实现和示例，可以计算无向图的最小生成树，并理解其在图论中的重要性和应用。