Graph
Vertices joined by edges. The model for networks, maps and dependencies.
BFS and DFS: Breadth-first from 0
Breadth-first search from 0. A queue holds the frontier. Take the vertex that has waited longest, look at its neighbours, and enqueue the ones never seen before with their distance. Because of the queue, vertices come out in order of distance from the start.
Cost
- Add vertex
- O(1)
- Add edge
- O(1)
- Neighbours
- O(deg)
- Space
- O(V + E)
Leads to
Topics that need this one first.
Taught by the same lesson
BFS and DFS covers these too, in the same run.