企业官网建设流程全解析

数学建模里有一个很有意思的现象：很多看起来八竿子打不着的问题，最后都会落到同一个抽象框架上——图。物流配送要选最省时间的路线，本质是最短路；通信基站要选成本最低的布线方案，本质是最小生成树；抢险物资从仓库运到受灾点、路网还有容量上限，本质是网络流；一个团队里怎么给人派活才能完成尽可能多的任务，本质是二分图匹配。这类题目在竞赛里反复出现，考的核心往往不是某个天才创意，而是你能不能把一个实际问题“翻译”成图，然后选对算法、写对代码。

这一章我们专门讲图与网络模型及方法。在Matlab里，图的表示方式和求解函数都很成熟，但我建议算法原理也要吃透。无论是全国大学生数学建模竞赛还是美赛，近几年的题目里图论模型几乎成了必考板块，很多时候不是让你直接调用shortestpath返回一个数字就完事，而是要求说明建模过程、分析结果、做敏感性讨论。只懂函数不懂原理，遇到需要改造模型的情况会非常难受。

我接下来会从最核心的四个方向展开：最短路、最小生成树、网络流、二分图匹配，每一部分都给原理、给Matlab代码、给比赛中的使用经验。最后用一个完整的物资调运案例把这些算法串起来，看看一套图论模型是怎么从题目文字一步步走到结果分析的。

1. 从实际问题到邻接矩阵：图论建模的第一步

1.1 点、边、权：把现实问题“翻译”成图

建模的第一步从来不是写代码，而是定义图的三要素。图在数学上很简单：一组顶点（节点）和连接这些顶点的边。但现实中不会有任何一道题直接告诉你“节点是什么”，这需要你自己判断。

我总结过一套比较通用的翻译规则：

• 点：有独立属性、需要被区分的实体。城市、仓库、设备、人员、工序、状态都可以是点。
• 边：实体之间的直接关系。道路、线路、依赖、匹配关系、转移可能性都是边。
• 权：这条边在问题里的量化属性。距离、时间、成本、容量、概率都可以作为权。

举个最经典的例子，快递配送问题里，点是配送中心和客户地址，边是道路连接，权是路上花费的时间或距离；换到通信布线问题，点是机房和终端设备，边是可铺设光缆的路段，权是每段光缆的造价。同样是点和边，因为实际含义不同，后续调用的算法和解读结果的方式就完全不同。

我做个表方便你理解：

这个翻译过程是整章的核心。我见过很多同学一上来就对着邻接矩阵发懵，其实就是因为没把“点是什么、边是什么、权是什么”想清楚。想清楚了，矩阵只是顺手的事。

1.2 邻接矩阵与Matlab的图对象

邻接矩阵是图论算法里最常用、也最直观的数据结构。假设图有n个节点，就构造一个n乘n的矩阵W，W(i,j)表示从节点i到节点j的边的权值。如果两个节点之间没有边，就填inf（无穷大）；W(i,i)一般填0，表示自己到自己没有距离。

无向图的邻接矩阵一定是对称的，因为i到j和j到i是同一条路；有向图则不一定对称，可能需要分别填不同的值。这一点在建模的时候容易忽略，尤其是涉及管线、管网这类方向敏感的问题时，一定先确认题目说的是“双向可达”还是“单向输送”。

在Matlab里有两种层面：一是直接手写邻接矩阵，配合自己实现的算法；二是用graph和digraph对象，直接调用内置求解函数。

% 邻接矩阵表示：4个节点，1-2权值3，1-3权值8，2-4权值2，3-4权值5 W = [0 3 8 inf; 3 0 inf 2; 8 inf 0 5; inf 2 5 0]; % 换成graph对象 g = graph(W); % 可视化 plot(g, 'EdgeLabel', g.Edges.Weight);

用邻接矩阵的好处是，它和算法代码直接对应，手写Dijkstra、Floyd时每一步操作都看得清清楚楚；用graph对象的好处是，一行就能调用shortestpath、minspantree、maxflow这些成熟函数。我一般建议先会用邻接矩阵手推算法，再用graph对象做快速验证。比赛时间紧张的时候，直接用内置函数能省下大量调试时间，但论文里写算法原理时，还是要基于邻接矩阵的那套流程来讲。

2. 最短路问题：Dijkstra与Floyd的完整实现

2.1 先想清楚一个问题：最短路在建模里到底解决什么

最短路问题是图论里最基础的问题，但很多同学会用错场景。最短路解决的永远是“带权图上的最优走法”，而不是“能不能走通”。只要题目里出现“选择一条最优路线”“总成本最低的路径”“最短传输时间”这类表述，就应该往最短路模型上想。

