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`

to`b`

using BFS. Consider a vertex`c`

that is on the path between`a`

and`b`

. What can we say about the shortest path from`c`

to`b`

? - 2.

Call the original shortest path from

`a`

to `b`

$p_{ab}$

, and the path from `c`

to `b`

along this path $p^{*}_{cb}$

. If there is some shorter path between `c`

and `b`

$p'_{cb}$

, then we could simply take the path from `a`

to `c`

in the original $p_{ab}$

, then take $p'_{cb}$

to find an even shorter path between `a`

and `b`

. However, we stated earlier that

$p_{ab}$

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