Check the connected or disconnected of graph


1. Introduction

The idea of the algorithm:
Step 1: starting from the top of any of the graph. I marked the peak comes and transfer 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: check if the number is less than n vertices mark (or exists at least one peak has not been mark) connected graph will not and vice versa connected graph.

kiemtraLT_exam

2. Source code:

#include<math.h>
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#define filename "File1.inp"
void Read_File(int **A,int &n) {
FILE *f = fopen(filename,"rb");
fscanf(f,"%d",&n);
*A = new int [n];
cout<<"Matric 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);
}
char CHECK_CONNECTED(int **A,int n){
char *_tick = new char [n];
char _success;
int _count=0;
for(int i = 0; i<n; i++)
_tick[i] = 0;
_tick[0] = 1;
_count++;
do {
_success =1;
for(int i = 0; i<n; i++)
if(_tick[i]==1){
for(int j = 0; j<n; j++)
if (_tick[j] == 0 && A[i][j] > 0){
_tick[j] = 1;
_success = 0;
_count++;
if(_count == n)
return 1;
}
}
}while (_success == 0);
return 0;
}
//main function
int main(){
int **A,n;
Read_File(A,n);
if (CHECK_CONNECTED(A,n)==1)
cout<<"\nCONNECTED GRAPH";
else
cout<<"\nDISCONNECTED GRAPH";
delete *A;
getch();
return 0;
}

3. Result:

kiemtraLT_result


Advertisements