[C] BFS, DFS

// bfsdfs.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

bfsdfs.cpp

#include "stdafx.h"

 

class Queue
{
public:

 Queue() : sp(0), count(0) { }

 void Put(int x) { data[(sp+count)%128] = x; count++; }
 int Get() { int x = data[sp]; sp = (sp+1)%128; count--; return x; }
 bool lsEmpty() { return count == 0; }

private:

int sp, count;
int data[128];

};

int adj[8][8] =
{

 { 0, 0, 1, 1, 0, 0, 0, 0 },
 { 1, 0, 1, 0, 0, 0, 0, 0 },
 { 1, 0, 0, 1, 1, 0, 0, 0 },
 { 1, 0, 1, 0, 0, 1, 1, 0 },
 { 0, 0, 1, 0, 0, 0, 0, 0 },
 { 0, 1, 0, 1, 0, 0, 1, 1 },
 { 0, 1, 0, 1, 0, 1, 0, 1 },
 { 0, 0, 0, 0, 0, 1, 1, 0 }

};

int visited[8];

void dfs(int s)
{

 visited[s] = true;
 printf( "%d\n", s );
 for( int i = 0; i < 8 ; i++ )
 {

  if( adj[s][i] == 0 )

continue;

  if( visited[i] = true )

continue;

  dfs(i);

 }

}

void bfs()
{

 int vis[8];
 for( int i = 0; i < 8; i++ )

vis[i] = false;

 Queue q;
 vis[0] = true;
 q.Put(0);

 while( q.lsEmpty() == false )
 {

  int u = q.Get();
  printf( "%d\n", u );
  for( int i = 0; i < 8; i++ )
  {

   if( adj[u][i] == 0 )

continue;

   if( vis[i] = true )

continue;

   vis[i] = true;
   q.Put(i);

  }

 }

}

int _tmain(int argc, _TCHAR* argv[])
{

 printf( "DFS result\n" );
 dfs(0);
 printf( "BFS result\n" );
 bfs();
 printf( "\n" );

 for( int i = 0; i < 8; i++ )
 {

  for( int j = 0; j < 8; j++)

   printf( "%d ", adj[i][j] );

  putchar( '\n' );

 }

 return 0;

}