Main Content

bfsearch

广度优先图搜索

全页折叠

语法

v = bfsearch(G,s)
T = bfsearch(G,s,events)
[T,E] = bfsearch(G,s,events)
[___] = bfsearch(___,'Restart',tf)

说明

v = bfsearch(G,s) 将广度优先搜索应用于图 G，从节点 s 开始。结果是按发现顺序排序的节点 ID 向量。

示例

T = bfsearch(G,s,events) 通过标记一个或多个搜索事件，自定义广度优先搜索的输出。例如，T = bfsearch(G,s,'allevents') 返回一个表，其中包含所有已标记的事件，X = bfsearch(G,s,'edgetonew') 返回边的矩阵或元胞数组。

示例

当 events 设置为 'edgetonew'、'edgetodiscovered' 或 'edgetofinished' 时，[T,E] = bfsearch(G,s,events) 还返回边索引 E 的向量。在多重图中，边索引是边的唯一性标识。

如果没有可从已发现的节点到达的新节点，[___] = bfsearch(___,'Restart',tf)（其中 tf 为 true）会重新启动搜索。您可以使用上述语法中的任何输入或输出参量组合。此选项可确保广度优先搜索到达图中的所有节点和边，即使这些节点和边无法从起始节点 s 到达。

示例

示例

全部折叠

打开实时脚本

创建并绘制一个图。

s = [1 1 1 1 2 2 2 2 2];
t = [3 5 4 2 6 10 7 9 8];
G = graph(s,t);
plot(G)

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

在节点 2 处开始执行图的广度优先搜索。结果指示节点发现顺序。

v = bfsearch(G,2)
v = 10×1

     2
     1
     6
     7
     8
     9
    10
     3
     4
     5
打开实时脚本

创建并绘制一个有向图。

s = [1 1 1 2 3 3 3 4 6];
t = [2 4 5 5 6 7 4 1 4];
G = digraph(s,t);
plot(G)

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

从节点 1 开始对图执行一次广度优先搜索。指定 'allevents' 返回一个表，其中包含算法中的所有事件。

T = bfsearch(G,1,'allevents')
T=14×4 table
         Event          Node       Edge       EdgeIndex
    ________________    ____    __________    _________

    startnode             1     NaN    NaN       NaN   
    discovernode          1     NaN    NaN       NaN   
    edgetonew           NaN       1      2         1   
    discovernode          2     NaN    NaN       NaN   
    edgetonew           NaN       1      4         2   
    discovernode          4     NaN    NaN       NaN   
    edgetonew           NaN       1      5         3   
    discovernode          5     NaN    NaN       NaN   
    finishnode            1     NaN    NaN       NaN   
    edgetodiscovered    NaN       2      5         4   
    finishnode            2     NaN    NaN       NaN   
    edgetofinished      NaN       4      1         8   
    finishnode            4     NaN    NaN       NaN   
    finishnode            5     NaN    NaN       NaN

要按照算法中的步骤执行，需要按从上到下的顺序读取表中的事件。例如：

  1. 算法在节点 1 处开始

  2. 在节点 1 和节点 2 之间发现一条边

  3. 发现节点 2

  4. 以些类推...

打开实时脚本

对存在多个分量的图执行广度优先搜索，然后根据搜索结果突出显示图节点和边。

创建并绘制一个有向图。此图有两个弱连通分量。

s = [1 1 2 2 2 3 4 7 8 8 8 8];
t = [3 4 7 5 6 2 6 2 9 10 11 12];
G = digraph(s,t);
p = plot(G,'Layout','layered');

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

c = conncomp(G,'Type','weak')
c = 1×12

     1     1     1     1     1     1     1     2     2     2     2     2

在节点 2 处开始执行图的广度优先搜索，并标记 'edgetonew'、'edgetofinished' 和 'startnode' 事件。指定 Restart 为 true，以使只要存在无法到达的剩余节点即重新启动搜索。

events = {'edgetonew','edgetofinished','startnode'};
T = bfsearch(G,2,events,'Restart',true)
T=15×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           2     NaN    NaN       NaN   
    edgetonew         NaN       2      5         3   
    edgetonew         NaN       2      6         4   
    edgetonew         NaN       2      7         5   
    edgetofinished    NaN       7      2         8   
    startnode           1     NaN    NaN       NaN   
    edgetonew         NaN       1      3         1   
    edgetonew         NaN       1      4         2   
    edgetofinished    NaN       3      2         6   
    edgetofinished    NaN       4      6         7   
    startnode           8     NaN    NaN       NaN   
    edgetonew         NaN       8      9         9   
    edgetonew         NaN       8     10        10   
    edgetonew         NaN       8     11        11   
    edgetonew         NaN       8     12        12

