20. Breadth-First Search

Written by Irina Galata

In the previous chapter, you explored how you can use graphs to capture relationships between objects. Remember that objects are vertices, and the relationships between them are represented by edges.

Several algorithms exist to traverse or search through a graph’s vertices. One such algorithm is the breadth-first search (BFS) algorithm.

You can use BFS to solve a wide variety of problems:

1. Generating a minimum-spanning tree.
2. Finding potential paths between vertices.
3. Finding the shortest path between two vertices.

Example

BFS starts by selecting any vertex in a graph. The algorithm then explores all neighbors of this vertex before traversing the neighbors of said neighbors and so forth. As the name suggests, this algorithm takes a breadth-first approach because it doesn’t visit the children until all the siblings are visited.

To get a better idea of how things work, you’ll look at a BFS example using the following undirected graph:

Note: Highlighted vertices represent vertices that have been visited.

To keep track of which vertices to visit next, you can use a queue. The first in, first out approach of the queue guarantees that all of a vertex’s neighbors are visited before you traverse one level deeper.

1. To begin, pick a source vertex to start from. In this example, you choose A, which is added to the queue.
2. As long as the queue is not empty, you can dequeue and visit the next vertex, in this case, A. Next, you need to add all A’s neighboring vertices [B, D, C] to the queue.

Note: You only add a vertex to the queue when it has not yet been visited and is not already in the queue.

3. The queue is not empty, so you need to dequeue and visit the next vertex, which is B. You then need to add B’s neighbor E to the queue. A is already visited, so it doesn’t get added. The queue now has [D, C, E].
4. The next vertex to be dequeued is D. D does not have any neighbors that aren’t visited. The queue now has [C, E].

5. Next, you need to dequeue C and add its neighbors [F, G] to the queue. The queue now has [E, F, G].

Note that you have now visited all of A’s neighbors, and BFS moves on to the second level of neighbors.

6. You need to dequeue E and add H to the queue. The queue now has [F, G, H]. Note that you don’t add B or F to the queue because B is already visited and F is already in the queue.

7. You need to dequeue F, and since all of its neighbors are already in the queue or visited, you don’t need to add anything to the queue.
8. Like the previous step, you need to dequeue G but you don’t add anything to the queue.

9. Finally, you need to dequeue H. The breadth-first search is complete since the queue is now empty.

10. When exploring the vertices, you can construct a tree-like structure, showing the vertices at each level: First the vertex you started from, then its neighbors, then its neighbors’ neighbors and so on.

Implementation

Open the starter project for this chapter. This project contains an implementation of a graph that was built in the previous chapter. It also includes a stack-based queue implementation, which you’ll use to implement BFS.

Og yuod dfujgil ffolejm, hoo’mr yekuji Zfidn.tx. Omq tgu gezkukukd papduk ma hdu Kyuvk nriqp:

fun breadthFirstSearch(source: Vertex<T>): ArrayList<Vertex<T>> {
  val queue = QueueStack<Vertex<T>>()
  val enqueued = mutableSetOf<Vertex<T>>()
  val visited = ArrayList<Vertex<T>>()

  // more to come ...

  return visited
}

Seru, nau ziyitif jlo gigtip lxaiwgkRungfBeajkr() hlahc canum ug e qcoypoww gubded. Un azat ypyoo roci fvwemxosaq:

1. puoii: Geitk zraxd ik cno liuvyyucunl fezbakeb bu gagaj sobd.
2. akyaieuh: Lekuwviqp rxebr notremad nuvi luub ayguooud, la muu qem’q iqraaao yci vape magxud rxaje.
3. nituvej: On ilqir kobh ylac htusuv sqi ungul ap mnosh wya duxxohuj beso isphoviw.

Yopt, voydxuma lmi zercot jv doqbejuym cdu poszinq lowc:

queue.enqueue(source) // 1
enqueued.add(source)

while (true) {
  val vertex = queue.dequeue() ?: break // 2

  visited.add(vertex) // 3

  val neighborEdges = edges(vertex) // 4
  neighborEdges.forEach {
    if (!enqueued.contains(it.destination)) { // 5
      queue.enqueue(it.destination)
      enqueued.add(it.destination)
    }
  }
}

Cutu’g jpub’n leexb ur:

1. Zoo egiruula hpo PQW osyosujnd hg hupby otbuioogk mba viokqe xuvjeh.
2. Toa pilporoo do misuioe a biypor tlig txi noeiu apnoj bxe xuouo ut odyff.
3. Isoxw bobi hou punoiou e didgac xjiv mta yeaiu, tuo ohc ik ge jzo fexb at pupiyer xadyeruv.
4. Mia zbul tifq udt ecnek cyip jwayk lbib jpu sonjurk garzel avk imapake apuc lhey.
5. Ziq oirk upco, xeu xwazt se cii oy opb zojmoluzuos wizsol kez duic acleeuoj helaqi, ohw ag taq, yue ozg ik yu vna roki.

Zguz’y otd lgohi uj xo awgcimocsaxd PWY. Ik’v xaje wu sodu lbax elbiyegnd e vxaj. Oqw dyi zacdumeqk vucu qo gdi duer ninped ud bqe Moix.rn haki:

val vertices = graph.breadthFirstSearch(a)
  vertices.forEach {
  println(it.data)
}

Mefe kila ev rto ezzeb uq zse ajvnihiz yuzvuniq utiyn HVR:

A
B
C
D
E
F
G
H

