> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/23.-graph-traversals-and-implementations/23.4-exercises.md).

# 23.4 Exercises

## Factual

1. Suppose we want to find the vertex with minimal degree (fewest neighbors). Is an adjacency matrix or adjacency list better?

<details>

<summary>Problem 1</summary>

An adjacency list would be better: we can just assess the size of each list in constant time versus iterating over all $$V$$ vertices in each row of the adjacency matrix to count the number of neighbors.

</details>

## Procedural

![](/files/51ySBEXhF5aSjuSumVTT)

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.

<details>

<summary>Problem 1</summary>

<pre><code><strong>    A  B  C  D  E  F
</strong><strong>   
</strong><strong>A   F  T  F  F  F  F
</strong><strong>B   T  F  T  T  T  F
</strong><strong>C   F  T  F  F  F  T
</strong><strong>D   F  T  F  F  F  T
</strong><strong>E   F  T  F  F  F  F
</strong><strong>F   F  F  T  T  F  F
</strong></code></pre>

</details>

<details>

<summary>Problem 2</summary>

```
[{A, B}, 
{B, A}, {B, C}, {B, D}, {B, E}, 
{C, B}, {C, F},
{D, B}, {D, F},
{E, B}, 
{F, C}, {F, D}]
```

</details>

<details>

<summary>Problem 3</summary>

```
A: [B]
B: [A, C, D, E]
C: [B, F]
D: [B, F]
E: [B]
F: [C, D]
```

</details>

<details>

<summary>Problem 4</summary>

`[A, B, C, D, E, F]`

</details>

<details>

<summary>Problem 5</summary>

preorder: `[A, B, C, F, D, E]`

postorder: `[D, F, C, E, B, A]`

</details>

## Metacognitive

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. Problem 4c from the [Spring 2015 Midterm 2](https://drive.google.com/file/d/1uE1QlF4YguWVp8m8UJ97R2xPC4b1NnQ5/view?usp=sharing).

<details>

<summary>Problem 1</summary>

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`.&#x20;

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`.

</details>

<details>

<summary>Problem 2</summary>

[Solutions](https://drive.google.com/file/d/1IYt4VbzdX4dTekh6cYAC8tigpJ_LgljV/view?usp=sharing) are linked here and on the course website.

</details>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook/23.-graph-traversals-and-implementations/23.4-exercises.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.