我常用的判断办法是：如果一条路径由多段组成，每段有一个可相加的代价，最终目标是找代价最小的一条，那这就是最短路问题。注意“可相加”三个字，有些题目的目标函数是“最大运量”“最小瓶颈”而不是“总代价最小”，那就不是最短路，可能是最小生成树或网络流。

最短路在竞赛题里的另一个角色是作为子流程。比如要规划一辆车服务多个客户的路径，任意两个客户之间应该走哪条路？先求出全图最短路径，把客户之间的最短距离作为新的“顶点间距离”，再去考虑排序问题。这时候Floyd这类全源最短路算法就派上用场了。

2.2 Dijkstra算法的贪心逻辑与代码

Dijkstra处理的是单源最短路问题，也就是从某个固定起点到其他所有点的最短路径。它的核心逻辑是贪心：维护一个数组dist记录当前已知起点到各节点的最短距离，每次从“尚未确定最短距离”的节点里挑一个距离最小的，把它标记为已确定，然后用这个节点去尝试更新它邻居的距离。这个过程叫“松弛”。

为什么要每次挑距离最小的节点？因为边的权都是非负的，已经找到最短路径的节点不可能再被其他更远的节点优化。这是个很朴素的逻辑：你现在手里有一条到A点距离10的路径，其他任何没确定的节点至少离起点12，那通过它们去绕到A，距离只会大于等于12，不可能比10小。

function [dist, path] = myDijkstra(W, s, t) % W: 邻接矩阵，不连通为inf % s: 起点编号，t: 终点编号 n = size(W, 1); dist = inf(1, n); visited = false(1, n); prev = zeros(1, n); dist(s) = 0; for iter = 1:n % 找未访问节点里距离最小的 unvisitedNodes = find(~visited); if isempty(unvisitedNodes), break; end [dmin, idx] = min(dist(unvisitedNodes)); u = unvisitedNodes(idx); if dmin == inf, break; end visited(u) = true; if u == t, break; end % 松弛操作 for v = 1:n if ~visited(v) && isfinite(W(u, v)) if dist(u) + W(u, v) < dist(v) dist(v) = dist(u) + W(u, v); prev(v) = u; end end end end % 从终点回溯路径 path = t; while path(1) ~= s path = [prev(path(1)), path]; end end

注意我这里面有一行容易被忽略但很重要的代码：[dmin, idx] = min(dist(unvisitedNodes))。如果不先把未访问节点筛出来，直接min(dist)很可能会选中已经确定最短路的节点，这样算法就会乱掉。很多手写Dijkstra出bug的同学，最后都卡在这一步。

用一个小例子验证一下：4个节点，W和前面一样，起点1，终点4。手算过程是：初始dist(1)=0，选中1，更新dist(2)=3、dist(3)=8；未访问节点里dist最小的是2，选中2，更新dist(4)=3+2=5；此时dist(3)=8，未访问最小的是4（dist=5），选中4，结束。所以1到4的最短路是5，路径1→2→4。这段逻辑在代码里走一遍，输出完全一致。

2.3 Floyd算法：用动态规划的思路一劳永逸

Floyd算法解决的是全源最短路问题，也就是一次性求出任意两点之间的最短路径。它的思路非常优雅，本质上是一个三维动态规划：D(i,j)表示从i到j的当前最短距离，然后尝试让每个节点k作为“中间节点”，如果i→k→j比直接i→j更短，就更新。

function D = myFloyd(W) n = size(W, 1); D = W; % 直接用邻接矩阵作为初始距离矩阵 for k = 1:n for i = 1:n for j = 1:n if isfinite(D(i, k)) && isfinite(D(k, j)) if D(i, k) + D(k, j) < D(i, j) D(i, j) = D(i, k) + D(k, j); end end end end end end

这段代码只有十来行，但包含了一个很容易踩的坑：中间层循环的顺序。变量名里层是k，不是i也不是j。如果写成最外层i、中间层j、内层k，结果会完全错乱。原因在于“依次把每个节点作为中间节点”这个顺序本身不能被打乱，因为第k轮迭代要利用前k-1轮的更新结果。

Floyd和Dijkstra的选型可以从数据规模和图结构来判断：

这里的负权边容易把初学者绕晕。Dijkstra在负权边存在时会失效，因为“已确定最短路的节点不可能被更新”这个贪心假设被打破了——一个节点绕一圈负权边之后，可能比当前记录的距离还小。Floyd可以处理负权边，因为它的状态转移考虑到所有中间节点组合，只要没有负权回路就能给出正确答案。所以在比赛里，如果题目给出了奇怪的代价定义，先检查有没有负值，有负值就老实换Floyd。

