Main Content

allpaths

查找两个图节点之间的所有路径

自 R2021a 起

全页折叠

语法

paths = allpaths(G,s,t)
[paths,edgepaths] = allpaths(G,s,t)
[___] = allpaths(G,s,t,Name,Value)

说明

paths = allpaths(G,s,t) 返回图 G 中从源节点 s 开始、到目标节点 t 结束的所有路径。输出 paths 是元胞数组，其中每个元胞 paths{k} 的内容列出一条路径中的节点。

示例

[paths,edgepaths] = allpaths(G,s,t) 还返回从 s 到 t 的每条路径中的边。输出 edgepaths 是元胞数组，其中 edgepaths{k} 给出沿对应路径 paths{k} 的边。

示例

[___] = allpaths(G,s,t,Name,Value) 使用一个或多个名称-值参量指定其他选项。您可以使用上述语法中的任何输出参量组合。例如，您可以指定 MaxNumPaths 和一个标量来限制返回的路径数。

示例

示例

全部折叠

打开实时脚本

为具有四个节点的完整图创建一个邻接矩阵，然后基于该邻接矩阵创建一个无向图。绘制图。

A = ones(4);
G = graph(A);
plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

计算图中从节点 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));

Figure contains an axes object. The axes object contains an object of type graphplot.

计算节点 A 和节点 H 之间的所有路径。指定两个输出参量以同时返回沿每条路径的边的边索引。

[paths,edgepaths] = allpaths(G,'A','H');

查看沿第一条路径的节点和边。

paths{1}
ans = 1x6 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

打开实时脚本

使用 '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]}

输入参数

全部折叠

输入图，指定为 graph 或 digraph 对象。可使用 graph 创建一个无向图，或使用 digraph 创建一个有向图。

示例: G = graph(1,2)

示例: G = digraph([1 2],[2 3])

源节点 ID 和目标节点 ID，指定为节点索引或节点名称的单独参量。

值示例
标量节点索引1
字符向量节点名称'A'
字符串标量节点名称"A"

示例: allpaths(G,2,5) 计算节点 2 和节点 5 之间的所有路径。

示例: allpaths(G,'node1','node2') 计算指定节点 node1 和 node2 之间的所有路径。

名称-值参数

将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN，其中 Name 是参量名称，Value 是对应的值。名称-值参量必须出现在其他参量之后，但参量对组的顺序无关紧要。

在 R2021a 之前，使用逗号分隔每个名称和值，并用引号将 Name 引起来。

示例: allpaths(G,s,t,'MaxNumPaths',100) 仅返回路径的字典编纂顺序中的前 100 个结果。

最大路径数，指定为包含 'MaxNumPaths' 和非负整数标量的逗号分隔对组。当两个节点之间的路径数量增长到足以达到内存限制时，此选项非常有用。您可以指定 MaxNumPaths 来限制 allpaths 返回的路径数，以便可用内存能够容纳结果。

示例: allpaths(G,s,t,'MaxNumPaths',100)

最大路径长度，指定为包含 'MaxPathLength' 和非负整数标量的逗号分隔对组。此选项过滤由 allpaths 返回的结果，以确保不返回长度大于指定限制的路径。路径的长度按其中的边数来度量，忽略边权重。

要查找某长度范围内的路径，请同时指定 'MaxPathLength' 和 'MinPathLength'。要查找具有精确指定长度的路径，请为 'MaxPathLength' 和 'MinPathLength' 指定相同的值。

示例: allpaths(G,s,t,'MaxPathLength',4) 返回长度小于或等于 4 的路径。

示例: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) 返回长度为 3、4 或 5 的路径。

最小路径长度，指定为包含 'MinPathLength' 和非负整数标量的逗号分隔对组。此选项过滤由 allpaths 返回的结果，以确保不返回长度小于指定限制的路径。路径的长度按其中的边数来度量，忽略边权重。

要查找某长度范围内的路径，请同时指定 'MaxPathLength' 和 'MinPathLength'。要查找具有精确指定长度的路径，请为 'MaxPathLength' 和 'MinPathLength' 指定相同的值。

示例: allpaths(G,s,t,'MinPathLength',2) 返回长度大于或等于 2 的路径。

示例: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) 返回长度为 3、4 或 5 的路径。

输出参量

全部折叠

指定节点之间的路径，以元胞数组形式返回。每个元素 paths{k} 都包含位于指定源节点和目标节点之间的路径之一上的节点。路径按字典编纂顺序返回。如果源节点和目标节点 s 和 t 指定同一个节点，则按照惯例 allpaths 返回包含该节点的单条路径。如果无法从节点 s 到达节点 t，则 paths 为空。

paths 中条目的数据类型取决于指定 s 和 t 的方式：

  • 如果将 s 和 t 指定为数值节点索引，则每个元素 paths{k} 均为节点索引的数值向量。

  • 如果将 s 和 t 指定为字符串节点名称，则每个元素 paths{k} 均为节点名称的字符串数组。

  • 如果将 s 和 t 指定为字符向量节点名称，则每个元素 paths{k} 均为字符向量节点名称的元胞数组。

沿每条路径的边，以元胞数组形式返回。每个元素 edgepaths{k} 包含沿对应路径的边的边索引 paths{k}。如果无法从节点 s 到达节点 t，则 edgepaths 为空。

详细信息

全部折叠

图路径

图中的路径是一组图边，可以沿这些边从指定的起始节点到达指定的结束节点。按照惯例，沿路径的节点必须唯一，因此路径不包含重复的节点或边。

提示

  • 图中路径的数量很大程度上取决于图的结构。对于某些图结构，路径数可能随着节点数增加而呈指数增长。例如，一个具有由 G = graph(ones(12)) 给出的 12 个节点的完整图包含近 1000 万条任意两个节点之间的路径。在这些情况下，使用 MaxNumPaths、MaxPathLength 和 MinPathLength 名称-值对组来控制 allpaths 的输出。

版本历史记录

在 R2021a 中推出

另请参阅

| | |