너비 우선 탐색

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
#define MAX_QUEUE_SIZE 100

// ---- 큐 소스코드 시작 -------------------------------------------------------
typedef int element;
typedef struct {
 element  queue[MAX_QUEUE_SIZE];
 int  front, rear;
} QueueType;

void error(char *message)
{
 fprintf(stderr,"%s\n",message);
 exit(1);
}
// 초기화 함수
void init(QueueType *q)
{
 q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
 return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
 return ((q->rear+1)%MAX_QUEUE_SIZE == q->front);
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
   if( is_full(q) )
  error("큐가 포화상태입니다");
 q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
 q->queue[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
    if( is_empty(q) )
  error("큐가 공백상태입니다");
 q->front = (q->front+1) % MAX_QUEUE_SIZE;
 return q->queue[q->front];
}
// 삭제 함수
element peek(QueueType *q)
{
    if( is_empty(q) )
  error("큐가 공백상태입니다");
 return q->queue[(q->front+1) % MAX_QUEUE_SIZE];
}
// ---- 큐 소스코드 끝 -------------------------------------------------------

// ---- 인접 리스트 그래프 소스코드 시작  ------------------------------------
typedef struct GraphNode
{ 
   int vertex;
   struct GraphNode *link;
} GraphNode;

typedef struct GraphType {
 int n; // 정점의 개수
 GraphNode *adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g)
{
 int v;
 g->n=0;
 for(v=0;v<MAX_VERTICES;v++)
  g->adj_list[v]=NULL;
}
// 정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
 if( ((g->n)+1) > MAX_VERTICES ){
  fprintf(stderr, "그래프: 정점의 개수 초과");
  return;
 }
 g->n++;
}
// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType *g, int u, int v)
{
 GraphNode *node;
 if( u >= g->n || v >= g->n ){
  fprintf(stderr, "그래프: 정점 번호 오류");  
  return;
 }
 node = (GraphNode *)malloc(sizeof(GraphNode));
 node->vertex = v;
 node->link = g->adj_list[u];
 g->adj_list[u] = node;
}
// ---- 인접 리스트 그래프 소스코드 끝  ------------------------------------

int visited[MAX_VERTICES];

// 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색
void bfs_list(GraphType *g, int v)
{ 
    // ...

}

int main()
{
 int i;
 GraphType g;
 
 graph_init(&g);
 // 인접 리스트 생성
 for(i=0;i<4;i++)
  insert_vertex(&g, i);
  
 insert_edge(&g,0,1);
 insert_edge(&g,1,0);
 insert_edge(&g,0,3);
 insert_edge(&g,3,0);
 insert_edge(&g,1,2);
 insert_edge(&g,2,1);
 insert_edge(&g,1,3);
 insert_edge(&g,3,1);
 insert_edge(&g,2,3);
 insert_edge(&g,3,2);

    // 너비 우선 탐색 
 bfs_list(&g, 0);
 
 system("pause");
 return 0;
}