几个常用的matlab图论工具箱函数

时间:2024-05-18 13:36:23

目录

 

Matlab图论工具箱的应用

Matlab图论工具箱

求解所有顶点的最短距离graphallshortestpaths函数

函数说明

Matlab使用方法

函数格式

Matlab调用格式

求解特定起始点的最短路径graphshortestpaths函数

函数说明

函数调用格式

函数参数说明

Matlab调用格式

最小生成树graphminspantree函数

函数说明

函数调用格式

参数说明

Matlab调用格式

计算有向图的最大流graphmaxflow函数

函数说明

函数调用格式

函数参数说明

Matlab调用格式

图的遍历graphtraverse函数

目的

函数说明

函数调用格式

函数参数说明

Matlab调用格式

图的广度优先遍历与深度优先遍历原理简介(仅作参考)

数据结构图中回溯概念的理解(仅作参考)

参考


Matlab图论工具箱的应用

Matlab图论工具箱

命令名

功能

graphallshortestpaths

求图中所有顶点对之间的最短距离

graphconncomp

找无向图的连通分支,或有向图的强弱连通分支

graphisdag

测试有向图是否含有圈,不含圈返回1,否则返回0

graphisomorphism

确定两个图是否同构,同构返回1,否则返回0

graphisspantree

确定一个图是否是生成树,是返回1,否则返回0

graphmaxflow

计算有向图的最大流

graphminspantree

在图中找最小生成树

graphpred2path

把前驱顶点序列变成路径的顶点序列

graphshortestpath

求图中指定的一对顶点间的最短距离和最短路径

graphtopootder

执行有向无圈图的拓扑排序

graphtraverse

求从一顶点出发,所能遍历图中的顶点

我接下来挑选几个常用的函数进行讲解。

求解所有顶点的最短距离graphallshortestpaths函数

函数说明

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调用格式

针对于“有向图”

几个常用的matlab图论工具箱函数

 

构建权值向量&生成网的邻接矩阵

几个常用的matlab图论工具箱函数

 

根据函数调用形式带入函数

注:当横纵坐标相等时,路径为0.

几个常用的matlab图论工具箱函数

 

针对于无向图

几个常用的matlab图论工具箱函数

 

求解特定起始点的最短路径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调用格式

几个常用的matlab图论工具箱函数

几个常用的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调用格式

针对于无向图

几个常用的matlab图论工具箱函数

几个常用的matlab图论工具箱函数

 

 

 

 

针对于有向图

几个常用的matlab图论工具箱函数

几个常用的matlab图论工具箱函数

 

几个常用的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函数的用法”

几个常用的matlab图论工具箱函数

注:稀疏矩阵G中的权值就代表对应路径所能承载的容量。

几个常用的matlab图论工具箱函数

几个常用的matlab图论工具箱函数

 

 

 

这里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表示遍历方法:默认为“深度优先遍历”:

几个常用的matlab图论工具箱函数

 

Depthvalue表示遍历深度值:

表示图G中指定搜索深度的节点的整数。默认值是Inf(无穷大)。

Matlab调用格式

几个常用的matlab图论工具箱函数

几个常用的matlab图论工具箱函数

 

 

 

图的广度优先遍历与深度优先遍历原理简介(仅作参考)

https://www.cnblogs.com/qzhc/p/10291430.html

数据结构图中回溯概念的理解(仅作参考)

https://blog.****.net/weixin_42744107/article/details/106875649

参考

图论工具箱常用函数:

https://www.cnblogs.com/markReaper/p/8454817.html