blob: a4afe64e104e17af7d00c12aeb3bf0fdd81d035a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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"
> </TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
> </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"
> </TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
> </TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Bibliography</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
|
