Lesson 8.1
Representation
An adjacency list uses space proportional to vertices plus edges; an adjacency matrix uses the square of the vertices regardless of how few edges exist.
Lessons and exercises
The most general structure in the course, and the one where the choice of representation changes the complexity of everything built on top of it.
Lesson 8.2
Breadth-First Search
BFS uses a queue and expands in layers, so the first time it reaches a vertex it has used the fewest edges. That is why it solves unweighted shortest paths.
Lesson 8.3
Depth-First Search
DFS uses a stack, explicitly or through recursion, and goes deep before backtracking. It underpins cycle detection and topological ordering.
Lesson 8.4
Shortest Paths and Spanning Trees
Dijkstra settles vertices in increasing distance and therefore cannot tolerate negative edges. Kruskal and Prim build minimum spanning trees by different strategies.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic