目录
求解所有顶点的最短距离graphallshortestpaths函数
求解特定起始点的最短路径graphshortestpaths函数
Matlab图论工具箱的应用
Matlab图论工具箱
命令名 |
功能 |
graphallshortestpaths |
求图中所有顶点对之间的最短距离 |
graphconncomp |
找无向图的连通分支,或有向图的强弱连通分支 |
graphisdag |
测试有向图是否含有圈,不含圈返回1,否则返回0 |
graphisomorphism |
确定两个图是否同构,同构返回1,否则返回0 |
graphisspantree |
确定一个图是否是生成树,是返回1,否则返回0 |
graphmaxflow |
计算有向图的最大流 |
graphminspantree |
在图中找最小生成树 |
graphpred2path |
把前驱顶点序列变成路径的顶点序列 |
graphshortestpath |
求图中指定的一对顶点间的最短距离和最短路径 |
graphtopootder |
执行有向无圈图的拓扑排序 |
graphtraverse |
求从一顶点出发,所能遍历图中的顶点 |
我接下来挑选几个常用的函数进行讲解。
求解所有顶点的最短距离graphallshortestpaths函数
函数说明
求图中所有顶点对之间的最短距离 |
Matlab使用方法
① 根据题目构造权值向量;
② 匹配线段的起始点与相应的权值;
③ 调用函数graphallshortestpaths
函数格式
[dist]=graphallshortestpaths(G) |
[dist]=graphallshortestpaths(G,...’Directed’,DirectedValue,...) |
[dist]=graphallshortestpaths(G,...’Weights’,WeightsValue,...) |
函数参数说明
G参数
G参数是什么?
G是个稀疏矩阵,我的理解是稀疏矩阵就是含有大量0的矩阵,可能为了便于存储和加快计算,才采用这种矩阵。实质上G就相当于以路径的始末点作为索引,以路径权值或者容量为内容的实数对。
G参数如何生成?
G并不是图的路径权值矩阵,它由s[]向量和t[]向量和路径权值向量w[]构成:G=spares(s,t,w)。也就是说G应该是个N*3的矩阵,第一行表示节点起点,第二行表示节点终点,第三行是权值。
无向图与有向图的区别?
由于是不重复的三角矩阵,因此生成的稀疏矩阵代表着有向图。如果想要生成无向图,需要这样操作:UG=tril(G+G');就是把G和自己的转置G'加起来再求等价变换得到的下三角矩阵。
DirectedValue属性
属性 |
作用 |
True |
有向图(默认) |
False |
无向图 |
WeightsValue属性
Weightvalue属性一般不用指定,函数graphallshortestpath函数默认从稀疏矩阵G中获取。
Dist输出参数
输出[dist]是一个N*N的矩阵,每一个元素代表两点之间最短距离,对角线上的元素总为零,不在对角线上的零表示起点和终点的距离为零,inf值表示没有路径。
Matlab调用格式
针对于“有向图”
构建权值向量&生成网的邻接矩阵
根据函数调用形式带入函数
注:当横纵坐标相等时,路径为0.
针对于无向图
求解特定起始点的最短路径graphshortestpaths函数
函数说明
graphshortestpaths |
求图中特定顶点对之间的最短距离 |
函数调用格式
[dist,path]=graphshortestpaths(G,S,T) |
[dist,path]=graphshortestpaths(G,S,T’Directed’,DirectedValue,...) |
[dist,path]=graphshortestpaths(G,S,T’Weights’,WeightsValue,...) |
函数参数说明
G |
稀疏矩阵 |
S |
起点 |
T |
终点 |
Dist |
最短距离 |
path |
最短距离经过的路径节点 |
Matlab调用格式
最小生成树graphminspantree函数
函数说明
graphminspantree |
在图中找最小生成树 |
函数调用格式
[Tree,pred]=graphminspantree(G) |
[Tree,pred]=graphminspantree(G,R) |
[Tree,pred]=graphminspantree(...,’Method’,MethofValue,...) |
[Tree,pred]=graphminspantree(...,’Weights’,WeightsValue,...) |
参数说明
该函数用来寻找一个无循环的节点集合,连接无向图的全部节点,并且总的权值最小。
Tree |
一个代表生成树的稀疏矩阵 |
Pred |
包含最小生成的祖先节点的向量 |
G |
稀疏矩阵 |
R |
根节点,取值为1到节点数目 |
Method |
可以选择‘Kruskal’,’Prim’等算法 |
Matlab调用格式
针对于无向图
针对于有向图
计算有向图的最大流graphmaxflow函数
函数说明
graphmaxflow |
计算有向图的最大流 |
函数调用格式
[MaxFlow,FlowMatrix,Cut]=graphmaxflow(G,SNode,TNode) |
[...]=graphmaxflow(G,SNode,TNode,...’Capacity’,CapacityValue,...) |
[...]=graphmaxflow(G,SNode,TNode,...’Method’,MethodValue,...) |
函数参数说明
输入参数G |
N*N的稀疏矩阵 |
输入参数SNode |
起点 |
输入参数TNcode |
目标点 |
CapacityValue属性 |
每条边自定义容量的列向量,默认从G中获取 |
MethodValue属性 |
可以取‘Edmonds’和‘Goldberg’算法 |
输出参数MaxFlow |
网络最大流 |
输出参数FlowMatrix |
每条边数据流的值所组成的稀疏矩阵 |
输出参数cut |
连接起点与目标点的逻辑向量,如果有多个解时,Cut是一个矩阵 |
Matlab调用格式
补充说明“sparse函数的用法” |
注:稀疏矩阵G中的权值就代表对应路径所能承载的容量。
这里K为2行6列的矩阵,代表着2个最优路径。
图的遍历graphtraverse函数
目的
主要是找到一种既不重复又不遗漏的访问方法,可用来判断一个图是否连通。
函数说明
graphtraverse |
求从某一个顶点出发,所能遍历图中的顶点 |
函数调用格式
[disc,pred,closed]=graphtraverse(G,S) |
[...]=graphtraverse(G,S,...’Directed’,DirectedValue,...) |
[...]=graphtraverse(G,S,...’Depth’,DepthValue,...) |
[...]=graphtraverse(G,S,...’Method’,MethodValue,...) |
函数参数说明
G |
有向图的稀疏矩阵 |
S |
起始节点 |
Disc |
节点索引向量 |
Pred |
祖先节点索引向量 |
Methodvalue表示遍历方法:默认为“深度优先遍历”:
Depthvalue表示遍历深度值:
表示图G中指定搜索深度的节点的整数。默认值是Inf(无穷大)。
Matlab调用格式
图的广度优先遍历与深度优先遍历原理简介(仅作参考)
https://www.cnblogs.com/qzhc/p/10291430.html
数据结构图中回溯概念的理解(仅作参考)
https://blog.****.net/weixin_42744107/article/details/106875649
参考
图论工具箱常用函数: