Java Reference
In-Depth Information
27 System.out.println(bfs.getNumberOfVerticesFound() +
28 " vertices are searched in this order:" );
29 for ( int i = 0 ; i < searchOrders.size(); i++)
30 System.out.println(graph.getVertex(searchOrders.get(i)));
31
32 for ( int i = 0 ; i < searchOrders.size(); i++)
33 if (bfs.getParent(i) != -1 )
34 System.out.println( "parent of " + graph.getVertex(i) +
35
" is " + graph.getVertex(bfs.getParent(i)));
36 }
37 }
12 vertices are searched in this order:
Chicago Seattle Denver Kansas City Boston New York
San Francisco Los Angeles Atlanta Dallas Miami Houston
parent of Seattle is Chicago
parent of San Francisco is Seattle
parent of Los Angeles is Denver
parent of Denver is Chicago
parent of Kansas City is Chicago
parent of Boston is Chicago
parent of New York is Chicago
parent of Atlanta is Kansas City
parent of Miami is Atlanta
parent of Dallas is Kansas City
parent of Houston is Atlanta
28.9.3 Applications of the BFS
Many of the problems solved by the DFS can also be solved using the BFS. Specifically, the
BFS can be used to solve the following problems:
Detecting whether a graph is connected. A graph is connected if there is a path
between any two vertices in the graph.
Detecting whether there is a path between two vertices.
Finding a shortest path between two vertices. You can prove that the path between
the root and any node in the BFS tree is a shortest path between the root and the node.
(See Check Point Question 28.25.)
Finding all connected components. A connected component is a maximal connected
subgraph in which every pair of vertices are connected by a path.
Detecting whether there is a cycle in the graph (see Programming Exercise 28.6).
Finding a cycle in the graph (see Programming Exercise 28.7).
Testing whether a graph is bipartite. (A graph is bipartite if the vertices of the graph
can be divided into two disjoint sets such that no edges exist between vertices in the
same set.) (See Programming Exercise 28.8.)
28.21 What is the return type from invoking bfs(v) ?
28.22
Check
What is breadth-first search?
Point
28.23
Draw a BFS tree for the graph in Figure 28.3b starting from node A .
28.24
Draw a BFS tree for the graph in Figure 28.1 starting from vertex Atlanta .
28.25
Prove that the path between the root and any node in the BFS tree is a shortest path
between the root and the node.
 
 
Search WWH ::




Custom Search