dfsearch

---

深度优先图搜索

函数库: TyMath

语法

v = dfsearch(G,s)
T = dfsearch(G,s,events)
T,E = dfsearch(G,s,events)
___ = dfsearch(___; restart=false)

说明

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=false)（其中 restart=true）会重新启动搜索。您可以使用上述语法中的任何输入或输出参数组合。此选项可确保深度优先搜索到达图中的所有节点和边，即使这些节点和边无法从起始节点 s 到达。示例

示例

执行深度优先图搜索

创建一个图。

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

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

v = dfsearch(G,7)

v = 10-element Vector{Int64}:
  7
  2
  1
  3
  4
  5
  6
  8
  9
 10

使用所有事件的深度优先图搜索

创建一个有向图。

using TyMath
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);

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

T = dfsearch(G, 3, "allevents")

T = 13×5 Matrix{Any}:
 "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.以此类推...

使用多个分量的深度优先图搜索

使用多个分量对图执行深度优先搜索。

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

using TyMath
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);

c = conncomp(G,"weak")[1]

c = 12-element Vector{Int64}:
 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×5 Matrix{Any}:
 "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" 事件会返回算法重新启动搜索时的位置和时间信息。

从图中删除循环

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

创建并绘制一个有向图。

using TyMath
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);

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

e,edge_indices = dfsearch(g, 1, "edgetodiscovered", restart=true)

e = 3×2 Matrix{Int64}:
 3  1
 6  4
 8  7

edge_indices = 3-element Vector{Int64}:
  3
  9
 11

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

gnew = flipedge(g, edge_indices);
isdag(gnew)

ans = true

输入参数

G - 输入图

Graph 对象 | DiGraph 对象

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

示例： G = Graph(1,2)

示例： G = DiGraph([1,2],[2,3])

s - 起始节点

节点索引 | 节点名称

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

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

示例： dfsearch(G,1)

events - 已标记的搜索事件

"discovernode" （默认） | "startnode" | "finishnode" | "edgetonew" | "edgetodiscovered" | "edgetofinished" | "allevents" | 字符串数组

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

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

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

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

注意

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

events 的值	说明	输出
"discovernode"（默认值）	发现新节点。	返回节点 ID 的向量： 如果 s 是数值节点索引，则该向量包含数值节点索引。 如果 s 是节点名称，则该向量是包含节点名称的字符串向量。
"finishnode"	已访问该节点的所有出向边。
"startnode"	此标志指示搜索中的起始节点。 如果 restart=true，则 "startnode" 标志搜索每次重新启动时的起始节点。
"edgetonew"	边连接到一个未发现的节点。	返回一个大小为 N×2 的矩阵，它指定图中边的端节点： 如果 s 是数值节点索引，则该矩阵包含数值节点索引。 如果 s 是节点名称，则该矩阵是包含节点名称的字符串矩阵。 T,E = dfsearch(…) 中 E 指定了第二个输出，它返回边索引 E 的向量。
"edgetodiscovered"	边连接到一个先前发现的节点。
"edgetofinished"	边连接到一个已完成的节点。
字符串数组	在字符串数组中指定两个或更多标志以在搜索期间仅标记这些事件。	返回矩阵 T，其中包含 Event、Node、Edge 和 EdgeIndex： Event 列中包含按出现顺序排列的标志。 Node 包含事件 "discovernode"、"finishnode" 和 "startnode" 的相应节点的节点 ID。 Edge 包含事件 "edgetonew"、"edgetodiscovered" 和 "edgetofinished" 的相应边。 EdgeIndex 包含事件 "edgetonew"、"edgetodiscovered" 和 "edgetofinished" 的边索引。在多重图中，边索引是重复边的唯一性标识。 Node 和 Edge 的未使用的元素设置为 NaN。 如果 s 为数值节点索引，则 Node 和 Edge 包含数值节点索引。 如果 s 为节点名称，则 Node 和 Edge 列为节点名称。
"allevents"	标记所有事件。

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

示例： X, E = dfsearch(G,"A","edgetonew") 在名为 "A" 的节点开始搜索并返回字符串数组 X，该数组指示在搜索期间连接到一个未发现节点的每条边。E 代表这些边在图中的索引。

示例： T = dfsearch(G,s,["discovernode","finishnode"]) 返回矩阵 T，但仅在发现新节点或节点被标记为完成时才做标记。

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

restart - 开启或关闭重新启动搜索操作

false （默认） | true

开启或关闭重新启动搜索操作，指定为 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) 同时搜索图中的两个连通分量。

输出参数

v - 节点 ID

数值向量 | 字符串向量

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

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

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

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

T - 搜索结果

向量 | 矩阵

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

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

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

• 如果 events 是搜索事件的字符串数组或是 "allevents"，则 T 是包含已标记的搜索事件的矩阵。该矩阵包含 Event 列中的搜索事件标志、Node 列中的相关节点 ID 以及 Edge 和 EdgeIndex 列中的相关边。

在所有情况中：

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

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

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

E - 边索引

向量

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

事件 "edgetonew"、"edgetodiscovered" 或 "edgetofinished" 的边索引向量。边索引的 N×1 向量对应于 T，它是大小为 N×2 的矩阵，指示每条相关边的源节点和目标节点。

提示

• 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=true 选项可使搜索访问图中的每个节点。在这种情况下，"startnode" 事件指示搜索每次重新启动时的起始节点。

另请参阅

bfsearch | ismultigraph | DiGraph | Graph