connected_components.cpp File Reference

[Graph Connected Components (Connected Components)] (https://en.wikipedia.org/wiki/Component_(graph_theory)) More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for connected_components.cpp:

Namespaces
namespace	graph
	Graph Algorithms.

Functions
void	graph::addEdge (std::vector< std::vector< int > > *adj, int u, int v)
	Function that add edge between two nodes or vertices of graph. More...
void	graph::explore (const std::vector< std::vector< int > > *adj, int u, std::vector< bool > *visited)
	Utility function for depth first seach algorithm this function explores the vertex which is passed into. More...
int	graph::getConnectedComponents (const std::vector< std::vector< int > > *adj)
	Function that perfoms depth first search algorithm on graph and calculated the number of connected components. More...
void	tests ()
int	main ()

Detailed Description

[Graph Connected Components (Connected Components)] (https://en.wikipedia.org/wiki/Component_(graph_theory))

Author

Ayaan Khan

A graph is a collection of nodes also called vertices and these vertices are connected by edges. A connected component in a graph refers to a set of vertices which are reachable form one another.

Example - Here is graph with 3 connected components

     1   4           5               8
    / \ /           / \             / \
   2---3           6   7           9   10

   first          second           third
   component      component        component

Function Documentation

main()

int main

(

void

)

Main function

running predefined tests

           {
    /// running predefined tests
    tests();
 
    int vertices = int(), edges = int();
    std::cout << "Enter the number of vertices : ";
    std::cin >> vertices;
    std::cout << "Enter the number of edges : ";
    std::cin >> edges;
 
    std::vector<std::vector<int>> adj(vertices, std::vector<int>());
 
    int u = int(), v = int();
    while (edges--) {
        std::cin >> u >> v;
        graph::addEdge(&adj, u, v);
    }
 
    int cc = graph::getConnectedComponents(&adj);
    std::cout << cc << std::endl;
    return 0;
}

Here is the call graph for this function:

tests()

void tests

(

)

Function to test the algorithm

             {
    std::cout << "Running predefined tests..." << std::endl;
    std::cout << "Initiating Test 1..." << std::endl;
    std::vector<std::vector<int>> adj1(9, std::vector<int>());
    graph::addEdge(&adj1, 1, 2);
    graph::addEdge(&adj1, 1, 3);
    graph::addEdge(&adj1, 3, 4);
    graph::addEdge(&adj1, 5, 7);
    graph::addEdge(&adj1, 5, 6);
    graph::addEdge(&adj1, 8, 9);
 
    assert(graph::getConnectedComponents(&adj1) == 3);
    std::cout << "Test 1 Passed..." << std::endl;
 
    std::cout << "Innitiating Test 2..." << std::endl;
    std::vector<std::vector<int>> adj2(10, std::vector<int>());
    graph::addEdge(&adj2, 1, 2);
    graph::addEdge(&adj2, 1, 3);
    graph::addEdge(&adj2, 1, 4);
    graph::addEdge(&adj2, 2, 3);
    graph::addEdge(&adj2, 3, 4);
    graph::addEdge(&adj2, 4, 8);
    graph::addEdge(&adj2, 4, 10);
    graph::addEdge(&adj2, 8, 10);
    graph::addEdge(&adj2, 8, 9);
    graph::addEdge(&adj2, 5, 7);
    graph::addEdge(&adj2, 5, 6);
    graph::addEdge(&adj2, 6, 7);
 
    assert(graph::getConnectedComponents(&adj2) == 2);
    std::cout << "Test 2 Passed..." << std::endl;
}

Here is the call graph for this function: