23.4 Exercises
Factual
Suppose we want to find the vertex with minimal degree (fewest neighbors). Is an adjacency matrix or adjacency list better?
Procedural
For the graph above, write the representation for the adjacency matrix representation.
Repeat (1) for the list of edges representation.
Repeat (1) for the adjacency list representation.
Run BFS starting from A for the graph above, and list the order in which vertices are visited. Break ties alphabetically.
Run DFS starting from A for the graph above, and list the postorder/postorder traversals. Break ties alphabetically.
Metacognitive
Suppose we find some shortest path from
a
tob
using BFS. Consider a vertexc
that is on the path betweena
andb
. What can we say about the shortest path fromc
tob
?Problem 4c from the Spring 2015 Midterm 2.
Last updated