I have to build a function that returns an integer which is the number of
connected components in the graph.
What I have tried:
I've implemented code to create the graph when adding edges or vertices.
using namespace std;
void Digraph::addVertex(int v) {
//adds v with an empty adjacency set.
nbrs[v];
}
void Digraph::addEdge(int u, int v) {
addVertex(v);
nbrs[u].insert(v);
}
bool Digraph::isVertex(int v) {
return nbrs.find(v) != nbrs.end();
}
bool Digraph::isEdge(int u, int v) {
return nbrs.find(u) != nbrs.end() && nbrs[u].find(v) != nbrs[u].end();
}
unordered_set<int>::const_iterator Digraph::neighbours(int v) const {
return nbrs.find(v)->second.begin();
}
unordered_set<int>::const_iterator Digraph::endIterator(int v) const {
return nbrs.find(v)->second.end();
}
int Digraph::numNeighbours(int v) {
return nbrs.find(v)->second.size();
}
int Digraph::size() {
return nbrs.size();
}
vector<int> Digraph::vertices() {
vector<int> v;
for (unordered_map<int, unordered_set<int>>::const_iterator it = nbrs.begin();
it != nbrs.end(); it++) {
v.push_back(it->first);
}
return v;
}
bool Digraph::isWalk(vector<int> walk) {
if (walk.size() == 0)
return false;
if (walk.size() == 1)
return isVertex(walk[0]);
for (vector<int>::size_type i=0; i<walk.size()-1; i++)
if (!isEdge(walk[i], walk[i+1]))
return false;
return true;
}
bool Digraph::isPath(vector<int> path) {
set<int> s(path.begin(), path.end());
if (s.size() < path.size())
return false;
return isWalk(path);
}
I've started implementing code to find the connected components. I've decided to use DFS(depth first search for my solution). I'm able to implement this alone using list but I can't figure out how to implement it using an instance of this digraph class. So, far I've done this:
#include "digraph.h"
#include <iostream>
#include <vector>
using namespace std;
int count_components(Digraph& graph){
bool* visited = new bool[V];
int count = 0;
for (int v = 0; v < V; v++)
visited[v] = false;
for (int v = 0; v < V; v++) {
if (visited[v] == false) {
DFSUtil(v, visited);
count += 1;
}
}
return count;
}
void depthFirstSearch(const Digraph& graph, int v, int parent, unordered_map<int, int>& searchTree) {
if (searchTree.find(v) != searchTree.end()) {
return;
}
searchTree[v] = parent;
for (auto iter = graph.neighbours(v); iter != graph.endIterator(v); iter++) {
depthFirstSearch(graph, *iter, v, searchTree);
}
}
How do I implement my code to work with my graph class?
sample main driver code:
Digraph graph;
int nodes[] = {1, 2, 3, 4, 5, 6};
for (auto v : nodes)
graph.addVertex(v);
graph.addEdge(1, 2);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
cout << count_components(graph) << endl;
Output should be 3 in this case.