dfsearch
图深度优先搜索
句法
描述
例子
执行深度优先图搜索
创建并绘制图表。
S = [1 1 1 1 2 2 2 2 2];T = [3 5 4 2 6 10 7 9 8];G =图表（S，T）;图（G）
执行深度优先搜索开始节点7曲线图的结果表示节点发现的顺序。
v = dfsearch (G, 7)
v =10×17 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 1 1 1;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];G =有向图(一个);图（G）
对从节点3开始的图执行深度优先搜索。指定'allevents'返回一个包含所有的算法事件的表。
T = dfsearch (G, 3,'allevents'）
T =13×4表事件节点边缘EdgeIndex ______________ ____ __________ _________的StartNode 3的NaN楠楠discovernode 3的NaN楠楠edgetonew的NaN 3 4 4 discovernode 4的NaN楠楠edgetonew的NaN 4 6 7 discovernode 6的NaN楠楠finishnode 6的NaN楠楠finishnode 4的NaN楠楠edgetofinished的NaN3 6 5 edgetonew的NaN 3 7 6 7 discovernode楠楠的NaN finishnode 7楠楠的NaN 3 finishnode楠楠的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 =有向图（S，T）;P =情节（G，'布局'那“分层”）;
C = conncomp（G，“类型”那“弱”）
c =1×121 1 1 1 1 1 1 2 2 2 2 2
从节点4开始对图执行深度优先搜索，并标记“edgetonew”那'edgetodiscovered'那'edgetofinished',“startnode”事件。指定重新启动作为真正的以便在存在无法到达的剩余节点时重新启动搜索。
事件= {“edgetonew”那'edgetodiscovered'那'edgetofinished'那“startnode”};T = dfsearch（G，4，事件“重启”,真正的)
T =15×4表事件节点边缘EdgeIndex ________________ ____ __________ _________的StartNode 4的NaN楠楠edgetonew的NaN 4 6 7的StartNode 1的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的NaN7 2 8 edgetofinished的NaN 1 4 2的StartNode 8的NaN楠楠edgetonew的NaN 8 9 9 edgetonew的NaN 8 10 10 edgetonew的NaN 8 11 11 edgetonew的NaN 8 12 12
当重新启动是真正的， 这“startnode”事件返回地点和时间的算法重新启动搜索信息。
根据事件突出显示图表:
颜色的起始节点红色。
绿色边是用来
“edgetonew”黑色的边是
'edgetofinished'洋红色的边是
'edgetodiscovered'
亮点（P，“边缘”T.EdgeIndex (T。事件= =“edgetonew”），'EdgeColor'那‘g’)突出(p,“边缘”T.EdgeIndex (T。事件= ='edgetofinished'），'EdgeColor'那“k”)突出(p,“边缘”T.EdgeIndex (T。事件= ='edgetodiscovered'），'EdgeColor'那“米”)突出(p, T.Node (~ isnan (T.Node)),“NodeColor”那'R'）
从图中去除周期
将有向图的一些边反转，使其成为无环图。
创建并绘制有向图。
S = [1 2 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 =有向图(s, t);情节(g,'布局'那“力”）
在图上执行深度优先搜索，标记'edgetodiscovered'事件。此事件对应于完成一个循环的边。
[e,edge_indices] = dfsearch(g, 1, d)'edgetodiscovered'那“重启”,真正的)
e =3×23 1 6 4 8 7
edge_indices =3×13 9 11
使用flipedge反转标记边的方向，使它们不再完成一个循环。这将从图中删除所有周期。使用isdag确认图是无圈的。
Gnew = flipedge(g, edge_indices); / /编辑isdag (gnew)
ANS =逻辑1
绘制新图形并突出显示被翻转的边。
P =情节（gnew，'布局'那“力”）;亮点（P，“边缘”findedge (gnew e (:, 2), e (: 1)),'EdgeColor'那'R'）
输入参数
输出参数
提示
dfsearch和bfsearch将无向图与有向图同等对待。结点之间的无向边S.和T.被处理像两个有向边，从一个S.来T.和一个从T.来S.．
算法
深度优先搜索算法从起始节点开始，S.，并检查邻居S.具有最小节点索引。那么该邻居，它会检查其索引的下一个未被发现的邻居。这样继续下去，直到搜索遇到其邻居都被访问过的节点。在这一点上，沿路径有一个未被发现的邻居最近先前发现的节点搜索回溯。这个过程一直持续，直到可达从起始节点的所有节点都被访问。
在伪代码中，（递归）算法可以写为：
事件startnode (S)调用DFS (S)函数DFS (C)事件discovernode (C)边缘E C从外向的边缘节点,连接节点N事件edgetonew (C、E), edgetodiscovered (C、E)或edgetofinished (C, E)(取决于节点N)的状态如果事件是edgetonew叫DFS (N)结束结束事件finishnode (C)
dfsearch可以返回标记来描述算法中的不同事件，例如当发现一个新节点时，或者当一个节点的所有传出边都被访问时。这里列出了事件标志。
| 事件标志 | 事件描述 |
|---|---|
“discovernode” |
发现新节点。 |
“finishnode” |
所有从节点发出的边都被访问过。 |
“startnode” |
这个标志表示搜索的开始节点。 |
“edgetonew” |
边缘连接到未发现的节点 |
'edgetodiscovered' |
Edge连接到以前发现的节点 |
'edgetofinished' |
边缘连接到一个成品节点 |
有关的更多信息，请参见输入参数描述事件．
笔记
如果输入图包含从起始节点无法到达的节点，则“重启”选项提供了一种方法，使搜索访问图中的每个节点。在这种情况下“startnode”Event表示每次重新启动搜索时的起始节点。
你也可以从以下列表中选择一个网站:
