Breadthfirst search
Motivation
Breadthfirst search
Finding the shortest path
Implementing the algorithm
Activity: Determining the number of connected components in a graph
Graded Playground Autograder
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 breathfirst 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<std::string, std::list<std::string>> graph_; 
We will encode the graph naively with an std::map<std::string, std::list<std::string>> . 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<std::string> . * 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, compilergenerated 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<std::string> .

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<std::string> GetVertices() const; 
Returns a std::vector<std::string> 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<std::string>& 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!