Reading 09: Graph Representation, Traversal

Readings

The readings for Monday, November 7 are:

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:

Data Structures & Algorithm Analysis
- 11.1 - 11.3
Open Data Structures
- 12. Graphs
Algorithms
- 4.1 Undirected Graphs

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:

Briefly explain what it means for a graph to be:

A. Connected?

B. Acyclic?

C. Directed?

D. Simple?

E. Weighted?
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?
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