3. 最小生成树：Kruskal与Prim的实际选择

3.1 Kruskal算法：把所有边排个序，再逐个“收编”

最小生成树要解决的问题是：如何用最少的边权总和，把所有节点连接成一个连通整体。最直观的场景是布线类问题——通信网络铺设光缆，要把所有节点连起来，每段光缆有造价，怎么选才能总造价最低。

Kruskal算法的思路特别适合手算和代码实现：把所有边按权从小到大排序，然后从权最小的边开始，一条一条尝试加入生成树，如果加入这条边后不会形成环，就保留它；如果会形成环，就跳过。整个过程本质是贪心。

“会不会形成环”这个判断，用并查集实现最方便。并查集维护每个节点所在的集合，如果一条边的两个端点已经在同一个集合里，说明加入这条边会产生环路，必须丢弃；否则这条边可以加入，同时把两个集合合并。

function [T, totalW] = myKruskal(W) n = size(W, 1); edgeList = []; for i = 1:n for j = i+1:n if isfinite(W(i, j)) edgeList = [edgeList; i, j, W(i, j)]; end end end % 按边权从小到大排序 [~, order] = sort(edgeList(:, 3)); edgeList = edgeList(order, :); parent = 1:n; T = zeros(0, 3); totalW = 0; for k = 1:size(edgeList, 1) u = edgeList(k, 1); v = edgeList(k, 2); w = edgeList(k, 3); % 查找u和v的根 ru = u; while parent(ru) ~= ru ru = parent(ru); end rv = v; while parent(rv) ~= rv rv = parent(rv); end if ru ~= rv parent(ru) = rv; T = [T; u, v, w]; totalW = totalW + w; end end end

这里有个工程细节：邻接矩阵遍历边时我只用了j = i+1:n，也就是只取矩阵上三角部分。如果拿来回遍历所有i,j，每条无向边会被记录两次，虽然不影响排序结果，但会让代码运行时间翻倍，而且可能因为重复边导致生成树出问题。这个习惯我在后面所有涉及无向图的代码里都保持了。

3.2 什么时候选Prim，什么时候选Kruskal

Prim算法的思路完全不同：从任意一个节点开始，维护一个“已经在树里”的集合，每次从集合外找一个离集合最近的节点加入，同时记录那条连接边。它是“加点法”，Kruskal是“加边法”。

Prim在稠密图上的表现更好，因为它的瓶颈在于每次找最近节点，复杂度O(n^2)，和边数关系不大；Kruskal的瓶颈在于对边排序，复杂度O(m log m)，更适合边数较少的稀疏图。竞赛里遇到几百上千个节点的图，直接用内置函数是最稳的，minspantree一行搞定，但要在论文里说清楚你用的是哪种策略、为什么选它。

另一个容易忽略的问题是：最小生成树不一定唯一。当多条边权值相同时，Kruskal选哪条、绕开哪条，会影响最终生成树的形态，但总权值是一样的。比赛做敏感性分析时，如果发现“有多棵最优树”，这不是bug，而是模型固有特性，论文里甚至可以作为讨论点展开。

4. 网络流模型：最大流算法与最小割思想

4.1 流网络的三个基本约束

网络流处理的是“有容量限制的网络上最多能输送多少流量”这一类问题。现实场景包括：油气管网的最大输送能力、交通路网的最大通行车辆数、通信网络的最大带宽。

要建立一个合法的流，必须满足三个基本约束：

1. 容量约束：每条边上的流量不能超过该边的容量，即0 ≤ f(u,v) ≤ c(u,v)。
2. 流量守恒：除了源点和汇点，其他中间节点流入的总流量等于流出的总流量。
3. 反对称性：f(u,v) = -f(v,u)，表示从u流向v的量等于从v流向u的负值。

第3条是很多初学同学不理解的地方。在代码里，它会体现为：当你沿正向边推送了流量，反向边会增加一个容量等于当前流量的“虚边”。为什么要这么干？因为算法允许“反悔”。前面做出的一次流量分配，后来发现不是最优的，就需要通过反向边把流量退回去，再重新分配。这就像你规划了一条运输路线，运到一半发现另一条路线更宽裕，你不可能把已经发出的车撤回来，但可以在账面上把流量调整过去。反向边就是那张“调整记账单”。

4.2 增广路算法：BFS版Edmonds-Karp

求最大流的经典思路是：不断找一条从源点s到汇点t的“增广路”，这条路满足每条边的剩余容量都大于0，然后在这条路上推送尽可能多的流量。重复这个过程，直到找不到增广路，当前总流量就是最大流。

