Main Content

dfsearch

深度优先图搜索

全页折叠

语法

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

说明

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

示例

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

示例

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

如果没有可从已发现的节点到达的新节点，[___] = dfsearch(___,'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.

从节点 7 开始对图执行深度优先搜索。结果指示节点发现顺序。

v = dfsearch(G,7)
v = 10×1

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

创建并绘制一个有向图。

A = [0 1 0 1 1 0 0; 
     0 0 0 0 0 0 0; 
     0 0 0 1 0 1 1;
     0 0 0 0 0 1 0; 
     0 0 0 0 0 0 0; 
     0 0 0 0 0 0 0; 
     0 0 0 0 0 0 0];
G = digraph(A);
plot(G)

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

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

T = dfsearch(G,3,'allevents')
T=13×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           3     NaN    NaN       NaN   
    discovernode        3     NaN    NaN       NaN   
    edgetonew         NaN       3      4         4   
    discovernode        4     NaN    NaN       NaN   
    edgetonew         NaN       4      6         7   
    discovernode        6     NaN    NaN       NaN   
    finishnode          6     NaN    NaN       NaN   
    finishnode          4     NaN    NaN       NaN   
    edgetofinished    NaN       3      6         5   
    edgetonew         NaN       3      7         6   
    discovernode        7     NaN    NaN       NaN   
    finishnode          7     NaN    NaN       NaN   
    finishnode          3     NaN    NaN       NaN

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

  1. 算法在节点 3 处开始

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

  3. 发现节点 4

  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

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

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

    startnode             4     NaN    NaN       NaN   
    edgetonew           NaN       4      6         7   
    startnode             1     NaN    NaN       NaN   
    edgetonew           NaN       1      3         1   
    edgetonew           NaN       3      2         6   
    edgetonew           NaN       2      5         3   
    edgetofinished      NaN       2      6         4   
    edgetonew           NaN       2      7         5   
    edgetodiscovered    NaN       7      2         8   
    edgetofinished      NaN       1      4         2   
    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'

  • 品红色边对应于 'edgetodiscovered'

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

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

打开实时脚本

通过逆转有向图某些边的方向来生成无环图。

创建并绘制一个有向图。

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

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

对图执行深度优先搜索，从而标记 'edgetodiscovered' 事件。此事件对应于构成循环的各边。

[e,edge_indices] = dfsearch(g, 1, 'edgetodiscovered', 'Restart', true)
e = 3×2

     3     1
     6     4
     8     7


edge_indices = 3×1

     3
     9
    11

使用 flipedge 将标记的边反向，使其不再构成循环。这会删除图中的所有循环。使用 isdag 确认图为无环图。

gnew = flipedge(g, edge_indices);
isdag(gnew)
ans = logical
   1

绘制新图并突出显示翻转的边。

p = plot(gnew, 'Layout', 'force');
highlight(p,'Edges',findedge(gnew,e(:,2),e(:,1)),'EdgeColor','r')

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"

示例: dfsearch(G,1)

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

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

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

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

注意

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

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

发现新节点。

返回节点 ID 的向量：

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

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

'finishnode'

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

'startnode'

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

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

'edgetonew'

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

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

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

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

此外，可以使用 [T,E] = dfsearch(…) 指定第二个输出，它返回边索引 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 = dfsearch(G,3) 在第三个节点处开始搜索并返回向量 v，其中包含按发现顺序排序的节点。这与 v = dfsearch(G,3,'discovernode') 相同。

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

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

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

数据类型: char | string | cell

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

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

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

示例: T = dfsearch(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] = dfsearch(G,s,'edgetonew')

提示

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

算法

深度优先搜索算法开始于起始节点 s，并检查 s 的具有最小节点索引的相邻节点。然后，对于该相邻节点，算法会检查下一个具有最小索引的未发现的相邻节点。这一过程会连续运行，直到搜索遇到一个其相邻节点均已访问过的节点。在该时间点，搜索将沿着路径回溯，找到前面发现的节点中有未发现的相邻节点的最近节点。此过程会连续运行，直到从起始节点可到达的所有节点均已访问。

该算法（递归算法）可用伪代码编写为如下形式：

Event startnode(S)
Call DFS(S)

function DFS(C)

  Event discovernode(C)
  
  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
      Call DFS(N)
    END
  END

Event finishnode(C)  

END

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

事件标志事件描述
'discovernode'

发现新节点。

'finishnode'

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

'startnode'

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

'edgetonew'

边连接到未发现的节点

'edgetodiscovered'

边连接到先前发现的节点

'edgetofinished'

边连接到已完成的节点

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

注意

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

扩展功能

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

版本历史记录

在 R2015b 中推出

另请参阅

| | |

主题