#include "stdafx.h"
#include "stdio.h"
#include "memory.h"
#include "conio.h"
#define MaxV 20 //Define su dung cho so dinh cuc dai cua do thi
int A[MaxV][MaxV]; //Ma tran ke
int V = 0; //So dinh cua do thi
int ChuaXet[MaxV];
//Thu tuc nhap matran ke bang ban phim.
void NhapMTKe(int A[][MaxV], int &V)
{
printf("Nhap V:");
scanf("%d", &V);
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
{
printf("A[%d,%d] = ", i+1, j+1);
scanf("%d", &(A[i][j]));
}
}
}
void XuatMTKe(int A[][MaxV], int V)
{
printf("\nMa tran ke:\n");
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
printf("%3d ", A[i][j]);
printf("\n");
}
}
int DocMTKe(char *fileName, int A[][MaxV], int &V)
{
FILE *f = fopen(fileName, "rt");
if (f == NULL)
{
printf("Doc file loi !!!");
return 0;
}
fscanf(f, "%d", &V);
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
{
fscanf(f, "%d", &(A[i][j]));
}
}
return 1;
}
/*Thu tuc duyet BFS, duyet theo chieu rong su dung QUEUE de chay khong de quy.*/
void BFS0DeQuy(int v)
{
int QUEUE[MaxV], topQ=0, bottomQ=0; //Khoi dau voi mot QUEUE rong
QUEUE[topQ++] = v; //Dua dinh v vao QUEUE, xem no nhu la da xet
ChuaXet[v] = 1;
while ( bottomQ < topQ ) //Lap trong khi QUEUE khac rong
{
v = QUEUE[bottomQ++]; //Lay dinh v tu day cua QUEUE
for (int u=0; u<V; u++)
if ( A[v][u] != 0 ) //The hien u ke voi dinh v
if ( ChuaXet[u]==0 )
{
QUEUE[topQ++] = u; // Dua u vao dinh cua QUEUE
ChuaXet[u] = 1;
}
}
}
*/
int main(int argc, char* argv[])
{
int j;
NhapMTKe(A, V);
//DocMTKe("D:\\Dothi_1.txt", A, V);
XuatMTKe(A,V);
memset(ChuaXet, 0, sizeof(ChuaXet) );
DFS0DeQuy(0);
printf( "Cac dinh da duyet: " );
for(j=0;j<V;j++)
if (ChuaXet[j] == 1)
printf( "%d ", j+1 );
getch ( );
return 1;
}