为什么找不到增广路就一定是最大流？这就涉及最大流-最小割定理：一个网络的最大流等于最小的割容量。割就是“把节点分成包含s的一边和包含t的一边，割开两边的边集”，割的容量是这些边的容量之和。只要还存在增广路，就说明s到t还没有被“完全卡死”，还能继续提高流量；当增广路不存在时，能到t的那一侧所有饱和边正好构成一个最小割。

我用BFS来找增广路，因为BFS能找到“边数最少”的增广路，这保证了算法在O(VE^2)的复杂度内必然结束，不会因为路径选择太差而出现极端情况。这就是经典的Edmonds-Karp算法。

function [maxFlow, flow] = myMaxFlow(cap, s, t) % cap: 容量矩阵，不连通为0 % s: 源点，t: 汇点 n = size(cap, 1); flow = zeros(n, n); while true pre = -ones(1, n); visited = false(1, n); visited(s) = true; queue = s; % BFS寻找增广路 while ~isempty(queue) && ~visited(t) u = queue(1); queue(1) = []; for v = 1:n if ~visited(v) && cap(u, v) - flow(u, v) > 1e-9 visited(v) = true; pre(v) = u; queue(end+1) = v; end end end if ~visited(t) break; % 找不到增广路 end % 计算这条增广路的瓶颈值 bottleneck = inf; v = t; while v ~= s u = pre(v); bottleneck = min(bottleneck, cap(u, v) - flow(u, v)); v = u; end % 更新流量，包括反向边 v = t; while v ~= s u = pre(v); flow(u, v) = flow(u, v) + bottleneck; flow(v, u) = flow(v, u) - bottleneck; v = u; end end maxFlow = sum(flow(s, :)); end

这段代码里那个1e-9是防止浮点误差。实际跑网络流时，容量往往不是整数，累加反向边多次后可能出现极小的残留值，如果不设阈值，BFS可能会在这些“本应为空”的边上反复跑，导致死循环。比赛里如果发现流量模型跑不动或结果异常，检查一下这里通常能解决问题。

4.3 最大流-最小割定理与建模意义

最大流-最小割定理不只是理论结论，它在建模中的直接价值是：求最大流的同时，你能得到瓶颈信息。最小割边就是限制整个网络传输能力的“咽喉”，在实际场景里对应着需要扩容的关键路段、关键管线。

另外，多源多汇问题可以很自然地转换。如果有多个仓库、多个需求点，只需要加一个超级源点，用容量无穷大的边连到所有仓库；再加一个超级汇点，让所有需求点用容量无穷大的边连到它。这样一转换，就能直接用单源单汇的算法求解。

这个转换我后面实战案例里会实际用到。

5. 二分图匹配与匈牙利算法

5.1 二分图匹配的典型场景

二分图是图论里非常实用的一类特殊图：所有顶点分成左右两组，边只存在于左侧和右侧之间。最常见的场景是任务分配问题：左侧是人员，右侧是任务，如果某个人能胜任某件任务，就在两者之间连一条边，问最多能同时安排多少个任务。

类似的还有排班问题：左侧是排班时段，右侧是可值班人员，能值班就连边，目标是尽量覆盖所有时段；还有教室分配问题：左侧是班级，右侧是可使用的教室。这类问题的共性是“一方到另一方的匹配关系”。

二分图的一个关键性质是：它不包含奇环（长度为奇数的环），这正是很多算法可以利用的前提。

5.2 匈牙利算法的递归实现

匈牙利算法用于求二分图最大匹配，核心思路和网络流很像：反复找增广路。这里增广路的含义是“一条从一个未匹配点出发、交替经过非匹配边和匹配边、最终到达另一个未匹配点的路径”。沿着增广路翻转匹配状态，匹配数就能增加1。

function matchCount = myHungarian(adj) % adj: n1行n2列的逻辑矩阵，adj(i,j)=true表示左侧i可以匹配右侧j n1 = size(adj, 1); n2 = size(adj, 2); matchR = -ones(1, n2); % 右侧每个节点匹配的左侧节点编号，-1表示未匹配 matchCount = 0; for u = 1:n1 visited = false(1, n2); if dfs(u) matchCount = matchCount + 1; end end function found = dfs(x) for v = 1:n2 if adj(x, v) && ~visited(v) visited(v) = true; if matchR(v) == -1 || dfs(matchR(v)) matchR(v) = x; found = true; return; end end end found = false; end end

这段代码里的visited数组是关键，它保证在一次尝试匹配中，不会重复试探同一个右侧节点。每次从新的左侧节点u开始时，visited都要重置为全false，这个细节错了整个算法就废了。

