Java Reference
In-Depth Information
vertices are connected if they overlap (line 51). The DFS of the graph results in a tree (line 60).
The tree's getNumberOfVerticesFound() returns the number of vertices searched. If it is
equal to the number of circles, all circles are connected (lines 61-62).
28.18
How is a graph created for the connected circles problem?
Check
28.19
When you click the mouse inside a circle, does the program create a new circle?
Point
28.20
How does the program know if all circles are connected?
28.9 Breadth-First Search (BFS)
The breadth-first search of a graph visits the vertices level by level. The first level
consists of the starting vertex. Each next level consists of the vertices adjacent to the
vertices in the preceding level.
Key
Point
The breadth-first traversal of a graph is like the breadth-first traversal of a tree discussed in
Section  25.2.4, Tree Traversal. With breadth-first traversal of a tree, the nodes are visited
level by level. First the root is visited, then all the children of the root, then the grandchildren
of the root, and so on. Similarly, the breadth-first search of a graph first visits a vertex, then all
its adjacent vertices, then all the vertices adjacent to those vertices, and so on. To ensure that
each vertex is visited only once, it skips a vertex if it has already been visited.
28.9.1 Breadth-First Search Algorithm
The algorithm for the breadth-first search starting from vertex v in a graph is described in
Listing 28.11.
L ISTING 28.11
Breadth-First Search Algorithm
Input: G = (V, E) and a starting vertex v
Output: a BFS tree rooted at v
1 Tree bfs(vertex v) {
2 create an empty queue for storing vertices to be visited;
3 add v into the queue;
4 mark v visited;
5
6 while (the queue is not empty) {
7 dequeue a vertex, say u, from the queue;
8 add u into a list of traversed vertices;
9 for each neighbor w of u
10 if w has not been visited {
11 add w into the queue;
12 set u as the parent for w in the tree;
13 mark w visited;
14 }
15 }
16 }
create a queue
enqueue v
dequeue into u
u traversed
check a neighbor w
is w visited?
enqueue w
Consider the graph in Figure 28.15a. Suppose you start the breadth-first search from vertex
0. First visit 0 , then visit all its neighbors, 1 , 2 , and 3 , as shown in Figure 28.15b. Vertex 1
has three neighbors: 0, 2, and 4. Since 0 and 2 have already been visited, you will now visit
just  4 , as shown in Figure 28.15c. Vertex 2 has three neighbors, 0, 1, and 3, which have all
been visited. Vertex 3 has three neighbors, 0, 2, and 4, which have all been visited. Vertex 4
has two neighbors, 1 and 3, which have all been visited. Hence, the search ends.
Since each edge and each vertex is visited only once, the time complexity of the bfs method
is O(|E| + |V|) , where |E| denotes the number of edges and |V| the number of vertices.
BFS time complexity
 
 
 
Search WWH ::




Custom Search