summaryrefslogtreecommitdiff
path: root/java/docs/algo/BreadthFirstSearch.html
blob: 47c782cfb7f04ec685f63c3aa5a222ed3640c35c (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
<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.BREADTHFIRSTSEARCH"
></A
>Breadth First Search (BFS)</H1
><P
>&#13;The BFS method performs a breadth-first search  [<A
HREF="bibliography.html#CLR98"
>clr98</A
>] of a graph.
A breadth-first search visits vertices that are closer to the
source before visiting vertices that are further 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.BREADTHFIRSTSEARCH.PSEUDOCODE"
></A
><P
><B
>Figure 1. Pseudocode for the BFS algorithm</B
></P
><PRE
CLASS="PROGRAMLISTING"
>paint all vertices white;
paint the source grey, set its distance to 0 and enqueue it;
repeat
  dequeue vertex v;
  if v is the target, we're done - exit this algorithm;
  paint v black;
  for each white neighbor w of v
	paint w grey;
	set distance w to (distance v + 1);
	set parent w to v;
	enqueue w
until the queue is empty
if we haven't yet exited, we didn't find the target</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
>