匈牙利算法的另一种理解方式是最大流：把二分图左侧接超级源点，右侧接超级汇点，所有边容量设为1，那么最大匹配数就等于最大流量。这种转化在实际比赛里很有用，因为当你已经写好了一个最大流模板，遇到匹配类题目时就可以直接套，不需要再单独写匈牙利算法。但反过来，遇到简单的二分图匹配，手写匈牙利也就十几行，代码效率更高。

6. 综合实战：多源多汇物资调运问题

6.1 场景设定

我把这一章的算法串起来，走一个完整的建模流程。

题目背景：某应急中心需要向两个受灾点运输救援物资。路网抽象后得到5个核心节点：

• 节点1：物资集散中心（唯一的出发点）
• 节点2、节点3：中转枢纽
• 节点4、节点5：两个受灾需求点

每条道路有双向运输能力，单位是“吨/天”，具体容量如下：

问题：每天最多能从中心运出多少吨救援物资，保证两个受灾点都能收到货。

6.2 建图与代码求解

这个案例有两个需求点，属于多汇问题。按前面说的办法，加一个超级汇点6，让节点4和节点5分别连到6，容量设为一个足够大的值，比如999。这样问题就变成标准的单源单汇最大流问题。

cap = zeros(6, 6); cap(1,2) = 40; cap(2,1) = 40; cap(1,3) = 25; cap(3,1) = 25; cap(2,3) = 10; cap(3,2) = 10; cap(2,4) = 30; cap(4,2) = 30; cap(2,5) = 10; cap(5,2) = 10; cap(3,4) = 20; cap(4,3) = 20; cap(3,5) = 15; cap(5,3) = 15; cap(4,6) = 999; cap(6,4) = 999; cap(5,6) = 999; cap(6,5) = 999; [maxFlow, flow] = myMaxFlow(cap, 1, 6); disp(['最大运输能力: ', num2str(maxFlow), ' 吨/天']);

运行这段代码，得到最大流65吨/天。我手动验证一下：节点1总共只有两条出边，容量分别是40和25，合计65，所以无论怎么走，源头一天最多只能发出65吨，这个数字就是理论上限。而算出来的流量分布恰好是：1向2发满40吨，1向3发满25吨；节点2把30吨运往节点4、10吨运往节点5；节点3把10吨转给节点2后，剩余15吨运往节点5。最终节点4收到30吨，节点5收到25吨，两边加起来65吨。完美吻合。

6.3 读懂结果与常见坑

最大流算完，别急着结束。你还要回答两个问题：瓶颈在哪里？如果要提高运力，优先扩哪条路？

从最小割的角度看，节点1的两个出边就是最明显的瓶颈，容量相加恰好是65。如果想提高总运力，优先扩1→2或1→3，而不是去扩中转内部的路段。因为中转内部比如2→3哪怕扩到无限大，源头进不来更多物资也没用。这就是最大流-最小割定理在结果解读上的实际价值。

我在实践中还遇到过这样几个坑，你都值得留意。

第一，容量矩阵不要只填上三角，有向边要单独填，无向边必须双向都填。上面代码里我所有边都写了两个方向，因为救援路网默认双向可通行，容量两侧相同。

第二，超级源点和超级汇点的容量一定要设得足够大，但又不能大到影响其他计算。我习惯用999这种“明显大于其他所有容量之和”的数，保证它不会成为新瓶颈。如果你手算的是几百上千的容量，那超级边的容量要相应提高。

第三，最大流只告诉你“最多能运多少”，它不负责告诉你“哪条路最便宜”。如果要同时考虑运输成本或时间，就需要把问题升级为最小费用最大流，在每条边上再加一个费用权值，用SPFA或Bellman-Ford找“最便宜增广路”。这个方向属于网络流的进阶内容，但建模比赛中出现频率不低，值得在学会最大流之后再进一步。

最后说一点经验：图与网络模型这一章，真正拉开差距的往往不是算法本身，而是“翻译”能力。点怎么定义不重叠，边怎么定义依据充分，权怎么定义和题目指标挂钩，这三步做好，后面调用哪个算法都是水到渠成的事。我带比赛这些年，见过太多把最小生成树当最短路用、把最大流当最短路径用的翻车案例，问题都出在建模初期没有把三要素想清楚。

我个人的习惯是拿到题目先画一张草稿图：圈出实体，连上关系，标上数值，然后对着这张图判断它属于哪类经典模型。这张图画对了，代码半个小时就能写出来；画错了，后面调再久都是在错误方向上打转。希望这一章的几个案例，能帮你建立起这种“先画图、再写码”的建模直觉。