Comment on page
- 1.Suppose we want to find the vertex with minimal degree (fewest neighbors). Is an adjacency matrix or adjacency list better?
- 1.For the graph above, write the representation for the adjacency matrix representation.
- 2.Repeat (1) for the list of edges representation.
- 3.Repeat (1) for the adjacency list representation.
- 4.Run BFS starting from A for the graph above, and list the order in which vertices are visited. Break ties alphabetically.
- 5.Run DFS starting from A for the graph above, and list the postorder/postorder traversals. Break ties alphabetically.
- 1.Suppose we find some shortest path from
busing BFS. Consider a vertex
cthat is on the path between
b. What can we say about the shortest path from
Call the original shortest path from
, and the path from
balong this path
. If there is some shorter path between
, then we could simply take the path from
cin the original
, then take
to find an even shorter path between
However, we stated earlier that
is the shortest path between
b. This is a contradiction.
Thus, the shortest path between
bmust be on the shortest path between