## Readings

The readings for Monday, November 7 are:

1. Data Structures and Other Objects Using C++:

• 15.1 - 15.3

### Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

#### TL;DR

The focus of the reading is graphs, specifically adjacency list and adjacency matrix representation, and depth-first search and breadth-first search traversal.

## Questions

Once you have completed the readings, answer the following questions in the `reading09/README.md` file in your assignments repository:

1. Briefly explain what it means for a graph to be:

A. Connected?

B. Acyclic?

C. Directed?

D. Simple?

E. Weighted?

2. Given the following graphs:

A. Provide the adjacency matrix and the adjacency list for each graph. For instance, `Graph 0` would have the following adjacency matrix and adjacency list:

```Graph 0 - Adjacency Matrix            Graph 0 - Adjacency List

A B C
A: 0 1 1                                A: B C
B: 0 0 0                                B:
C: 0 1 0                                C: B
```

B. What is a reason for using an adjacency matrix instead of an adjacency list to represent a graph?

C. Conversely, what is a reason for using an adjacency list instead of an adjacency matrix to represent a graph?

3. Given the following non-recursive implementation of depth-first search:

```struct Graph {
map<string, set<string>> adj; // Adjacency List/Set
};

void traversal(Graph &g, const string &s) {
stack<string> q;
set<string>   v;

// TODO

while (!q.empty()) {
// TODO
}
}
```

A. Complete the implementation of depth-first search by filling in the `TODO` sections with the appropriate C++ code. Remember to:

• Print out each node you visit.

• Visit each node exactly once.

B. What is the purpose of `stack<string> q`?

C. What is the purpose of `set<string> v`?

D. What would we need to change in the function to perform a breadth-first search instead of depth-first search?

## Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 09 - TA assignment list.

#### Development Branch

To facility the Merge Request workflow, you must do your development in its own branch:

```\$ cd path/to/repo                 # Go to your repository
\$ git checkout master             # Make sure we are on master branch first
\$ git pull                        # Make sure we have changes from GitLab
\$ git checkout -b reading09       # Create reading09 branch
...                               # Do your work
\$ git commit                      # Commit your work (can do this multiple times)
\$ git push -u origin reading09    # Push branch to GitLab
```