Count the number of connected components in the graph


1. Introduction:

The idea of the algorithm:
Step 0: initialization number of components is 0.
Step 1: starting from a less marked peak of the graph. I marked the peak output development, increasing the number of components in the 1 and go to step 2.
Step 2: from a peak i had marked, one marked vertex j if A [i, j] = 1 and j not yet rated mark and move on to Step 3.
Step 3: perform Step 2 until no longer workable switch Step 4.
Step 4: If the number of peaks marked with n ends algorithm, reverse back Step1.

TPLT_exam

2. Source code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define TenFile "File2.inp"
void Read_File(int **A,int &n) {
FILE*f = fopen(TenFile,"rb");
fscanf(f,"%d",&n);
*A = new int [n];
cout<<"Matrix corresponding link: ";
for(int i =0;i<n;i++) {
A[i] = new int [n];
cout<<endl;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<" "<<A[i][j];
}
}
fclose(f);
}
int connected_components(int **A, int n){
char *_mark = new char [n];
char success;
int count=0, i,j, MLT=0;
for( i = 0; i<n; i++)
_mark[i] = 0;
do {
j = 0;
while(_mark[j]==1)
j++;
_mark[j] = 1;
count++;
MLT++;
do {
success = 0;
for(i = 0; i<n; i++)
if(_mark[i]==1)
for(j = 0; j<n; j++)
if (_mark[j] == 0 && A[i][j] > 0) {
_mark[j] = 1;
success =1;
count++;
if(count == n) return MLT;
}
}while (success == 1);
} while(count<n);
return MLT;
}
//Main function
void main(){
clrscr();
int **A,n;
Read_File(A,n);
cout<<"\nNumber of connected components: "<<connected_components(A,n);
delete *A;
getch();
}

3. Result:

TPLT_Result_1


Advertisements