前言

\(matlab\)封装了很有非常实用的图论算法，如最短路，最小生成树，网络流等。本篇将简要介绍\(matlab\)图论的相关命令。

一、基本命令

更多命令可在\(matlab\)函数窗口中找到

二、应用举例

1.最短路

//g稀疏矩阵
//s,t起点终点
//0,1无向有向
//‘Bellman-Ford‘图论算法，默认dijkstra
//dis最短路程
//path最短路径
[dis,path,pred]=graphshortestpath(g,s,t,‘Directed‘,0 or 1,‘Method‘,‘Bellman-Ford‘)

无向图：

code：

a=zeros(11);
a(1,2) =2;a(1,3) =8;a(1,4) =1;
a(2,3) =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(5,6) =3;a(5,8) =2;a(5,9) =9;
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‘; //转化为下三角
//[i,j,v]=find(a); //寻找边权不为0的边并将横纵坐标赋给i,j，边权赋给v
//b=sparse(i,j,v,11,11);  //建立稀疏矩阵以减小空间复杂度
//法二
b=sparse(a‘); //直接建立稀疏矩阵
[x,y,z]=graphshortestpath(b,1,11,‘Directed‘,1)

有向图

code：

a=zeros(7);
a(1,2)=4;a(1,3)=2;
a(2,3)=3;a(2,5)=6;a(2,4)=2;
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;
//[i,j,v]=find(a);
//b=sparse(i,j,v,7,7);
b=sparse(a);
[x,y,z]=graphshortestpath(b,1,7,‘Directed‘,1)

2.最小生成树

[ST,pred]=graphminspantree(g,‘Method‘,‘Kruskal‘)
view(biograph(ST,[],‘ShowArrows‘,‘off‘))//画出最小生成树

知识补充

sparse
full
find

【matlab】图论工具箱