Algorithms / 너비 우선 탐색(Breath first search)

// Graph algorithms - breath first search : BFS)

 

#include <stdio.h>
#define N 8

int a[N+1][N+1] =
{
{0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0},
{0,1,0,1,1,1,0,0,0},
{0,0,1,0,0,0,0,1,0},
{0,0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,1,0,0},
{0,0,0,0,0,1,0,1,1},
{0,0,0,1,0,0,1,0,1},
{0,0,0,0,0,0,1,1,0}};

 

int v[N+1]; //visit

int queue[100];
int head=0;
int tail=0;

int main(void) {
 int i,j;

 for(i=1; i<=N; i++)
  v[i]=0;

 queue[tail++]=1; //queue[0] = 1;
 v[1]=1; // initial
 
 do{
  i=queue[head++]; //i = queue[0]
  
  for(j=1; j<=N; j++) {
   if(a[i][j]==1 && v[j] == 0) { //간선이 연결되어 있고, 방문하지 않은 정점
    printf("%d -> %d  ", i, j); //output
    queue[tail++]=j; //queue[1] = j
    v[j]=1; // Visit
   }
  }
 }while(head != tail);

 printf("\n");
 return 0;
}