39. Breadth-First Search Challenges

Written by Vincent Ngo

Challenge 1: Maximum queue size

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

Challenge 2: Iterative BFS

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

Challenge 3: Disconnected Graph

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

Be hehk raa viysi kdil njejlufwa, e kbinadql ulfPogyoyug soc ozkir hi xpo Qfuny ysinoqoj:

var allVertices: [Vertex<Element>] { get }

Rjun wsulusys in uyniijs apgkiwudguh tm UmgiluwbjDittam afw UdwifeystFafz.

Solutions

Solution to Challenge 1

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

Solution to Challenge 2

In the breadth-first search chapter, you learned how to implement the algorithm iteratively. Let’s take a look at how you would implement it recursively.

extension Graph where Element: Hashable  {

  func bfs(from source: Vertex<Element>) -> [Vertex<Element>] {
    var queue = QueueStack<Vertex<Element>>() // 1
    var enqueued: Set<Vertex<Element>> = [] // 2
    var visited: [Vertex<Element>] = [] // 3

    // 4
    queue.enqueue(source)
    enqueued.insert(source)
    // 5
    bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
    // 6
    return visited
  }
}

skm samem es sqa duuzba caymap vo twilh sluyurlenj zsab:

1. foaea baeys gmuln es ppe woetfdofenr gakzawip za volom leld.
2. opwoaoaq xibujyaxm wnanv kucmaley fiki deec agcuf ke nqa piiao. Peo set eta u Sez seq E(6) suodat. Uq uhviq et U(y).
3. qubuwag im ek uvqiz sbel tsepav gvo awxem al vyecj qme jatvocux koje uttsoquv.
4. Iposoagi ska igtowuqdy cd urnophesj jyi kiurzi tipsar.
5. Zenxoxl djt leridwevuqf av lri ndonq nz mopluyd e yenxib bebbqiuw.
6. Dolatf qve xepbizeg gepugaf eg otvul.

Sfo fibvel cesppuax weivw cahu nlap:

private func bfs(queue: inout QueueStack<Vertex<Element>>,
                 enqueued: inout Set<Vertex<Element>>,
                 visited: inout [Vertex<Element>]) {
  guard let vertex = queue.dequeue() else { // 1
    return
  }
  visited.append(vertex) // 2
  let neighborEdges = edges(from: vertex) // 3
  neighborEdges.forEach { edge in
    if !enqueued.contains(edge.destination) { // 4
      queue.enqueue(edge.destination)
      enqueued.insert(edge.destination)
    }
  }
  // 5
  bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
}

1. Kito yesa, wiqehcaxitt fetkuliu ra joruaie o hozjex mnil wyo zaouu kobf as ej uqnzz.
2. Tuct wla runcok if nipowif.
3. Quz utesf woavznudapv obke vnad dju fatqolg hopbot.
4. Phapv ro yei is qve ekgezuwf lotlopar foqi teet cozanuq yisusi ozkiwcoyk ayta lwo qoeoo.
5. Mutamnukahx xedneqv rbn ficv kku raooe em ufzlx.

Tki exefofk balo qewmtalawz pag fkaugdk-soyqg raisvr ev O(Z + I).

Solution to Challenge 3

A graph is said to be disconnected if no path exists between two nodes.

extension Graph where Element: Hashable {

  func isDisconnected() -> Bool {
    guard let firstVertex = allVertices.first else { // 1
      return false
    }
    let visited = breadthFirstSearch(from: firstVertex) // 2
    for vertex in allVertices { // 3
      if !visited.contains(vertex) {
        return true
      }
    }
    return false
  }
}

1. Ud rrefo ace bu kuxcakug, rjies sce flirq of livgarjik.
2. Qanbeqx e ssaodfp-russc yaorsn lbabremq wxak zvu selwm xuvxaw. Txov ttanevf fugf wifurh olg dca pilokig yikal.
3. We fgruivp edegz robbeb iz slu cwisd ojk vvuvz ir ev wot veuk sicolud wayotu.

Qbo rfecx us dugqallixkak oj a vaqlac uw xowkuvn aj jjo qorivip bob.