Reputation: 1
I have an undirected graph and looking for (efficient) algorithm that determine how many connected components there is in the and for every node it could tell in which connected components it locate.
I think it might be the Depth-First Search but not sure about it.
Upvotes: 0
Views: 1396
Reputation: 390
Suppose, we have the next disconnected graph:
I can offer the solution of your problem, using the algorithm Depth first search.
#include <iostream>
#include <vector>
using namespace std;
const int maximumSize=10;
vector<int> visited(maximumSize, 0);
vector<int> graph[maximumSize];
vector<vector<int>> components;
int vertices, edges;
void showContentVector1D(vector<int>& input)
{
for(int i=0; i<input.size(); ++i)
{
cout<<input[i]<<", ";
}
return;
}
void showContentVector2D(vector<vector<int>>& input)
{
int count=0;
for(int i=0; i<input.size(); ++i)
{
++count;
cout<<count<<": ";
for(int j=0; j<input[i].size(); ++j)
{
cout<<input[i][j]<<", ";
}
cout<<endl;
}
return;
}
void createGraph()
{
cin>>vertices>>edges;
int vertex0, vertex1;
for(int edge=1; edge<=edges; ++edge)
{
cin>>vertex0>>vertex1;
graph[vertex0].push_back(vertex1);
graph[vertex1].push_back(vertex0);
}
return;
}
void depthFirstSearch(int currentVertex, int previousVertex, vector<int>& graphVertices)
{
if(visited[currentVertex]==1)
{
return;
}
visited[currentVertex]=1;
graphVertices.push_back(currentVertex);
for(int nextVertex : graph[currentVertex])
{
if(nextVertex==previousVertex)
{
continue;
}
depthFirstSearch(nextVertex, currentVertex, graphVertices);
continue;
}
return;
}
void solve()
{
createGraph();
vector<int> graphVertices;
int quantityOfComponents=0;
for(int vertex=0; vertex<vertices; ++vertex)
{
if(visited[vertex]==0)
{
++quantityOfComponents;
depthFirstSearch(vertex, -1, graphVertices);
components.push_back(graphVertices);
graphVertices.clear();
}
}
cout<<"components <- "<<endl;
showContentVector2D(components);
cout<<endl<<"quantityOfComponents <- "<<quantityOfComponents<<endl;
return;
}
int main()
{
solve();
return 0;
}
Input:
5 4
0 1
0 2
1 2
3 4
Output:
components <-
1: 0, 1, 2,
2: 3, 4,
quantityOfComponents <- 2
If you have the concrete questions, write the corresponding comment.
Upvotes: 1