RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/df/ddd/connected__components_8cpp.html below:

TheAlgorithms/C++: graph/connected_components.cpp File Reference

Searching...

No Matches

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

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

Go to the source code of this file.

void graph::addEdge (std::vector< std::vector< int > > *adj, int u, int v) Function that add edge between two nodes or vertices of graph.
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.
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.
void tests () int main ()

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

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

Definition in file connected_components.cpp.

◆ main()

Main function

running predefined tests

Definition at line 127 of file connected_components.cpp.

127 {

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

137 std::vector<std::vector<int>> adj(vertices, std::vector<int>());

138

139 int u = int(), v = int();

140 while (edges--) {

141 std::cin >> u >> v;

143 }

144

146 std::cout << cc << std::endl;

147 return 0;

148}

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...

void addEdge(std::vector< std::vector< int > > *adj, int u, int v)

Function that add edge between two nodes or vertices of graph.

◆ tests()

Function to test the algorithm

Definition at line 93 of file connected_components.cpp.

93 {

94 std::cout << "Running predefined tests..." << std::endl;

95 std::cout << "Initiating Test 1..." << std::endl;

96 std::vector<std::vector<int>> adj1(9, std::vector<int>());

103

105 std::cout << "Test 1 Passed..." << std::endl;

106

107 std::cout << "Innitiating Test 2..." << std::endl;

108 std::vector<std::vector<int>> adj2(10, std::vector<int>());

121

123 std::cout << "Test 2 Passed..." << std::endl;

124}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4