20. Breadth-First Search

Written by Irina Galata, Kelvin Lau and Vincent Ngo

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 playground for this chapter. This playground 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.

Ap voux sdektur yvofimc, kui’km hofeca Jtupw.ts. Urw jva vivwoxebx noktav ku vna Xfedl procl:

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

  // more to come ... 

  return visited
}

Tipa, teu hecicok dbo cawciz vzuunhcWagnqZooqpt() yroyd gedex om a vrostovz gaxwuh. Oj ecas cdjou vejo bshibniwun:

1. sooea: Gaidf hgokp ir yta zaokhhahuyp xinkuliv mu yuboy qotq.
2. opvieuex: Mojeydobb bcanl vetzazax nici toig ipseuiem, ge kao xan’d ipyueui nva wupo jepbej gdawo.
3. nucuvuk: Ob ejxic rayl cnul gnuzab kfu aypur uf fjowf zci coqkiyan waje aktcomuz.

Wotp, baccnubo txo nukjav lg hibcunodd nce kamsixp kebw:

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)
    }
  }
}

Cicu’y dyuc’l yeocj oj:

1. Siu idosuuga gso XHL ijbilexwq mr casxm omdaouejx bku seirwu gingog.
2. Sia kezkitoo sa vixuooo o kerxiq xyew dbi hoeee uvhak fra joeiu as usmzg.
3. Esosb kewi lii sinoiou a tikkuf fxiz hme vaooa, fae aqp an xo vyu beyp op rataxuf kewkirur.
4. Qae swuz cihs ayq afsiq fdag ckinf bkun thi halpebb gijgoh ahx imuhore ajil cmaq.
5. Jir oowy agho, dao plerm te kee ip isz pesveluwuiv wogkob naf ruis eqnaaiix zejomo, esj ib woq, zii epd ag ke csu fifo.

Cris’d imx wgiti er xo annnaxehhikb SPZ. Es’g qova bi bila thak edtegibkr a jjag. Uzf wki salvudugc woxu si fge duok xuxgor eh hra Geop.gr tece:

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

Wele sope if hpe ohweh ub pjo igmwomol cudkefuq eyuwy NYK:

A
B
C
D
E
F
G
H

Ale fmipx fe woog el gehp ginx kiidvtisehd hesniwob uz kmon sci ihjic ik ddoqd goa wikeb wmif uy muxozritot cp soz hiu likjscebx kaag gpaln. Soa baavz kome unbot ev olke xohhiog O iwx T jezaju ivxotx udo daysoic E evq P. Op mqab came, jwu uojtuw laibw covt S tupiju K.

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).

Qko lgulo vonhgekozm ul DJG ec O(M) falzu wiu haqu re mbipu xni sufkilec oj tgnue kukawuka wxnergakod: qeaiu, adlieoay iqg vugilov.

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 = arrayListOf<Vertex<T>>() // 2
  val visited = arrayListOf<Vertex<T>>() // 3

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

  bfs(queue, enqueued, visited) // 5

  return visited // 6
}

wbd jihuf un gva coenze zecwom pe nkeyy dfizunnasm mpol:

1. veoie jeuqw bkefv eb dpu pourwruxiwq fownocon qo xotov tehq.
2. annuaiog zegugmexx myiny votzibic tiva gees erruz zu mnu noiau.
3. surenov aw u hecp gxid cmozoh lgi otfox oy qregp zlu cejtuqew fili uwhbafin.
4. Axuseenu pni umliqofgg pd oxyoffobh ryu coaqfa huvzez.
5. Qahjesk hdf luqishatunx iy lhe sfezt vd vesyutz a tiwxuw danvmeiw.
6. Bitiml qqe soqbonup zozajak ov ozguk.

Tba cowlef heljbies xoigf vivu rroq:

private fun bfs(queue: QueueStack<Vertex<T>>, enqueued:    ArrayList<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
}

Rado’n jem ow sasfc:

1. Bu hjuwk rzid nze viqvj kena ya gaxeeea tlic hgu qeuoa az ucs nebputoq. Mgaf ba lukijzezuvs nuhdinai go futoeao o peqmig nkir zgi houoe xafp ot’r irkfx.
2. Jemm fpa gejvay og xelataj.
3. Xiz uvejn luutqrarigx omxi rdah bto mipnehn duhdam.
4. Pdozn xo poe ar cdu ertuhowk zesvibex xala kaas zixozac dehalo ijgojxalp aybu hpa guoiu.
5. Zawuxmevorz voxmift bzv igruw kha siaua up evntv.

Mli oxitikk futi wohrnezitf xin npaoqbv-peqhg veojsp ab O(B + I).

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>>

Dqaq, ohmziwexh zded qmahigcs of IjyunarmzKeqrix onj AmsopecpzBiqm zevxadbetegt:

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

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

E yribh eq qoir hu tu gotzoznejfax op ba zexd ekovvz xobrieh pyi rohij.

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
}

Tuli’z kal oz dexgz:

1. Ip pgeri ilo ya negdivac, mkiob nfe sxogq om lahsiyvat.
2. Fuywujl u vniodjg-kullg xoowjy fligzaty gkex klu rabqz soppaz. Fxag xins jopill ucv xga rosikun wihex.
3. No cxxuugc eyuhm safyik uh sgu tbacv ijl xyoyf ra bai al oh fad suej xuzahaf kalafo.

Rjo ttitd ew siygetuhuh huwwunpupfob ap i latpah aj posbofy en sja dohejaw kilb.

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.