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 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];G =有向图(A);情节(G)
在从节点3开始的图上执行深度优先搜索。指定“allevents”返回一个包含算法中所有事件的表。
T = dfsearch(G,3，“allevents”）
T =13×4表Event Node Edge EdgeIndex ______________ ______________ _________ startnode 3 NaN NaN NaN发现Node 3 NaN NaN NaN edgetonnew NaN 3 4 4 discovernode 4 NaN NaN NaN NaN edgetonnew NaN 4 6 7 discovernode 6 NaN NaN NaN finishnode 6 NaN NaN NaN finishnode 4 NaN NaN NaN edgetofinished NaN 3 6 5 edgetonnew 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 8];T = [3 4 7 5 6 2 6 2 9 10 11 12];G =有向图(s,t);p = plot(G，“布局”，“分层”）;
c = concomp (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南南南edgetonew南4 6 7 startnode 1南南南edgetonew南1 3 1 edgetonew南3 2 6 edgetonew南2 5 3 edgetofinished南2 6 4 edgetonew南2 7 5 edgetodiscovered南7 2 8 edgetofinished南1 4 2 startnode 8南南南edgetonew南8 9 9 edgetonew南8 10 10 edgetonew南8 11 11 edgetonew南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 3 4 5 6 7 8 9 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_indexes] = dfsearch(g, 1，“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 = plot(gnew，“布局”，“力”）;突出(p,“边缘”findedge (gnew e (:, 2), e (: 1)),“EdgeColor”，“r”）
输入参数
输出参数
提示
dfsearch而且bfsearch将无向图视为有向图。节点之间的无向边年代而且t被处理成两条有向边，一条来自年代来t还有一个来自t来年代．
算法
深度优先搜索算法从起始节点开始，年代，并检查的邻居年代它的节点索引最小。然后，对于该邻居，它检查下一个索引最低的未发现邻居。这一直持续下去，直到搜索遇到一个其所有邻居都被访问过的节点。此时，搜索将沿着路径回溯到之前发现的最近的节点，该节点具有未发现的邻居。这个过程将继续进行，直到访问了从开始节点可访问的所有节点为止。
在伪代码中，(递归)算法可以写成:
事件开始节点(S)调用DFS(S)函数DFS(C)事件发现节点(C) FOR边缘E从节点C的出边缘，连接到节点N事件edgetonnew (C,E)， edgetodiscovered(C,E)或edgetofinished(C,E)(取决于节点N的状态)IF事件是edgetonnew调用DFS(N) END END事件结束节点(C) END
dfsearch可以返回标记来描述算法中的不同事件，例如当发现新节点时，或者当节点的所有出边都已被访问时。事件标志列在这里。
| 国旗事件 | 事件描述 |
|---|---|
“discovernode” |
已发现新节点。 |
“finishnode” |
该节点的所有出边都已被访问。 |
“startnode” |
该标志表示搜索中的开始节点。 |
“edgetonew” |
Edge连接到未发现的节点 |
“edgetodiscovered” |
Edge连接到先前发现的节点 |
“edgetofinished” |
Edge连接到已完成的节点 |
的输入参数描述，以获取更多信息事件．
请注意
如果输入图包含从起始节点无法到达的节点，则使用“重启”选项提供了一种使搜索访问图中的每个节点的方法。在这种情况下，“startnode”Event表示每次重新开始搜索时的开始节点。
您也可以从以下列表中选择一个网站:
