四、图与网络模型

4.1 图的基本概念与数据结构

4.1.1 基本概念

4.1.2 图与网络的数据结构

计算机上描述图与网络主要有两种方法：邻接矩阵表示法和稀疏矩阵表示法。
假设$G=(V,E)$是一个简单无向图，顶点集合$V=v_1,...,v_n$，边集合$E=e_1,...,e_m$，记$|V|=n,|E|=m$

1. 数据结构的重要性

• 目的：在计算机上实现网络优化算法
• 关键影响：算法效率取决于图的表示方法和中间结果操作方案

2. 两种核心表示方法

邻接矩阵表示法

• 适用场景：任意图（尤其稠密图）
• 存储原理：$n\times n$ 矩阵 $W=(w_{ij})$
• 定义：
  • 赋权图：
    $$w_{ij}=\{\begin{array}{ll}\text{权值},& v_i\text{ 与 }{v}_j\text{ 有边}\\ 0\text{ 或 }\infty ,& \text{无边}\end{array}$$
  • 非赋权图：
    $$w_{ij}=\{\begin{array}{ll}1,& v_i\text{ 与 }{v}_j\text{ 有边}\\ 0,& \text{无边}\end{array}$$
• 优缺点：
  • ✅ 优点：直观易查边
  • ❌ 缺点：边数 $m\ll n^2$ 时空间浪费严重

稀疏矩阵表示法

• 适用场景：边数远小于顶点数的图

• 存储原理：仅存储非零元素 (行地址, 列地址, 值)

• 优缺点：

  • ✅ 优点：节省存储空间
  • ❌ 缺点：需要特殊处理对称性

• MATLAB处理：

图类型	存储规则	MATLAB 命令
有向图	存储所有非零元素	sparse(W) → 直接转换
无向图	仅存储下三角非零元素	sparse(tril(W)) → 忽略上三角
格式转换	稀疏矩阵 ↔ 普通矩阵	sparse()/full()

3. 关键特性对比

特性	邻接矩阵	稀疏矩阵
空间复杂度	$O(n^2)$	$O(m)$（非零元素数）
查找边效率	$O(1)$（直接访问）	$O(m)$（需遍历）
适用图规模	小型稠密图	大型稀疏图
对称性处理	显式存储所有元素	无向图只需存一半

注：当 $m<0.2n^2$ 时优先选择稀疏矩阵（空间节省 >80%）

4. MATLAB 操作示例

%% 邻接矩阵 → 稀疏矩阵（无向图）
W = [0 2 0; 2 0 1; 0 1 0];  % 无向图邻接矩阵
sparse_W = sparse(tril(W))  % 只存储下三角% 输出：
% (1,1)    0
% (2,1)    2
% (2,2)    0
% (3,2)    1
% (3,3)    0%% 稀疏矩阵 → 邻接矩阵
full_W = full(sparse_W) + tril(sparse_W,-1)'  % 恢复对称性

4.2 最短路径问题

4.2.1 两个指定顶点之间的最短路径

1. 问题描述

• 场景：铁路网络中寻找两个指定城镇间的最短路线
• 目标：求两个指定顶点 $u_0$ 和 $v_0$ 间具有最小权的路
• 术语：
  • 最短路：权值最小的路径
  • 距离 $d(u_0,v_0)$：最短路的权值

2. 赋权图模型

G = (V, E, W)

顶点集 $V$：表示各个城镇 $v_1,v_2,\cdots ,v_n$
邻接矩阵 $W$：
$$w_{ij}=\{\begin{array}{c}直通铁路距离，v_i与v_j有连接\\ \infty ,无连接\end{array}$$

3. Dijkstra算法

核心思想： 按距起点 $u_0$ 从近到远的顺序，逐步求得 $u_0$ 到各顶点的最短路
算法步骤：

1. 初始化：

• 起点标号：$l(u_0)=0$
• 其他顶点标号：$l(v)=\infty$
• 已确定集合：$S_0=u_0$
• 迭代计数：$i=0$

2. 更新标号：

• 对每个 $v\notin S_i$（未确定顶点）：
  l(v)=min{l(v),min⁡u∈Si[l(u)+w(u,v)]}l(v)=min\{l(v),\min_{u \in S_i}[l(u)+w(u,v)]\}l(v)=min{l(v),u∈Si​min​[l(u)+w(u,v)]}
• 找出最小标号顶点：$u_{i+1}=\arg {\min }_{v\notin S_i}l(v)$
• 更新集合：$S_{i+1}=S_i\cup u_{i+1}$

3. 终止条件：

• 若 $i=|V|-1$（所有顶点已处理），停止
• 否则 $i\leftarrow i+1$，返回步骤2

标号类型：

标号类型	含义	状态
T标号	顶点进入 $S_i$ 前的临时标号	未确定最短路径
P标号	顶点进入 $S_i$ 时的永久标号	已确定最短路径

4. 算法特性

1. 输出结果

• $l(v)$ 给出 $u_0$ 到 $v$ 的最短距离
• 通过回溯边可得到完整路径

2. 适用条件：

• 非负权值（铁路距离 $w_{ij}\ge 0$）
• 有向图/无向图均可

3. 复杂度：

• 时间复杂度：$O(|V{|}^2)$
• 空间复杂度：$O(|V|)$

clc,clear
a=zeros(6); %邻接矩阵初始化
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';
a(a==0)=inf;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;
temp=1; %最新的P标号的顶点
while sum(pb)<length(a)tb=find(pb==0);d(tb)=min(d(tb),d(temp)+a(temp,tb));tmpb=find(d(tb)==min(d(tb)));temp=tb(tmpb(1)); %可能有多个点同时达到最小值，取一个pb(temp)=1;index1=[index1,temp];temp2=find(d(index1)==d(temp)-a(temp,index1));index2(temp)=index1(temp2(1));
end
d,index1,index2

从起点sb到终点db的通用Dijkstra标号算法程序：

function [mydistance,mypath]=mydijkstra(a,sb,db)
%输入：a-邻接矩阵；a(i,j)-i到j的距离，可以是有向的
%sb-起点的标号；db-终点的标号
%输出：mydistance-最短路的距离；mypath-最短路的路径
n=size(a,1);visited(1:n)=0;
distance(1:n)=inf;distance(sb)=0; %起点到各顶点的距离初始化
visited(sb)=1;u=sb; %u为最新的P标号顶点
parent(1:n)=0; %前驱顶点的初始化
for i=1:n-1id=find(visited==0); %查找未标号的顶点for v=idif a(u,v)+distance(u)<distance(v)distance(v)=distance(u)+a(u,v); %修改距离值parent(v)=u;endendtemp=distance;temp(visited==1)=inf; %已标号的距离设为无穷[t,u]=min(temp);visited(u)=1; %标记已经标号的顶点
end
if parent(db)~=0 %如果存在路t=db;mypath=[db];while t~=sbp=parent(t);mypath=[p mypath];t=p;end
end
mydistance=distance(db);

4.2.2 两个指定顶点之间最短路径问题

1. 问题描述

• 目标：求有向图中从顶点 (v_1) 到顶点 (v_n) 的最短路径
• 图结构：
  • 顶点数：(n)
  • 弧集合：(E)

2. 邻接矩阵定义

$$\begin{gathered} W=(w_{ij}{)}_{n\times n} \\ \text{其中}{w}_{ij}=\{\begin{array}{ll}\text{弧 }{v}_i{v}_j\text{ 的权值},& v_i{v}_j\in E\\ \infty ,& \text{其他}\end{array} \end{gathered}$$

3. 决策变量

$$x_{ij}=\{\begin{array}{ll}1,& \text{弧 }{v}_i{v}_j\text{ 在最短路径上}\\ 0,& \text{其他}\end{array}$$

4. 数学规划模型

目标函数（最小化路径总权值）

$$\min \sum _{v_i{v}_j\in E}{w}_{ij}{x}_{ij}$$

约束条件（流量平衡方程）

{∑j=1nx1j−∑j=1nxj1=1(起点 v1 净流出)∑j=1nxnj−∑j=1nxjn=−1(终点 vn 净流入)∑j=1nxij−∑j=1nxji=0∀i≠1,n(中间点流量守恒)xij∈{0,1}∀i,j \begin{cases} \sum_{j=1}^{n} x_{1j} - \sum_{j=1}^{n} x_{j1} = 1 & \text{(起点 } v_1 \text{ 净流出)} \\ \sum_{j=1}^{n} x_{nj} - \sum_{j=1}^{n} x_{jn} = -1 & \text{(终点 } v_n \text{ 净流入)} \\ \sum_{j=1}^{n} x_{ij} - \sum_{j=1}^{n} x_{ji} = 0 & \forall i \neq 1,n \quad \text{(中间点流量守恒)} \\ x_{ij} \in \{0,1\} & \forall i,j \end{cases} ⎩⎨⎧​∑j=1n​x1j​−∑j=1n​xj1​=1∑j=1n​xnj​−∑j=1n​xjn​=−1∑j=1n​xij​−∑j=1n​xji​=0xij​∈{0,1}​(起点 v1​ 净流出)(终点 vn​ 净流入)∀i=1,n(中间点流量守恒)∀i,j​

5. 模型解读

1. 目标函数：最小化所选路径的总长度
2. 起点约束：(v_1) 必须有且只有一条出弧被选中
3. 中间点约束：流入量 = 流出量（流量守恒）
4. 隐含终点约束：通过方程组自动满足$(\sum x_{jn}-\sum x_{nj}=1)$
5. 决策变量：二进制选择保证路径的连续性

6. 模型特点

特性	说明
问题类型	0-1整数规划
约束数量	(n) 个（每个顶点一个约束）
变量数量	(|E|) 个（每条弧一个变量）
求解难度	NP-Hard（但存在高效算法）

实际求解中通常使用Dijkstra算法（非负权）或Bellman-Ford算法（含负权）

4.2.3 每对顶点之间的最短路径

  计算赋权图中各对顶点之间的最短路径，可以调用Dijkstra算法。每次以不同的顶点作为起点，用Dijkstra算法求从该起点到其他顶点的最短路径，反复执行$n-1$次。这种方法时间复杂度为$O(n^3)$。
第二种解决方法是Floyd算法。
对于赋权图$G=(V,E,A_0)$，邻接矩阵：
$$A_0=\left[\begin{array}{c}{a}_{11}{a}_{12}...a_{1,n}\\ a_{21}{a}_{22}...a_{2,n}\\ ...\\ a_{n1}{a}_{n2}...a_{n,n}\end{array}\right]$$
其中：
$$\begin{gathered} a_{ij}=\{\begin{array}{ll}权值,& 当v_i{v}_j之间有连接\\ \infty ,& 当v_i{v}_j之间无连接\end{array} \\ {a}_{ii}=0,i=1,2,...,n \end{gathered}$$
对于无向图，$A_0$是对称矩阵。
Floyd算法的基本思想是递推产生一个矩阵序列$A_1,...A_k,...A_n$，其中$A_k(i,j)$表示从顶点$v_i$到顶点$v_j$的路径上经过的顶点序号不大于k的最短路径长度。
计算时用迭代公式：
$$A_k(i,j)=min(A_{k-1}(i,j),A_{k-1}(i,k)+A_{k-1}(k,j))$$
k是迭代次数，$i,j,k=1,2,...,n$。最后，当$k=n$时，$A_n$即时各顶点之间的最短通路值。

clc,clear
n=6;a=zeros(n);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;a(5,6)=55;
a=a+a';
a(a==0)=inf; 
a([1:n+1:n^2])=0; %把对角线元素替换为0
path=zeros(n);
for k=1:nfor i=1:nfor j=1:nif a(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendend
end
a,path

从起点sb到终点db通用的Floyd算法程序如下：

function [dist,mypath]=myfloyd(a,sb,db)
%输入：a-邻接矩阵；a(i,j)-i,j之间的距离，可以有向
%sb-起点标号；db-终点标号
%输出：dist-最短路的距离；mypath-最短路的路径
n=size(a,1);path=zeros(n);
for k=1:nfor i=1:nfor j=1:nif a(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendend
end
dist=a(sb,db);
parent=path(sb,:); %从sb到db最短路径上各顶点的前驱顶点
parent(parent==0)=sb; %path中的分量为0，表示该顶点的前驱顶点是起点
mypath=db;t=db;
while t~=sbp=parent(t);mypath=[p,mypath];t=p;
end

4.3 最小生成树问题

4.3.1 基本概念

4.3.2 最小生成树

  修建连接n个城市的铁路，已知$i$城与$j$城之间的铁路造价为$c_{ij}$，设计线路图，使总造价最低。
问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。
构造最小生成树有两种常用方法：
1.prim算法
构造连通赋权图$G=(V,E,W)$的最小生成树，设置两个集合$P$和$Q$，$P$用于存放最小生成树中的顶点，$Q$用于存放最小生成树中的边。$P$的初值为P={v1}P=\{v_1\}P={v1​}（假设从顶点$v_1$出发），$Q$的初值为空集。
prim算法的思想是，从所有$p\in P,v\in V-P$的边中，选出具有最小权值的边$pv$，将顶点$v$加入集合$P$中，将边$pv$加入$Q$中，如此重复，直到$P=V$时，最小生成树构造完毕，这时$Q$中包含了最小生成树的所有边。

算法如下：
（1）P={v1},Q=∅P=\{v_1\},Q= \emptysetP={v1​},Q=∅
（2）while $P\ne V$
找最小边$pv$，其中$p\in P,v\in V-P$；
$$\begin{gathered} P=P+v; \\ Q=Q+pv; \end{gathered}$$
例题：

%用result的第一、二、三行分别表示最小生成树边的起点、终点、权集合
clc,clear
a=zeros(7);
a(1,2)=50;a(1,3)=60;
a(2,4)=65;a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50;a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(a==0)=inf;
result=[];
p=1;tb=2:length(a);
while size(result,2) ~= length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d,1); %找第一个最小值j=p(jb);k=tb(kb);result=[result,[j;k:d]];p=[p,k];tb(find(tb==k))=[];
end
result
%最小生成树边集为：{v1v2,v2v5,v5v4,v4v6,v4v7,v7v3}

2.Kruskal算法
算法如下：
(1）选$e_1\in E(G)$，使得$e_1$是权值最小的边。
(2) 若$e_1,e_2,...,e_i$已经选好，则从E(G)−{e1,e2,...ei}E(G)-\{e_1,e_2,...e_i\}E(G)−{e1​,e2​,...ei​}中选取$e_{i+1}$，使得：

• {e1,e2,...ei,ei+1}\{e_1,e_2,...e_i,e_{i+1}\}{e1​,e2​,...ei​,ei+1​}无圈；
• $e_{i+1}$是E(G)−{e1,e2,...ei}E(G)-\{e_1,e_2,...e_i\}E(G)−{e1​,e2​,...ei​}中权值最小的边。

(3) 直到选得$e_{|V|-1}$为止

例题：

用index存放各边端点信息，将选中边的顶点序号中较大序号$u$改为此边的另一序号$v$，同时把后面边中的所有序号为$u$的改为$v$。
几何意义是将序号$u$顶点收缩到$v$顶点，$u$顶点不复存在。后面寻查时，两个顶点序号相同则失去被选资格。

clc,clear
a(1,[2,3])=[50,60];a(2,[4,5])=[65,40];
a(3,[4,7])=[52,45];a(4,[5,6])=[50,30];
a(4,7)=42;a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,:);
loop=length(a)-1;
result=[];
while length(result)<looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=index(1,flag);v2=index(2,flag);if v1~=v2result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];
end
result

4.4 网络最大流问题

4.4.1 概念定义

4.4.2 求最大流的标号法（Ford-Fulkerson）

从$v_s$到$v_t$的一个可行流出发（若网络中没有给定$f$，则可以设$f$是零流），经过标号过程与调整过程，即可求得从$v_s$到$v_t$的最大流。

1.标号过程
顶点$v_x$有两个标号：第一个标号表示在可能的增广路上$v_x$的前驱顶点；第二个标号${\delta }_x$表示在可能的增广路上可以调整的流量。
（1）初始化，出发点$v_s$标号为$(0,\infty )$
（2）若顶点$v_x$已标号，则对所有未标号的邻接顶点$v_y$标号：

• 若$(v_x,v_y)\in A$，且$f_{xy}<c_{xy}$时，令δy=min{cxy−fxy,δx}\delta_y=min\{c_{xy}-f_{xy},\delta_x\}δy​=min{cxy​−fxy​,δx​}，则顶点$v_y$标号为$(v_x,{\delta }_y)$；若$f_{xy}=c_{xy}$，则不标号。
• 若$(v_y,v_x)\in A$，且$f_{yx}>0$时，令δy=min{fyx,δx}\delta_y=min\{f_{yx},\delta_x\}δy​=min{fyx​,δx​}，则顶点$v_y$标号为$(-v_x,{\delta }_y)$，$-v_x$表示在可能的增广路上$(v_y,v_x)$为反向弧；若$f_{yx}=0$，则不标号。

（3）重复（2）直至收点$v_t$被标号，或没有顶点可以标号为止。$v_t$被标号时表明存在一条从$v_x$到$v_y$的增广路，则转向增流过程。若收点$v_t$不能被标号，且没有顶点可以标号时，表明不存在条从$v_x$到$v_y$的增广路，算法结束，此时获得的流为最大流。

2.增流过程
（1）令$v_y=v_t$
（2）若$v_y$的标号为$(v_x,{\delta }_t)$，则$f_{xy}=f_{xy}+{\delta }_t$；若标号为$(-v_x,{\delta }_t)$，则$f_{yx}=f_{yx}-{\delta }_t$
（3）若$v_y=v_x$，去掉全部标号，并回到标号过程。否则，令$v_y=v_x$，并回到步骤（2）。

最大流算法的实现可以使用Matlab工具箱。

4.5 最小费用最大流问题

4.5.1 最小费用最大流

4.5.2 最小费用流的一种迭代方法

算法步骤：
（1）求从发点到收点的最小费用通路$\mu (s,t)$
（2）对该通路分配最大可能的流量
f‾=min⁡(vi,vj)∈μ(s,t){cij}\overline{f}=\min_{(v_i,v_j) \in \mu(s,t)}\{c_{ij}\}f​=(vi​,vj​)∈μ(s,t)min​{cij​}
并让通路上所有边的容量相应减少$\overline{f}$。对于通路上的饱和边，其单位流费用相应改为$\infty$。
（3）作该通路上所有边$(v_i,v_j)$的反向边$(v_j,v_i)$，令
$$c_{ji}=\overline{f},b_{ji}=-b_{ij}$$
（4）重复步骤（1）、（2）、（3），直至从发点到收点的全部流量等于指定的$v(f)$为止（或再也找不到从$v_s$到$v_t$的最小费用通路）。

4.6 Matlab图论工具箱

4.6.1 Matlab图论工具箱命令

命令名	功能
graphallshortestpaths	求图中所有顶点对之间的最短距离
graphconncomp	找无向图的连通分支，或有向图的强（弱）连通分支
graphisdag	测试有向图是否有圈，不含圈返回1，否则返回0
graphisomorphism	确定两个图是否同构，同构返回1，否则返回0
graphisspantree	确定一个图是否是生成树，是返回1，否则返回0
graphmaxflow	计算有向图的最大流
graphminspantree	在图中找最小生成树
graphpred2path	把前驱顶点序列变成路径的顶点序列
graphshortestpath	求图中指定一对顶点间的最短距离和最短路径
graphtopoorder	执行有向无圈图的拓扑排序
graphtraverse	求从一顶点出发，所能遍历图中的顶点

4.6.2 应用实例

1.无向图最短路径问题
求从v1到v11的最短路径及长度

clc,clear
a(1,2)=2;a(1,3)=8;a(1,4)=1;
a(2,3)=6;a(2,5)=1;
a(3,4)=7;a(3,5)=5;a(3,6)=1;a(3,7)=2;
a(4,7)=9;
a(5,6)=3;a(5,8)=2;a(5,9)=9;
a(6,7)=4;a(6,9)=6;
a(7,9)=3;a(7,10)=1;
a(8,9)=7;a(8,11)=9;
a(9,10)=1;a(9,11)=2;
a(10,11)=4;
a=a'; %Matlab工具箱要求数据是下三角矩阵
[i,j,v]=find(a);
b=sparse(i,j,v,11,11) %构造稀疏矩阵
[x,y,z]=graphshortestpath(b,1,11,'Directed',false) %Directed是标志图为有向或无向的属性，该图是无向图，属性值设为false（也可以写为0）

2.渡河问题

clc,clear
a=[1,1,1,1;1,1,1,0;1,1,0,1;1,0,1,1;1,0,1,0;0,1,0,1;0,1,0,0;0,0,1,0;0,0,0,1;0,0,0,0]; %每一行都是一个可行状态
b=[1,0,0,0;1,1,0,0;1,0,1,0;1,0,0,1]; %每一行都是一个转移状态
w=zeros(10); %邻接矩阵初始化
for i=1:9for j=i+1:10for k=1:4if findstr(xor(a(i,:),b(k,:)),a(j,:))w(i,j)=1;endendend
end
w=w'; %变为下三角矩阵
c=sparse(w); %构造稀疏矩阵
[x,y,z]=graphshortestpath(c,1,10,'Directed',0) %无向图
h=view(biograph(c,[],'ShowArrows','off','ShowWeights','off')); %画出无向图
Edges=getedgesbynodeid(h); %提取句柄h中的边集
set(Edges,'LinColor',[0 0 0]); %边画出黑色
set(Edges,'LinWidth',1.5); %线宽设为1.5

3.有向图最短路径问题

clc,clear
a=zeros(7);
a(1,2)=4;a(1,3)=2;
a(2,3)=3;a(2,4)=2;a(2,5)=6;
a(3,4)=5;a(3,6)=4;
a(4,5)=2;a(4,6)=7;
a(5,6)=4;a(5,7)=8;
a(6,7)=3;
b=sparse(a); %构造稀疏矩阵
[x,y,z]=graphshortestpath(b,1,7,'Directed',1,'Method','Bellman-Ford')
%有向图，Directed设为；'Method'属性默认值为Dijkstra
view(biograph(b,[]))

4.构造最小生成树问题

clc,clear
x=[0 5 16 20 33 23 35 25 10];
y=[15 20 24 20 25 11 7 0 3];
xy=[x;y];
d=mandist(xy); %求xy的两两列向量间的绝对值距离
d=tril(d); %截取下三角矩阵
b=sparse(d) %转化为稀疏矩阵
[ST,pred]=graphminspantree(b,'Method','Kruskal') 
st=full(ST); %把最小生成树矩阵转化为普通矩阵
TreeLength=sum(sum(st)) %求最小生成树的长度
view(biograph(ST,[],'ShowArrows','off')) %画出最小生成树

5.最大流问题

clc,clear,a=zeros(9);
a(1,2)=6;a(1,3)=4;a(1,4)=5;
a(2,3)=3;a(2,5)=9;a(2,6)=9;
a(3,4)=4;a(3,5)=6;a(3,6)=7;a(3,7)=3;
a(4,7)=5;a(4,9)=2;
a(5,8)=12;
a(6,5)=8;a(6,8)=10;
a(7,6)=4;a(7,8)=15;
a(9,3)=2;
b=sparse(a);
[x,y,z]=graphmaxflow(b,1,8)

新版 MATLAB（R2015b 及之后）中移除了旧的 graph… 系列命令（这些命令属于旧式的“图论工具箱”）。MathWorks 在 R2015b 版本中引入了全新的、面向对象的图形和图论算法处理方式，将图作为一等公民 (graph 和 digraph 对象) 来操作。
为什么移除？
面向对象设计： 新设计将图本身定义为一个对象 (graph 用于无向图，digraph 用于有向图)，所有操作都是基于这个对象的方法或作用于该对象的函数。这更符合现代编程习惯，代码更易读、易维护、易扩展。
集成与统一： 新功能紧密集成在 MATLAB 核心中（不再是一个独立的“工具箱”概念），与绘图、矩阵运算等其他功能结合更顺畅。
性能与功能增强： 新实现通常性能更好，并添加了旧工具箱不具备的功能（如更丰富的可视化选项、更多算法）。
简化 API： 新函数命名更直观（如 shortestpath, maxflow），参数传递方式也更一致。

替代方案：

旧命令（已弃用）	新命令
graphallshortestpaths	distances 函数。例如：D = distances(G)
graphconncomp	conncomp 函数。例如：[bins, binsizes] = conncomp(G)
graphisdag	isdag 函数。例如：tf = isdag(DG) (DG 是 digraph 对象)
graphisomorphism	isisomorphic 函数。例如：tf = isisomorphic(G1, G2)
graphisspantree	没有直接单函数对应。通常通过检查：边数=节点数-1 (numedges(G) == numnodes(G)-1) 且 conncomp(G) 返回单个连通分量 (max(binsizes)==numnodes(G)) 来判断。
graphmaxflow	maxflow 函数。例如：[mf, GF, cs, ct] = maxflow(DG, s, t)
graphminspantree	minspantree 函数。例如：[T, pred] = minspantree(G)
graphpred2path	通常使用 shortestpath 函数自动获取路径。手动转换可用：path = predecessors2path(pred, s, t) (需自定义此辅助函数，逻辑简单)。shortestpathtree 的输出也可用于构建路径。
graphshortestpath	shortestpath 函数 (求路径) 和 distances 函数 (仅求距离)。例如：[P, d] = shortestpath(G, s, t)
graphtopoorder	toposort 函数。例如：order = toposort(DG)
graphtraverse	dfsearch (深度优先) 或 bfsearch (广度优先) 函数。例如：v_order = dfsearch(G, start_node)

关键变化和使用方法：
1.创建图对象：所有操作都基于 graph (无向图) 或 digraph (有向图) 对象。你需要先用 graph 或 digraph 函数创建图。

% 创建无向图
G = graph(s, t); % s, t 是定义边的源节点和目标节点向量
% 创建有向图
DG = digraph(s, t);
% 也可以创建带权图
G = graph(s, t, weights);
DG = digraph(s, t, weights);
% 或者从邻接矩阵创建
G = graph(A); % A 是稀疏或满的邻接矩阵
DG = digraph(A);

2.使用函数： 创建图对象 G 或 DG 后，调用上表中列出的新函数（如 distances, conncomp, shortestpath, minspantree, maxflow, toposort, dfsearch, bfsearch 等），并将图对象作为第一个参数传入。
3.参数顺序： 非常重要！ 新函数的第一个参数总是图对象。旧命令中图通常是最后一个参数。这是迁移代码时最常见的错误来源。

• 旧：[dist] = graphshortestpath(adj_matrix, start_node, end_node);
• 新：先创建图 G = graph(adj_matrix); 然后 [P, dist] = shortestpath(G, start_node, end_node);
  4.pred 到 path 的转换： 像 minspantree 或 shortestpathtree 这样的函数会返回前驱节点向量 pred。新版没有直接的 graphpred2path。如果需要手动从 pred 和终点 t 回溯到起点 s 的路径，可以写一个简单的循环：

function path = predecessors2path(pred, s, t)path = t;while t ~= st = pred(t); % 找到 t 的前驱节点path = [t, path]; % 将前驱节点插入路径开头end
end

更推荐使用 shortestpath(G, s, t) 直接获取路径，或者使用 shortestpathtree 的输出对象（它包含了源点到所有点的路径信息）。

4.7 TSP(旅行商)问题

4.7.1 修改圈近似算法

function main
a=zeros(6);
a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;
a(5,6)=13;a=a+a';L=size(a,1);
c=[5 1:4 6 5]; %初始圈
[circle,long]=modifycircle(a,L,c) %调用自定义函数%自定义函数：modifycircle
function [circle,long]=modifycircle(a,L,c)
for k=1:Lflag=0; %退出标志for m=1:L-2 %m为算法中的ifor n=m+2:L %n为算法中的jif a(c(m),c(n))+a(c(m+1),c(n+1))<a(c(m),c(m+1))+a(c(n),c(n+1))c(m+1:n)=c(n:-1:m+1);flag=flag+1; %修改一次，标志加1endendendif flag==0 %一条边也没有修改，则返回long=0; %圈长的初始值for i=1:Llong=long+a(c(i),c(i+1)); %求改良圈长endcircle=c; %返回修改圈end
end

4.7.2 TSP问题的数学规划模型