Questions (due 2/14, 10:30am)

Once you have completed the readings, answer the following questions:

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

   A. Connected?

   B. Acyclic?

   C. Directed?

   D. Simple?

   E. Weighted?

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

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

4. 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?

Submission

To submit your reading assignment, you must upload a text/PDF file onto Canvas prior to class