ch5ex14

README

= Exercise 5.14
// Refs:
:url-base: https://github.com/fenegroni/TGPL-exercise-solutions
:workflow: workflows/Exercise 5.14
:action: actions/workflows/ch5ex14.yml
:url-workflow: {url-base}/{workflow}
:url-action: {url-base}/{action}
:badge-exercise: image:{url-workflow}/badge.svg?branch=main[link={url-action}]

{badge-exercise}

Use the `breadthFirst` function to explore a different structure. For example,
you could use the course dependencies from the `topoSort` example (a directed graph), the file
system hierarchy on your computer (a tree), or a list of bus or subway routes downloaded from
your city government's web site (un undirected graph).

== Example

`BreadthFirst` encapsulates the essence of a breadth-first traversal.
The caller provides an initial list `worklist` of items to visit
and a function value `f` to call for each item.
Each item is identified by a string.
The function `f` returns a list of new items to append to `worklist`.
The `BreadthFirst` function returns when all items have been visited.
It maintains a set of strings to ensure that no item is visited twice.

We provide the Example function `TestBreadthFirst` that prints the course dependencies
from the `topoSort` example.

Documentation

Index

• func BreadthFirst(f func(string) []string, worklist []string)

Examples

• BreadthFirst

Functions

func BreadthFirst

func BreadthFirst(f func(string) []string, worklist []string)

BreadthFirst calls f for each item in the worklist. Any items returned by f are added to the worklist. f is called at most once for each item.

Example

// prereqs maps computer science courses to their prerequisites.
var prereqs = map[string][]string{
	"algorithms":            {"data structures"},
	"calculus":              {"linear algebra"},
	"compilers":             {"data structures", "formal languages", "computer organisation"},
	"data structures":       {"discrete math"},
	"databases":             {"data structures"},
	"discrete math":         {"intro to programming"},
	"formal languages":      {"discrete math"},
	"networks":              {"operating systems"},
	"operating systems":     {"data structures", "computer organisation"},
	"programming languages": {"data structures", "computer organisation"},
}
visit := func(s string) []string {
	fmt.Println(s)
	return prereqs[s]
}
var courses []string
for k := range prereqs {
	courses = append(courses, k)
}
sort.Strings(courses)
BreadthFirst(visit, courses)

Output:

algorithms
calculus
compilers
data structures
databases
discrete math
formal languages
networks
operating systems
programming languages
linear algebra
computer organisation
intro to programming