Main Content

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

dfsearch

深度优先图搜索

说明

示例

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)(其中 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.

从节点 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. The axes 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. 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

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

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   

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

输入参数

全部折叠

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

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

在所有情况中:

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

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

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

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

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

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

提示

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

算法

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

在 R2015b 中推出