mario
17-11-2008, 07:09 PM
Kiểm tra tính liên thông của đồ thị
// Kiem tra tinh lien thong cua do thi.
#include<conio.h>
#include<iostream.h>
#include<iomanip.h>
int kt[100],n,tk=1;
void DFS (int a[100][100], int i)
{
int j;
cout<<"->"<<i;
kt[i]=1;
for (j=1;j<=n;j++)
if (a[i][j]==1 && kt[j]==0)
DFS (a,j);
}
//-----------------------------------------
void DFSS (int a[100][100])
{
for (int i=1;i<=n;i++)
{
if (kt[i]==0)
{
tk++;
cout<<endl;
DFS (a,i);
}
}
}
//-----------------------------------------
void nhap (int a[100][100])
{
int i,j;
cout<<"Nhap so dinh cua do thi n = "; cin>>n;
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
{
cout<<"a["<<i<<","<<j<<"]="; cin>>a[i][j];
a[j][i]=a[i][j];
}
a[i][i]=0;
}
}
//-----------------------------------------
void indothi (int a[100][100])
{
cout<<"Do thi da nhap : "<<endl;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<setw(6)<<a[i][j];
cout<<endl;
}
getch();
}
//-----------------------------------------
void lienthong (int a[100][100])
{
int i,j;
nhap (a);
indothi (a);
for (i=1;i<=n;i++)
kt[i]=0;
DFS (a,1);
DFSS (a);
if (tk==1) cout<<endl<<"Do thi lien thong !";
else
{
cout<<endl<<"Do thi khong lien thong, ";
cout<<"va co "<<tk<<" thanh phan lien thong.";
}
getch();
}
//-----------------------------------------
void main ()
{
int a[100][100];
clrscr();
lienthong (a);
}
Nguồn: CuaSoIT.com
// Kiem tra tinh lien thong cua do thi.
#include<conio.h>
#include<iostream.h>
#include<iomanip.h>
int kt[100],n,tk=1;
void DFS (int a[100][100], int i)
{
int j;
cout<<"->"<<i;
kt[i]=1;
for (j=1;j<=n;j++)
if (a[i][j]==1 && kt[j]==0)
DFS (a,j);
}
//-----------------------------------------
void DFSS (int a[100][100])
{
for (int i=1;i<=n;i++)
{
if (kt[i]==0)
{
tk++;
cout<<endl;
DFS (a,i);
}
}
}
//-----------------------------------------
void nhap (int a[100][100])
{
int i,j;
cout<<"Nhap so dinh cua do thi n = "; cin>>n;
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
{
cout<<"a["<<i<<","<<j<<"]="; cin>>a[i][j];
a[j][i]=a[i][j];
}
a[i][i]=0;
}
}
//-----------------------------------------
void indothi (int a[100][100])
{
cout<<"Do thi da nhap : "<<endl;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<setw(6)<<a[i][j];
cout<<endl;
}
getch();
}
//-----------------------------------------
void lienthong (int a[100][100])
{
int i,j;
nhap (a);
indothi (a);
for (i=1;i<=n;i++)
kt[i]=0;
DFS (a,1);
DFSS (a);
if (tk==1) cout<<endl<<"Do thi lien thong !";
else
{
cout<<endl<<"Do thi khong lien thong, ";
cout<<"va co "<<tk<<" thanh phan lien thong.";
}
getch();
}
//-----------------------------------------
void main ()
{
int a[100][100];
clrscr();
lienthong (a);
}
Nguồn: CuaSoIT.com