dfsearch
深度优先图搜索
语法
说明
示例
创建并绘制一个图。
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)
从节点 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)
在节点 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
要按照算法中的步骤执行，需要按从上到下的顺序读取表中的事件。例如：
算法在节点 3 处开始
在节点 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');
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')
通过逆转有向图某些边的方向来生成无环图。
创建并绘制一个有向图。
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')
对图执行深度优先搜索，从而标记 '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')
输入参数
输出参量
提示
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' 事件指示搜索每次重新启动时的起始节点。
扩展功能
版本历史记录
在 R2015b 中推出
