Introduction To Program Design Lecture 25

What It Means

Breadth-first search, or BFS, explores all nodes one edge away before nodes two edges away. A worklist queue stores nodes discovered but not yet processed.

Removing from the front and adding neighbors to the back creates first-in, first-out order.

Read, Run, and Change

Predict the output, then select Run code. Edit the example and run it again to test your prediction. Reset restores the original program. Each example runs independently.

Try itChange the neighbor order at North and predict the breadth-first visit order.

Run codeResetEditable Kotlin

1

fun main() {

2

    val north = Station("North", mutableListOf())

3

    val central = Station("Central", mutableListOf())

4

    val south = Station("South", mutableListOf())

5

    val east = Station("East", mutableListOf())

6

    val stations: TransitGraph = mutableSetOf(north, central, south, east)

7

    val start = north

8

    north.next.addAll(listOf(central, east))

9

    central.next.add(south)

10

    south.next.add(north) // A cycle back to the start.

11

​

12

    val queue = mutableListOf(start)

13

    val visited = mutableSetOf<String>()

14

​

15

    while (queue.isNotEmpty()) {

16

        val current = queue.removeAt(0)

17

        if (visited.add(current.name)) {

18

            queue.addAll(current.next)

19

        }

20

    }

21

​

22

    println(visited)

23

}

Supporting code included with this example

These definitions are loaded automatically each time you run. The editable program above supplies this example's inputs.

Station.kt
// A station has its own identity. Connections may change or form cycles.
// Ordinary classes keep set membership independent of mutable connections.
class Station(val name: String, val next: MutableList<Station>)
typealias TransitGraph = MutableSet<Station>

Check the original program's output

[North, Central, East, South]

Each new node enters the back of the queue. The visited check prevents its neighbors from being enqueued repeatedly after processing.

Notice: A queue is about processing order; the visited set is about avoiding repeated processing.

Supplementary and External Resources

Practice

  1. Where are new neighbors added?

  2. Which node is removed next?

  3. What prevents cycles from repeating forever?

What It Means

A reachability function returns only true or false. A path function must additionally remember which nodes led to the destination. An accumulator can carry the path so far.

Visited tracking remains necessary because a path-building search can encounter cycles too.

Read, Run, and Change

Predict the output, then select Run code. Edit the example and run it again to test your prediction. Reset restores the original program. Each example runs independently.

Try itChange the target. Use a fresh visited set for each independent search.

Run codeResetEditable Kotlin

1

fun pathFrom(

2

    current: Station,

3

    target: String,

4

    path: List<String>,

5

    visited: MutableSet<String>

6

        ): List<String> {

7

    if (current.name == target) return path + current.name

8

    if (!visited.add(current.name)) return emptyList()

9

    return current.next.fold(emptyList<String>()) { found, neighbor ->

10

        if (found.isNotEmpty()) found

11

        else pathFrom(neighbor, target, path + current.name, visited)

12

    }

13

}

14

​

15

fun main() {

16

    val north = Station("North", mutableListOf())

17

    val central = Station("Central", mutableListOf())

18

    val south = Station("South", mutableListOf())

19

    val east = Station("East", mutableListOf())

20

    val stations: TransitGraph = mutableSetOf(north, central, south, east)

21

    val start = north

22

    north.next.addAll(listOf(central, east))

23

    central.next.add(south)

24

    south.next.add(north) // A cycle back to the start.

25

    println(pathFrom(start, "South", emptyList(), mutableSetOf()))

26

    println(pathFrom(start, "West", emptyList(), mutableSetOf()))

27

}

Supporting code included with this example

These definitions are loaded automatically each time you run. The editable program above supplies this example's inputs.

Station.kt
// A station has its own identity. Connections may change or form cycles.
// Ordinary classes keep set membership independent of mutable connections.
class Station(val name: String, val next: MutableList<Station>)
typealias TransitGraph = MutableSet<Station>

Check the original program's output

[North, Central, South]
[]

The successful result includes each station in route order. An empty list represents failure for a branch.

Notice: Avoid sharing one mutable path list across branches unless backtracking is handled carefully.

Supplementary and External Resources

Practice

  1. What represents failure?

  2. When is the current name added?

  3. What prevents following a cycle?

What It Means

DFS uses recursion or a stack-like worklist and explores depth first. BFS uses a queue and explores by distance from the start.

If every edge has equal cost, the first path found by BFS uses the fewest edges. DFS may find a path quickly but not necessarily a shortest one.

Read, Run, and Change

Predict the output, then select Run code. Edit the example and run it again to test your prediction. Reset restores the original program. Each example runs independently.

Try itTrace the two orders, then change the graph and compare them again.

Run codeResetEditable Kotlin

1

fun depthFirst(start: Station): List<String> {

2

    val visited = mutableSetOf<String>()

3

    fun visit(current: Station) {

4

        if (!visited.add(current.name)) return

5

        for (neighbor in current.next) visit(neighbor)

6

    }

7

    visit(start)

8

    return visited.toList()

9

}

10

​

11

fun breadthFirst(start: Station): List<String> {

12

    val visited = mutableSetOf<String>()

13

    val queue = mutableListOf(start)

14

    while (queue.isNotEmpty()) {

15

        val current = queue.removeAt(0)

16

        if (visited.add(current.name)) queue.addAll(current.next)

17

    }

18

    return visited.toList()

19

}

20

​

21

fun main() {

22

    val north = Station("North", mutableListOf())

23

    val central = Station("Central", mutableListOf())

24

    val south = Station("South", mutableListOf())

25

    val east = Station("East", mutableListOf())

26

    val stations: TransitGraph = mutableSetOf(north, central, south, east)

27

    val start = north

28

    north.next.addAll(listOf(central, east))

29

    central.next.add(south)

30

    south.next.add(north) // A cycle back to the start.

31

    println(depthFirst(start))

32

    println(breadthFirst(start))

33

}

Supporting code included with this example

These definitions are loaded automatically each time you run. The editable program above supplies this example's inputs.

Station.kt
// A station has its own identity. Connections may change or form cycles.
// Ordinary classes keep set membership independent of mutable connections.
class Station(val name: String, val next: MutableList<Station>)
typealias TransitGraph = MutableSet<Station>

Check the original program's output

[North, Central, South, East]
[North, Central, East, South]

Both strategies still need visited tracking in a graph with cycles.

Notice: Traversal order matters when the problem asks for a particular path, not only whether any path exists.

Supplementary and External Resources

Practice

  1. Which strategy finds a fewest-edge path in an unweighted graph?

  2. Which strategy follows one route deeply first?

  3. Do both need visited tracking?

What It Means

Many systems are about relationships rather than simple sequences: cities connect by roads, courses connect by prerequisites, web pages connect by links, and people connect through friendships. A graph records those connections.

Graph search appears in maps, recommendation systems, build tools, network routing, and games. It lets a program ask whether one thing can reach another, find a route, or discover what depends on a change.

Read This Example

A model to think with

Course prerequisites
Programming I -> Data Structures
Data Structures -> Algorithms
Algorithms -> Machine Learning

A planning tool can follow the connections to explain which courses must come first. It can also detect a cycle if two requirements accidentally depend on each other.

Notice: Connections can lead back to places already visited, so a search needs a way to remember what it has already explored.

Supplementary and External Resources

Practice

  1. Why are course prerequisites a graph?

  2. What could a routing program ask about a road network?

  3. Why remember visited places?