summaryrefslogtreecommitdiff
path: root/java/docs/algo/DepthFirstSearch.html
diff options
context:
space:
mode:
Diffstat (limited to 'java/docs/algo/DepthFirstSearch.html')
-rw-r--r--java/docs/algo/DepthFirstSearch.html137
1 files changed, 137 insertions, 0 deletions
diff --git a/java/docs/algo/DepthFirstSearch.html b/java/docs/algo/DepthFirstSearch.html
new file mode 100644
index 0000000..a4afe64
--- /dev/null
+++ b/java/docs/algo/DepthFirstSearch.html
@@ -0,0 +1,137 @@
+<HTML
+><HEAD
+><TITLE
+></TITLE
+><META
+NAME="GENERATOR"
+CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
+REL="NEXT"
+TITLE="Bibliography"
+HREF="bibliography.html"></HEAD
+><BODY
+CLASS="ARTICLE"
+BGCOLOR="#FFFFFF"
+TEXT="#000000"
+LINK="#0000FF"
+VLINK="#840084"
+ALINK="#0000FF"
+><DIV
+CLASS="ARTICLE"
+><DIV
+CLASS="SECT1"
+><H1
+CLASS="SECT1"
+><A
+NAME="JOELIB.ALGORITHMS.DEPTHFIRSTSEARCH"
+></A
+>Depth First Search (DFS)</H1
+><P
+>The DFS method performs a depth--first search [<A
+HREF="bibliography.html#CLR98"
+>clr98</A
+>] of a graph.
+A depth--first search visits vertices that are further to the
+source before visiting vertices that are closer away. In this
+context `distance' is defined as the number of edges in the
+shortest path from the source vertex.
+<DIV
+CLASS="FIGURE"
+><A
+NAME="JOELIB.ALGORITHMS.DEPTHFIRSTSEARCH.PSEUDOCODE"
+></A
+><P
+><B
+>Figure 1. Pseudocode for the DFS algorithm</B
+></P
+><PRE
+CLASS="PROGRAMLISTING"
+>DFS(G)
+ {
+ For each v in V,
+ {
+ color[v]=white;
+ pred[u]=NULL
+ }
+
+ time=0;
+ For each u in V
+ If (color[u]=white) DFSVISIT(u)
+ }
+
+
+ DFSVISIT(u)
+ {
+ color[u]=gray;
+ d[u] = ++time;
+
+ For each v in Adj(u) do
+ If (color[v] = white)
+ {
+ pred[v] = u;
+ DFSVISIT(v);
+ }
+
+ color[u] = black; f[u]=++time;
+ }</PRE
+></DIV
+>
+The time complexity is <IMG
+SRC="formulas/o_e+v.gif"> [<A
+HREF="bibliography.html#CLR98"
+>clr98</A
+>].</P
+></DIV
+></DIV
+><DIV
+CLASS="NAVFOOTER"
+><HR
+ALIGN="LEFT"
+WIDTH="100%"><TABLE
+SUMMARY="Footer navigation table"
+WIDTH="100%"
+BORDER="0"
+CELLPADDING="0"
+CELLSPACING="0"
+><TR
+><TD
+WIDTH="33%"
+ALIGN="left"
+VALIGN="top"
+>&nbsp;</TD
+><TD
+WIDTH="34%"
+ALIGN="center"
+VALIGN="top"
+>&nbsp;</TD
+><TD
+WIDTH="33%"
+ALIGN="right"
+VALIGN="top"
+><A
+HREF="bibliography.html"
+ACCESSKEY="N"
+>Next</A
+></TD
+></TR
+><TR
+><TD
+WIDTH="33%"
+ALIGN="left"
+VALIGN="top"
+>&nbsp;</TD
+><TD
+WIDTH="34%"
+ALIGN="center"
+VALIGN="top"
+>&nbsp;</TD
+><TD
+WIDTH="33%"
+ALIGN="right"
+VALIGN="top"
+>Bibliography</TD
+></TR
+></TABLE
+></DIV
+></BODY
+></HTML
+> \ No newline at end of file