Click here to Skip to main content
14,920,001 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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];
    
        // To store the number of connected components
        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; // already visited this node
      }
    
      searchTree[v] = parent;
    
      for (auto iter = graph.neighbours(v); iter != graph.endIterator(v); iter++) {
    
          depthFirstSearch(graph, *iter, v, searchTree); // recursive call
      }
    }
      // for (i = adj[v].begin(); i != adj[v].end(); ++i)
      //   if (!visited[*i])
      // 	DFSUtil(*i, visited);
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.
Posted
Updated 19-Mar-21 2:36am
Comments
Rick York 15-Mar-21 23:19pm
   
You might find some hints on this page : https://www.codeproject.com/Questions/396593/i-need-code-in-Undirected-Graphs-that-allow-me-to

1 solution

By connected components, I assume you mean the number of disjoint subgraphs. If so, I would use an edge deletion algorithm. Put each vertex in a separate set and then iterate over the edges. For each edge, combine the two sets that contain the two vertices in the edge, and then delete the edge. When no edges remain, the number of non-empty sets is the number of disjoint subgraphs.
   
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900