Comment on page
23.4 Exercises
- 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
a
tob
using BFS. Consider a vertexc
that is on the path betweena
andb
. What can we say about the shortest path fromc
tob
? - 2.
Call the original shortest path from
a
to b
, and the path from
c
to b
along this path . If there is some shorter path between
c
and b
, then we could simply take the path from
a
to c
in the original , then take
to find an even shorter path between
a
and b
. However, we stated earlier that
is the shortest path between
a
and b
. This is a contradiction.Thus, the shortest path between
c
and b
must be on the shortest path between a
and b
.Last modified 8mo ago