Matlab中图论工具箱的应用

Matlab图论工具箱的命令见表1

1 matlab图论工具箱的相关命令

命令名

功能

graphallshortestpaths

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

graphconncomp

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

graphisdag

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

graphisomorphism

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

graphisspantree

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

graphmaxflow

计算有向图的最大流

graphminspantree

在图中找最小生成树

graphpred2path

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

graphshortestpath

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

graphtopootder

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

graphtraverse

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

1.图的最短路径graphallshortestpaths函数的命令格式:

[dist]=graphallshortestpaths(G)

[dist]=graphallshortestpaths(G,...’Directed’,DirectedValue,...)

[dist]=graphallshortestpaths(G,...’Weights’,WeightsValue,...)

G是代表一个图的N*N稀疏矩阵,矩阵中的非零值代表一条边的权值:DirectedValue属性表示图是否为有向图,false代表无向图,true代表有向图,默认为true。WeightsValue是矩阵G中边的自定义权值列向量,该属性可以使我们使用零权值。输出[dist]是一个N*N的矩阵,每一个元素代表两点之间最短距离,对角线上的元素总为零,不在对角线上的零表示起点和终点的距离为零,inf值表示没有路径。

1)创建并显示一个含有6个结点11条边的有向图

w=[41 99 51 32 15 45 38 32 36 29 21];%权值向量

dg=sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],w)%构造的稀疏矩阵表示图

h=view(biograph(dg,[],'ShowWeights','on'))%显示图的结构

dist=graphallshortestpaths(dg)%显示图中每对结点之间的最短路径  

dist =

0 136 53 57 21 95

111 0 51 66 32 104

60 94 0 15 81 53

45 79 67 0 66 38

81 115 32 36 0 74

89 41 29 44 73 0

Matlab中图论工具箱的应用

(2)创建无向图,结点信息同上

ug=tril(dg+dg');%要求生成的无向图是一个下三角矩阵

view(biograph(ug,[],'ShowArrows','off','ShowWeights','on'));

dist=graphallshortestpaths(ug,'directed',false)

dist =

0 53 53 45 21 82

53 0 51 66 32 41

53 51 0 15 32 29

45 66 15 0 36 38

21 32 32 36 0 61

82 41 29 38 61 0

Matlab中图论工具箱的应用

2.最小生成树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’算法。

(1)构造无向图

w=[ 41    29    51    32    50    45    38    32    36    29    21];

dg=sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],w)

ug=tril(dg+dg');

view(biograph(ug,[],'ShowArrows','off','ShowWeights','on'));
Matlab中图论工具箱的应用
[st,pred]=graphminspantree(ug)%生成最小生成树

h=view(biograph(st,[],'ShowArrows','off','ShowWeights','on'));

Edges=getedgesbynodeid(h);%提取无向图h的边集

set(Edges,'LineColor',[0 0 0]);%设置颜色属性

set(Edges,'LineWidth',1.5)%设置边值属性
Matlab中图论工具箱的应用

3.计算有向图的最大流graphmaxflow,函数格式为:

[MaxFlow,FlowMatrix,Cut]=graphmaxflow(G,SNode,TNode)

[...]=graphmaxflow(G,SNode,TNode,...’Capacity’,CapacityValue,...)

[...]=graphmaxflow(G,SNode,TNode,...’Method’,MethodValue,...)

G是N*N的稀疏矩阵,表示有向图,SNode和TNode都是G中的节点,分别表示起点和目标点,CapacityValue为每条边自定义容量的列向量;MethodValue可以取‘Edmonds’和‘Goldberg’算法。输出MaxFlow表示最大流,FlowMatrix是表示每条边数据流值的稀疏矩阵,Cut表示连接SNode到TNode的逻辑向量,如果有多个解时,Cut是一个矩阵。

(1)构造带有节点和边的有向图

cm=sparse([1 1 2 2 3 3 4 5],[2 3 4 5 4 5 6 6],[2 3 3 1 1 1 2 3 ],6,6);

%6个节点8条边

[M,F,K]=graphmaxflow(cm,1,6);%计算第1个到第6个节点的最大流

h=view(biograph(cm,[],'ShowWeights','on'));%显示原始有向图的图结构
Matlab中图论工具箱的应用
h1=view(biograph(F,[],'ShowWeights','on'));%显示计算最大流矩阵的图结构
Matlab中图论工具箱的应用

4.图的遍历函数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是祖先节点索引向量

(1)创建一个有向图

DG=sparse([1 2 3 4 5 5 5 6 7 8 8 9],[2 4 1 5 3 6 7 9 8 1 10 2],true,10,10)

h1=view(biograph(DG));
Matlab中图论工具箱的应用
order=graphtraverse(DG,4)%使用深度优先算法从第4个节点开始遍历

order2=graphtraverse(DG,4,'Method','BFS')%使用广度优先遍历

index=graphtraverse(DG,4,'depth',2)%标记与节点4邻近的深度为2的节点

order =

4 5 3 1 2 6 9 7 8 10

order2 =

4 5 3 6 7 1 9 8 2 10

index =

4 5 3 6 7

相关推荐