Java Reference
In-Depth Information
0
1
0
1
0
1
2
2
2
3
4
3
4
3
4
(a)
(b)
(c)
F
IGURE
28.15
Breadth-first search visits a node, then its neighbors, then its neighbors's
neighbors, and so on.
28.9.2 Implementation of Breadth-First Search
The
bfs(int v)
method is defined in the
Graph
interface and implemented in the
AbstractGraph
class in Listing 28.3 (lines 197-222). It returns an instance of the
Tree
class
with vertex
v
as the root. The method stores the vertices searched in the list
searchOrder
(line 198), the parent of each vertex in the array
parent
(line 199), uses a linked list for a
queue (lines 203-204), and uses the
isVisited
array to indicate whether a vertex has been
visited (line 207). The search starts from vertex
v
.
v
is added to the queue in line 206 and is
marked as visited (line 207). The method now examines each vertex
u
in the queue (line 210)
and adds it to
searchOrder
(line 211). The method adds each unvisited neighbor
e.v
of
u
to
the queue (line 214), sets its parent to
u
(line 215), and marks it as visited (line 216).
Listing 28.12 gives a test program that displays a BFS for the graph in Figure 28.1 start-
ing from Chicago. The graphical illustration of the BFS starting from Chicago is shown in
Figure 28.16. For an interactive GUI demo of BFS, go to
www.cs.armstrong.edu/liang/animation/
L
ISTING
28.12
TestBFS.java
1
public class
TestBFS {
2
public static void
main(String[] args) {
3 String[] vertices = {
"Seattle"
,
"San Francisco"
,
"Los Angeles"
,
4
vertices
"Denver"
,
"Kansas City"
,
"Chicago"
,
"Boston"
,
"New York"
,
5
"Atlanta"
,
"Miami"
,
"Dallas"
,
"Houston"
};
6
7
int
[][] edges = {
8 {
0
,
1
}, {
0
,
3
}, {
0
,
5
},
9 {
1
,
0
}, {
1
,
2
}, {
1
,
3
},
10 {
2
,
1
}, {
2
,
3
}, {
2
,
4
}, {
2
,
10
},
11 {
3
,
0
}, {
3
,
1
}, {
3
,
2
}, {
3
,
4
}, {
3
,
5
},
12 {
4
,
2
}, {
4
,
3
}, {
4
,
5
}, {
4
,
7
}, {
4
,
8
}, {
4
,
10
},
13 {
5
,
0
}, {
5
,
3
}, {
5
,
4
}, {
5
,
6
}, {
5
,
7
},
14 {
6
,
5
}, {
6
,
7
},
15 {
7
,
4
}, {
7
,
5
}, {
7
,
6
}, {
7
,
8
},
16 {
8
,
4
}, {
8
,
7
}, {
8
,
9
}, {
8
,
10
}, {
8
,
11
},
17 {
9
,
8
}, {
9
,
11
},
18 {
10
,
2
}, {
10
,
4
}, {
10
,
8
}, {
10
,
11
},
19 {
11
,
8
}, {
11
,
9
}, {
11
,
10
}
20 };
21
22 Graph<String> graph =
new
UnweightedGraph<>(vertices, edges);
23
edges
create a graph
AbstractGraph<String>.Tree bfs =
24
graph.bfs(graph.getIndex(
"Chicago"
));
create a BFS tree
25
26 java.util.List<Integer> searchOrders = bfs.getSearchOrder();
get search order
Search WWH ::
Custom Search