Berwyn Bowers
Berwyn Bowers

Reputation: 1

algorithm to Find connected components in a graph and to which connected components each node does it belong

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

Answers (1)

Vadim Chernetsov
Vadim Chernetsov

Reputation: 390

Suppose, we have the next disconnected graph:

enter image description here

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

Related Questions