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

**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:**

Advertisements