Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

bfsearch

广度优先图搜索

说明

示例

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)(其中 tftrue)会重新启动搜索。您可以使用上述语法中的任何输入或输出参数组合。此选项可确保广度优先搜索到达图中的所有节点和边,即使这些节点和边无法从起始节点 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. The axes 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. The axes 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. The axes 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' 事件。指定 Restarttrue,以使只要存在无法到达的剩余节点即重新启动搜索。

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   

Restarttrue 时,'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. The axes contains an object of type graphplot.

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

创建并绘制一个有向图。

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. The axes 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. The axes contains an object of type graphplot.

输入参数

全部折叠

输入图,指定为 graphdigraph 对象。可使用 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.EventT.NodeT.EdgeT.EdgeIndex

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

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

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

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

  • T.NodeT.Edge 的未使用的元素设置为 NaN

  • 如果 s 为数值节点索引,则 T.NodeT.Edge 包含数值节点索引。

  • 如果 s 为节点名称,则 T.NodeT.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

开启或关闭重新启动搜索操作,指定为 truefalse(默认值)。如果图包含无法从起始节点到达的节点,则此选项非常有用。如果 '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.EdgeT.EdgeIndex 中的相关边。

在所有情况中:

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

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

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

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

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

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

提示

  • dfsearchbfsearch 将有向图与无向图同等对待。节点 st 之间的无向边被视为两条有向边,其中一条是从 st,另一条是从 ts

算法

广度优先搜索算法在起始节点 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' 事件指示搜索每次重新启动时的起始节点。

在 R2015b 中推出