Algorithms_in_C++
1.0.0
Set of algorithms implemented in C++.
|
Graph Connected Components (Connected Components) More...
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
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 () |
Graph Connected Components (Connected Components)
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
int main | ( | void | ) |
Main function
running predefined tests
void tests | ( | ) |
Function to test the algorithm