📄 dfs-dfs2.html
字号:
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color=#ff0080>/** Execute a depth first search traversal on graph g, starting * from a start vertex s, passing in an information object (in) */</font> <font color=#8000a0><font color=#8000a0>public</font> </font>R <font color=#0000ff>execute</font>(Graph<V, E> g, Vertex<V> s, <font color=#8000a0>I </font>in) { graph = g; start = s; info = in; <font color=#ff8000>for</font><font color=#0000ff></font>(Vertex<V> v: graph.<font color=#0000ff>vertices</font>()) <font color=#0000ff>unVisit</font>(v); <font color=#ff0080>// mark vertices as unvisited</font> <font color=#ff8000>for</font><font color=#0000ff></font>(Edge<E> e: graph.<font color=#0000ff>edges</font>()) <font color=#0000ff>unVisit</font>(e); <font color=#ff0080>// mark edges as unvisited</font> <font color=#0000ff>setup</font>(); <font color=#ff0080>// perform any necessary setup prior to DFS traversal</font> <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>finalResult</font>(<font color=#0000ff>dfsTraversal</font>(start)); } <font color = #ff0080>/** Recursive template method for a generic DFS traversal. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font>R <font color=#0000ff>dfsTraversal</font>(Vertex<V> v) { <font color=#0000ff>initResult</font>(); <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isDone</font>()) <font color=#0000ff>startVisit</font>(v); <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isDone</font>()) { <font color=#0000ff>visit</font>(v); <font color=#ff8000>for</font><font color=#0000ff> </font>(Edge<E> e: graph.<font color=#0000ff>incidentEdges</font>(v)) { <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isVisited</font>(e)) { <font color=#ff0080>// found an unexplored edge, explore it</font> <font color=#0000ff>visit</font>(e); Vertex<V> w = graph.<font color=#0000ff>opposite</font>(v, e); <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isVisited</font>(w)) { <font color=#ff0080>// w is unexplored, this is a discovery edge</font> <font color=#0000ff>traverseDiscovery</font>(e, v); <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isDone</font>()) <font color=#ff8000>break</font>; visitResult = <font color=#0000ff>dfsTraversal</font>(w); <font color=#ff0080>// get result from DFS-tree child</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isDone</font>()) <font color=#ff8000>break</font>; } <font color=#ff8000>else</font> { <font color=#ff0080>// w is explored, this is a back edge</font> <font color=#0000ff>traverseBack</font>(e, v); <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isDone</font>()) <font color=#ff8000>break</font>; } } } } <font color=#ff8000>if</font><font color=#0000ff></font>(!<font color=#0000ff>isDone</font>()) <font color=#0000ff>finishVisit</font>(v); <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>result</font>(); }</dl></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -