Breadth-first search

This lesson contains approximately 20 minutes of video content.

Motivation

Breadth-first search

Finding the shortest path

Implementing the algorithm

Activity: Determining the number of connected components in a graph

Graded Playground Autograder

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<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, 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<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!

#include <iostream> #include "trivial_graph.hpp" int main() { // TrivialGraph graph; // graph.AddVertex("CS-128"); // graph.AddVertex("CS-124"); // graph.AddVertex("CS-225"); // graph.AddEdge("CS-124", "CS-128"); // graph.AddEdge("CS-128", "CS-225"); // std::cout << graph << std::endl; // std::cout << graph.NoConnectedComponents() << std::endl; }
#ifndef TRIVIAL_GRAPH_HPP #define TRIVIAL_GRAPH_HPP #include <iostream> #include <list> #include <map> #include <string> #include <vector> class TrivialGraph { public: // Functions to implement unsigned int NoConnectedComponents(); // Functions defined TrivialGraph() = default; void AddVertex(const std::string& vertex); void AddEdge(const std::string& v1, const std::string& v2); friend std::ostream& operator<<(std::ostream& os, const TrivialGraph& graph); private: bool VertexInGraph(const std::string vertex); std::vector<std::string> GetVertices() const; std::list<std::string>& GetAdjacencyList(const std::string& vertex); std::map<std::string, std::list<std::string>> graph_; }; std::ostream& operator<<(std::ostream& os, const TrivialGraph& graph); #endif
#include "trivial_graph.hpp" #include <iomanip> #include <stdexcept> #include <utility> void TrivialGraph::AddVertex(const std::string& vertex) { if (VertexInGraph(vertex)) throw std::runtime_error("vertex already in graph."); graph_.insert({vertex, std::list<std::string>()}); } void TrivialGraph::AddEdge(const std::string& v1, const std::string& v2) { if (!VertexInGraph(v1) || !VertexInGraph(v2)) throw std::runtime_error("vertex not in graph."); auto& v1_adj = GetAdjacencyList(v1); auto& v2_adj = GetAdjacencyList(v2); v1_adj.push_back(v2); v2_adj.push_back(v1); } std::vector<std::string> TrivialGraph::GetVertices() const { std::vector<std::string> verticies; for (auto const& entry : graph_) verticies.push_back(entry.first); return verticies; } std::list<std::string>& TrivialGraph::GetAdjacencyList( const std::string& vertex) { return graph_.find(vertex)->second; } bool TrivialGraph::VertexInGraph(const std::string vertex) { return graph_.contains(vertex); } std::ostream& operator<<(std::ostream& os, const TrivialGraph& graph) { os << "Contents:" << std::endl; for (const auto& pair : graph.graph_) { os << " " << std::setw(15) << pair.first << ": ["; int i = pair.second.size() - 1; for (const auto& list_entry : pair.second) { os << list_entry; if (i != 0) os << ", "; i -= 1; } os << "]" << std::endl; } return os; }