This chapter provides knowledge of BFS. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Breadth-First Search 3/25/14 16:17 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Breadth-First Search L0 L1 A B C L2 © 2014 Goodrich, Tamassia, Goldwasser E D F Breadth-First Search 1 Breadth-First Search q q Breadth-first search (BFS) is a general technique for traversing a graph A BFS traversal of a graph G n n n n Visits all the vertices and edges of G Determines whether G is connected Computes the connected components of G Computes a spanning forest of G © 2014 Goodrich, Tamassia, Goldwasser q q BFS on a graph with n vertices and m edges takes O(n + m ) time BFS can be further extended to solve other graph problems n n Breadth-First Search Find and report a path with the minimum number of edges between two given vertices Find a simple cycle, if there is one 2 1 Breadth-First Search 3/25/14 16:17 BFS Algorithm q The algorithm uses a mechanism for setting and getting “labels” of vertices and edges Algorithm BFS(G) Input graph G Output labeling of the edges and partition of the vertices of G for all u ∈ () setLabel(u, UNEXPLORED) for all e ∈ () setLabel(e, UNEXPLORED) for all v ∈ () if getLabel(v) = UNEXPLORED BFS(G, v) © 2014 Goodrich, Tamassia, Goldwasser Algorithm BFS(G, s) L0 ← new empty sequence (s) setLabel(s, VISITED) i←0 while ¬() Li +1 ← new empty sequence for all v ∈ () for all e ∈ (v) if getLabel(e) = UNEXPLORED w ← opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) setLabel(w, VISITED) Li +(w) else setLabel(e, CROSS) i ← i +1 Breadth-First Search 3 Java Implementation © 2014 Goodrich, Tamassia, Goldwasser Breadth-First Search 4 2 Breadth-First Search 3/25/14 16:17 Example unexplored vertex visited vertex unexplored edge discovery edge cross .
