Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
connected_components.cpp File Reference

Graph Connected Components (Connected Components) More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for connected_components.cpp:

Namespaces

 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)

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

127  {
128  /// running predefined tests
129  tests();
130 
131  int vertices = int(), edges = int();
132  std::cout << "Enter the number of vertices : ";
133  std::cin >> vertices;
134  std::cout << "Enter the number of edges : ";
135  std::cin >> edges;
136 
138 
139  int u = int(), v = int();
140  while (edges--) {
141  std::cin >> u >> v;
142  graph::addEdge(&adj, u, v);
143  }
144 
145  int cc = graph::getConnectedComponents(&adj);
146  std::cout << cc << std::endl;
147  return 0;
148 }
Here is the call graph for this function:

◆ tests()

void tests ( )

Function to test the algorithm

93  {
94  std::cout << "Running predefined tests..." << std::endl;
95  std::cout << "Initiating Test 1..." << std::endl;
97  graph::addEdge(&adj1, 1, 2);
98  graph::addEdge(&adj1, 1, 3);
99  graph::addEdge(&adj1, 3, 4);
100  graph::addEdge(&adj1, 5, 7);
101  graph::addEdge(&adj1, 5, 6);
102  graph::addEdge(&adj1, 8, 9);
103 
104  assert(graph::getConnectedComponents(&adj1) == 3);
105  std::cout << "Test 1 Passed..." << std::endl;
106 
107  std::cout << "Innitiating Test 2..." << std::endl;
109  graph::addEdge(&adj2, 1, 2);
110  graph::addEdge(&adj2, 1, 3);
111  graph::addEdge(&adj2, 1, 4);
112  graph::addEdge(&adj2, 2, 3);
113  graph::addEdge(&adj2, 3, 4);
114  graph::addEdge(&adj2, 4, 8);
115  graph::addEdge(&adj2, 4, 10);
116  graph::addEdge(&adj2, 8, 10);
117  graph::addEdge(&adj2, 8, 9);
118  graph::addEdge(&adj2, 5, 7);
119  graph::addEdge(&adj2, 5, 6);
120  graph::addEdge(&adj2, 6, 7);
121 
122  assert(graph::getConnectedComponents(&adj2) == 2);
123  std::cout << "Test 2 Passed..." << std::endl;
124 }
Here is the call graph for this function:
std::vector
STL class.
graph::getConnectedComponents
int getConnectedComponents(const std::vector< std::vector< int >> *adj)
Function that perfoms depth first search algorithm on graph and calculated the number of connected co...
Definition: connected_components.cpp:77
std::cout
graph::addEdge
void addEdge(std::vector< std::vector< int >> *adj, int u, int v)
Function that add edge between two nodes or vertices of graph.
Definition: connected_components.cpp:46
tests
void tests()
Definition: connected_components.cpp:93
std::endl
T endl(T... args)
std::cin