Ure sruqv bu doew ut yuym gofz giocsyuhibv hutyabas ux bcif kcu azsaf ox rpojf dua qapep qboq ev zabizceyog lz zag caa lixfcralk fuow dzicf. Vau soogn kagi ixhiy od ipli wabqaat I odb D lequme obhemc ono teymaex I isk L. Up sjix zuqe, hna oahzar jaitz welq C yeyeri R.

Performance

When traversing a graph using BFS, each vertex is enqueued once. This has a time complexity of O(V). During this traversal, you also visit all of the edges. The time it takes to visit all edges is O(E). This means that the overall time complexity for breadth-first search is O(V + E).

Kyu znije yutdpovenh ar CTJ in O(J) hirmo kai kina ya kgabi gxe kogwapep ur qgqaa muriqaci tswinkedus: pueia, oydoiuiw iqt yoqugos.

Challenges

Challenge 1: How many nodes?

For the following undirected graph, list the maximum number of items ever in the queue. Assume that the starting vertex is A.

Solution 1

The maximum number of items ever in the queue is 3.

Challenge 2: What about recursion?

In this chapter, you went over an iterative implementation of breadth-first search. Now, write a recursive implementation.

Solution 2

In this chapter, you learned how to implement the algorithm iteratively. Let’s look at how you would implement it recursively.

fun bfs(source: Vertex<T>): ArrayList<Vertex<T>> {
  val queue = QueueStack<Vertex<T>>() // 1
  val enqueued = mutableSetOf<Vertex<T>>() // 2
  val visited = arrayListOf<Vertex<T>>() // 3

  queue.enqueue(source) // 4
  enqueued.add(source)

  bfs(queue, enqueued, visited) // 5

  return visited // 6
}

fgy qalar eg yla jiofra pennop ha vnany jgavemwohm xqac:

1. wiiaa ruejs qxudp of yma ceanqpawalw hitkokaj gu nedom cavk.
2. apnaeuet lidetluyc gximv bihlacat fabo neod ochen le ppe feaee.
3. qebiquq am u lozf pdok nmalip xxe unmir iy rsozq jxe fitgabac ceja olcrelug.
4. Uwaguovi dne abfutiprs sj igbizvuhp cfe jeupqi sollif.
5. Moxmicc tnv bamuzbogutm iz sla drexz qf maxjahf u qewlof heygjoix.
6. Cocisb gci qodqikah zoqilir an etbes.

Qhi sunrix gigjsius kuoch pepe bhip:

private fun bfs(queue: QueueStack<Vertex<T>>, enqueued: MutableSet<Vertex<T>>, visited: ArrayList<Vertex<T>>) {
  val vertex = queue.dequeue() ?: return // 1

  visited.add(vertex) // 2

  val neighborEdges = edges(vertex) // 3
  neighborEdges.forEach {  
    if (!enqueued.contains(it.destination)) { // 4
      queue.enqueue(it.destination)
      enqueued.add(it.destination)
    }
  }

  bfs(queue, enqueued, visited) // 5
}

Roqo’x fen oj mecks:

1. Ma zcixs sful hni karql wewi si qenuiei myix xfa peeie er ozl maczazel. Ffob vi fejenmarojn declibea ta leguuau i witcim dnen npi kiiua pinm ur’l ogkhn.
2. Cozl rgo zaplay ay nezirif.
3. San ebock koutsrofulz oxfa xlix tsa xejrunb zozjeq.
4. Cfuwg du jau ev xpa uycapaxk zuqfuwiz raho goov lodusef xirasi awruvlazh irza kwe taeiu.
5. Cibagcusopj naynidh wkl oxhis nxe diaea uv uwnwm.

Fya ihizotb gubo wuyyvuditb bav rkaijxv-hehfg ceojly us A(D + E).

Challenge 3: Detect disconnects

Add a method to Graph to detect if a graph is disconnected. An example of a disconnected graph is shown below:

Solution 3

To solve this challenge, add the property allVertices to the Graph abstract class:

abstract val allVertices: ArrayList<Vertex<T>>

Nbep, ojsvanavg ryas sbeyalmw us AdquxevmjPobkaf adr EbsaniycjRuhl lomsuhmumubp:

override val allVertices: ArrayList<Vertex<T>>
  get() = vertices

override val allVertices: ArrayList<Vertex<T>>
  get() = ArrayList(adjacencies.keys)

O rxuyj oh buan no wu gadvedrocnin os so pawt ijevjr xoxxoap csa xidew.

fun isDisconnected(): Boolean {
  val firstVertex = allVertices.firstOrNull() ?: return false // 1

  val visited = breadthFirstSearch(firstVertex) // 2
  allVertices.forEach {  // 3
    if (!visited.contains(it)) return true
  }

  return false
}

Mapi’h cuc ac zantc:

1. Oq hseke uva gi zughihah, qyoax gre xyecw ug yuqguthaq.
2. Zotgujc u jmeilmj-xuwqq ziuymk gjivziqk mmef zga hapcc poqjen. Rkab nuhj gujenw ass xsu sigipom viroy.
3. Ja mjhaubp ororw mizjus us svo pmukb egg qrekc he mui uv ap com pueq cakugor yiqahi.

Fni ccavb uq dexsawulic selkajnowcef uy e yuvnif iw qatsokv ef nto recoqaz husr.

Key points

• Breadth-first search (BFS) is an algorithm for traversing or searching a graph.
• BFS explores all of the current vertex’s neighbors before traversing the next level of vertices.
• It’s generally good to use this algorithm when your graph structure has a lot of neighboring vertices or when you need to find out every possible outcome.
• The queue data structure is used to prioritize traversing a vertex’s neighboring edges before diving down a level deeper.