当 Restart 为 true 时，'startnode' 事件会返回算法重新启动搜索时的位置和时间信息。

基于事件突出显示图：

  • 将起始节点设为红色。

  • 绿色边对应于 'edgetonew'

  • 黑色边对应于 'edgetofinished'

highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g')
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') 
highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')

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

打开实时脚本

使用广度优先搜索来确定图为偶图，并返回相关分区。偶图是指其节点可划分为两个集 A 和 B，且图中每条边分别连接 A 和 B 中的一个节点的图。

创建并绘制一个有向图。

s = [1 1 1 1 2 2 4 5 6 7 8];
t = [2 3 6 8 5 10 6 6 10 3 10];
g = digraph(s,t);
plot(g);

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

对图使用广度优先搜索来确定是否为偶图，如果是，则返回相关分区。

events = {'edgetonew', 'edgetodiscovered', 'edgetofinished'};
T = bfsearch(g, 1, events, 'Restart', true);
partitions = false(1, numnodes(g));
is_bipart = true;
is_edgetonew = T.Event == 'edgetonew';
ed = T.Edge;

for ii=1:size(T, 1)   
    if is_edgetonew(ii)
        partitions(ed(ii, 2)) = ~partitions(ed(ii, 1));
    else
        if partitions(ed(ii, 1)) == partitions(ed(ii, 2))
            is_bipart = false;
            break;
        end
    end
end

is_bipart
is_bipart = logical
   1

由于 g 是偶图，partitions 变量包含有关每个节点属于哪个分区的信息。

绘制布局为 'layered' 的偶图，使用 partitions 变量指定在第一层中出现的源节点。

partitions
partitions = 1x10 logical array

   0   1   1   0   0   1   0   1   0   0


plot(g, 'Layout', 'layered', 'Source', find(partitions));

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

输入参数

全部折叠

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

示例: G = graph(1,2)

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

起始节点，指定为下表中的值之一。

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

示例: bfsearch(G,1)

已标记的搜索事件，指定为下表中的选项之一。

  • 要标记单个事件，请使用标志名称。

  • 要标记部分事件，请将两个或更多标志名称放在一个元胞数组或字符串数组中。

  • 要标记所有事件，请使用 'allevents'。

注意

根据 events 的值，bfsearch 的输出会有所不同。请参阅下表中的最后一列，了解有关每个选项返回的输出的信息。

events 的值描述输出
'discovernode'（默认值）

发现新节点。

返回节点 ID 的向量：

  • 如果 s 是数值节点索引，则该向量包含数值节点索引。

  • 如果 s 是节点名称，则该向量是包含节点名称的元胞数组。

'finishnode'

已访问该节点的所有出向边。

'startnode'

此标志指示搜索中的起始节点。

如果 'Restart' 为 true，则 'startnode' 标志搜索每次重新启动时的起始节点。

'edgetonew'

边连接到一个未发现的节点。

返回一个大小为 N×2 的矩阵或元胞数组，它指定图中边的端节点：

  • 如果 s 是数值节点索引，则该矩阵包含数值节点索引。

  • 如果 s 是节点名称，则该矩阵是包含节点名称的元胞数组。

此外，可以使用 [T,E] = bfsearch(…) 指定第二个输出，它返回边索引 E 的向量。

'edgetodiscovered'

边连接到一个先前发现的节点。

'edgetofinished'

边连接到一个已完成的节点。

元胞数组

在元胞数组中指定两个或更多标志以在搜索期间仅标记这些事件。

返回表 T，其中包含变量 T.Event、T.Node、T.Edge 和 T.EdgeIndex：

  • T.Event 是一个分类向量，其中包含按出现顺序排列的标志。

  • T.Node 包含事件 'discovernode'、'finishnode' 和 'startnode' 的相应节点的节点 ID。

  • T.Edge 包含事件 'edgetonew'、'edgetodiscovered' 和 'edgetofinished' 的相应边。

  • T.EdgeIndex 包含事件 'edgetonew'、'edgetodiscovered' 和 'edgetofinished' 的边索引。在多重图中，边索引是重复边的唯一性标识。

  • T.Node 和 T.Edge 的未使用的元素设置为 NaN。

  • 如果 s 为数值节点索引，则 T.Node 和 T.Edge 包含数值节点索引。

  • 如果 s 为节点名称，则 T.Node 和 T.Edge 是包含节点名称的元胞数组。

'allevents'

标记所有事件。

示例: v = bfsearch(G,3) 在第三个节点处开始搜索并返回向量 v，其中包含按发现顺序排序的节点。这与 v = bfsearch(G,3,'discovernode') 相同。

示例: X = bfsearch(G,'A','edgetonew') 在名为 'A' 的节点处开始搜索并返回元胞数组 X，该数组指示在搜索期间连接到一个未发现节点的每条边。

