This lesson contains approximately 20 minutes of video content.

### Implementing the algorithm

#### Activity: Determining the number of connected components in a graph

Activity Prompt:

In this question, you will be working with the undirected `TrivialGraph` implemented using an adjacency list. Your job is to determine the number of connected components in a `TrivialGraph` object's `graph_`.

In the Graph lessons, we introduced connected and not connected (i.e., disconnected) graphs.

 A graph is connected if there is a path from every vertex to every other vertex in the graph A graph that is disconnected consists of a set of connected components

In the case of the connected graph, we see one connected component of nodes. In the case of the not connected graph, you can see two connected components.

In graph theory, a connected component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The connected components of any graph partition its vertices into disjoint sets and are the induced subgraphs of those sets. A graph that is itself connected has exactly one connected component consisting of the whole graph. (Wikipedia)

In this problem, you will implement a `NoConnectedComponents()`, a member function of `TrivialGraph` that returns the number of connected components in a `TrivialGraph` object's `graph_`.

How might you solve this problem? Consider how breath-first search allows you to explore pathways throughout a graph. When you invoke the algorithm, you must track the vertices you've visited. How can you identify the number of connected components in a graph? Consider what happens when you run the "traversal" from some node. During the traversal, you mark the nodes you've visited. At the end of the "traversal", you've explored one connected component and marked all the vertices in that component as visited. Could you somehow call the "traversal" again from a node you haven't visited yet? Can you count the number of times this "traversal" is invoked until all vertices are marked as visited? If so, you've determined the number of connected components in the graph.

##### Data members
 `std::map> graph_;` We will encode the graph naively with an `std::map>`. The map's key values for our application will be vertices represented as an `std::string`. Each "vertex" will map to its adjacency list encoded as an `std::list`. * The astute student may notice some inefficiencies in storage with this representation. I'll acknowledge that now and note that we're going for accessibility of graph concepts and not the performance in this activity.
##### Provided member functions
###### public:
 `TrivialGraph()` We will use the default, compiler-generated definition of the default constructor. `void AddVertex(const std::string& vertex);` This function inserts `vertex` into `graph_`. We implement this behavior by inserting the key `vertex` to `graph_` and mapping that key to an empty `std::list`. `void AddEdge(const std::string& v1, const std::string& v2)` Adds an undirected edge between `v1` and `v2` to the `graph_`. If `v1` or `v2` is not in the graph (can check with `VertexInGraph`), throw an exception.
###### private:
 `std::vector GetVertices() const;` Returns a `std::vector` of the vertices in `graph_`. `bool VertexInGraph(const std::string vertex);` This function returns true if `vertex` is a vertex in the graph, i.e., `vertex` is a key in `graph_`. `std::list& GetAdjacencyList(const std::string& vertex)` This function returns the adjacency list for `vertex`. An exception is thrown if `vertex` does not exist as a key in the `graph_`.
##### Public member functions you are to implement
 `unsigned int NoConnectedComponents();` Returns the number of connected components in the `graph_`.

We will only transmit the contents of your `trivial_graph.hpp` and `trivial_graph.cc` to the grader. Let's get started!