allpaths
查找两个图节点之间的所有路径
说明
示例
为具有四个节点的完整图创建一个邻接矩阵，然后基于该邻接矩阵创建一个无向图。绘制图。
A = ones(4); G = graph(A); plot(G)
计算图中从节点 1 开始到节点 3 结束的所有路径。
paths = allpaths(G,1,3)
paths=5×1 cell array
{[ 1 2 3]}
{[1 2 4 3]}
{[ 1 3]}
{[1 4 2 3]}
{[ 1 4 3]}
allpaths 的第二个输出参量返回沿每条路径的边。这对于多重图特别有用，多重图需要边索引来唯一识别路径中的边。
创建一个包含 8 个节点和 18 条边的有向多重图。指定节点的名称。绘制一个包含带标签的节点和边的图。
s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3];
t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7];
names = {'A','B','C','D','E','F','G','H'};
G = digraph(s,t,[],names);
p = plot(G,'EdgeLabel',1:numedges(G));
计算节点 A 和节点 H 之间的所有路径。指定两个输出参量以同时返回沿每条路径的边的边索引。
[paths,edgepaths] = allpaths(G,'A','H');
查看沿第一条路径的节点和边。
paths{1}ans = 1×6 cell
{'A'} {'B'} {'C'} {'E'} {'G'} {'H'}
edgepaths{1}ans = 1×5
1 4 9 13 17
突出显示沿第一条路径的节点和边。
highlight(p,'Edges',edgepaths{1},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)
使用 'MaxNumPaths'、'MaxPathLength' 和 'MinPathLength' 选项来限制 allpaths 返回的路径数。
为包含 20 个节点的完整图创建一个邻接矩阵。从该邻接矩阵创建一个无向图，省略自环。
A = ones(20);
G = graph(A,'omitselfloops');由于图中的所有节点都连接到所有其他节点，图中任意两个节点之间都有大量路径（超过 1.7e16 个）。因此，计算两个节点之间的所有路径是不可行的，因为内存中容纳不下结果。在这种情况下，计算从节点 2 到节点 5 的前 10 条路径。
paths1 = allpaths(G,2,5,'MaxNumPaths',10)paths1=10×1 cell array
{[ 2 1 3 4 5]}
{[ 2 1 3 4 6 5]}
{[ 2 1 3 4 6 7 5]}
{[ 2 1 3 4 6 7 8 5]}
{[ 2 1 3 4 6 7 8 9 5]}
{[ 2 1 3 4 6 7 8 9 10 5]}
{[ 2 1 3 4 6 7 8 9 10 11 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 13 5]}
{[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}
现在计算节点 2 和节点 5 之间路径长度小于或等于 2 的前 10 条路径。
paths2 = allpaths(G,2,5,'MaxNumPaths',10,'MaxPathLength',2)
paths2=10×1 cell array
{[ 2 1 5]}
{[ 2 3 5]}
{[ 2 4 5]}
{[ 2 5]}
{[ 2 6 5]}
{[ 2 7 5]}
{[ 2 8 5]}
{[ 2 9 5]}
{[2 10 5]}
{[2 11 5]}
最后，计算节点 2 和节点 5 之间路径长度大于或等于 3 的前 10 条路径。
paths3 = allpaths(G,2,5,'MaxNumPaths',10,'MinPathLength',3)
paths3=10×1 cell array
{[ 2 1 3 4 5]}
{[ 2 1 3 4 6 5]}
{[ 2 1 3 4 6 7 5]}
{[ 2 1 3 4 6 7 8 5]}
{[ 2 1 3 4 6 7 8 9 5]}
{[ 2 1 3 4 6 7 8 9 10 5]}
{[ 2 1 3 4 6 7 8 9 10 11 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 13 5]}
{[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}
输入参数
名称-值参数
输出参量
详细信息
提示
图中路径的数量很大程度上取决于图的结构。对于某些图结构，路径数可能随着节点数增加而呈指数增长。例如，一个具有由
G = graph(ones(12))给出的 12 个节点的完整图包含近 1000 万条任意两个节点之间的路径。在这些情况下，使用MaxNumPaths、MaxPathLength和MinPathLength名称-值对组来控制allpaths的输出。
版本历史记录
在 R2021a 中推出