示例: T = bfsearch(G,s,{'discovernode','finishnode'}) 返回表 T，但仅在发现新节点或节点被标记为完成时才做标记。

示例: T = bfsearch(G,s,'allevents') 会对所有搜索事件进行标记并返回表 T。

数据类型: char | string | cell

开启或关闭重新启动搜索操作，指定为 true 或 false（默认值）。如果图包含无法从起始节点到达的节点，则此选项非常有用。如果 'Restart' 为 true，则只要未发现的节点仍无法从已发现的节点到达，即重新启动搜索。新的开始节点是仍未发现的、具有最小索引的节点。重新启动操作将重复执行，直到 bfsearch 发现了所有节点。

默认情况下，'Restart' 为 false，这样搜索仅访问从起始节点可到达的节点。

当 'Restart' 为 true 时，对于图中的每个节点，都会发生一次 'discovernode' 和 'finishnode' 事件。此外，'edgetonew'、'edgetodiscovered' 或 'edgetofinished' 会将图中的每条边都标记一次。由 'edgetonew' 标记的各条边构成一个或多个树。

示例: T = bfsearch(graph([1 3],[2 4]),1,'Restart',true) 同时搜索图中的两个连通分量。

数据类型: logical

输出参量

全部折叠

节点 ID，返回为以下格式之一：

  • 如果您使用数值节点 ID 来指定起始节点 s，则 v 是节点索引的数值列向量。

  • 如果 s 是包含节点名称的字符向量或字符串，则 v 是包含节点名称的元胞向量。

v 中的节点 ID 反映广度优先图搜索的发现顺序。

搜索结果，返回为以下格式之一：

  • 如果 events 未指定或为 'discovernode'、'finishnode' 或 'startnode'，则 T 是类似于 v 的节点 ID 向量。

  • 如果 events 是 'edgetonew'、'edgetodiscovered' 或 'edgetofinished'，则 T 是大小为 N×2 的矩阵或元胞数组，指示每条相关边的源和目标节点。

  • 如果 events 是搜索事件的元胞数组或是 'allevents'，则 T 是包含已标记的搜索事件的表。该表包含 T.Event 中的搜索事件标志、T.Node 中的相关节点 ID 以及 T.Edge 和 T.EdgeIndex 中的相关边。

在所有情况中：

  • T 的元素或行的顺序指示其在搜索期间的出现顺序。

  • 如果您指定 s 为数值节点 ID，则 T 也使用数值 ID 来指代节点。

  • 如果您指定 s 为节点名称，则 T 也使用名称引用节点。

边索引，以向量形式返回。

指定此输出以获取事件 'edgetonew'、'edgetodiscovered' 或 'edgetofinished' 的边索引向量。边索引的 N×1 向量对应于 T，它是大小为 N×2 的矩阵或元胞数组，指示每条相关边的源节点和目标节点。

示例: [T,E] = bfsearch(G,s,'edgetonew')

提示

  • dfsearch 和 bfsearch 将有向图与无向图同等对待。节点 s 和 t 之间的无向边被视为两条有向边，其中一条是从 s 到 t，另一条是从 t 到 s。

算法

广度优先搜索算法在起始节点 s 开始，并按照节点索引顺序检查其所有相邻节点。然后，对于其中每个相邻节点，再按顺序访问它们的未访问相邻节点。算法会连续运行，直到从起始节点可到达的所有节点均已访问。

算法可用伪代码编写为如下形式：

Event startnode(S)
Event discovernode(S)
NodeList = {S}

WHILE NodeList is not empty

  C = NodeList{1}
  Remove first element from NodeList
  
  FOR edge E from outgoing edges of node C, connecting to node N
    Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E)
    (depending on the state of node N)
    IF event was edgetonew
      Event discovernode(N)
      Append N to the end of NodeList
    END
  END

  Event finishnode(C)
END

bfsearch 可返回标志来描述算法中的不同事件，例如，当发现新节点时或某节点的所有出向边均已访问时。此处列出了事件标志。

事件标志事件描述
'discovernode'

发现新节点。

'finishnode'

已访问该节点的所有出向边。

'startnode'

此标志指示搜索中的起始节点。

'edgetonew'

边连接到未发现的节点

'edgetodiscovered'

边连接到先前发现的节点

'edgetofinished'

边连接到已完成的节点

有关详细信息，请参阅 events 的输入参量描述。

注意

若输入图包含无法从起始节点到达的节点，使用 'Restart' 选项可使搜索访问图中的每个节点。在这种情况下，'startnode' 事件指示搜索每次重新启动时的起始节点。

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2015b 中推出

另请参阅

| | |

主题