#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 8
#define FALSE 0
#define TRUE 1
typedef struct node *node_pointer;
typedef struct node
{
int vertex;
node_pointer link;
};
node_pointer graph[MAX_VERTICES];
short int visited[MAX_VERTICES];
typedef struct queue *queue_pointer;
typedef struct queue
{
int vertex;
queue_pointer link;
};
node_pointer createnode(int data);
void bfs (int vertex);
void addq(queue_pointer *, queue_pointer *, int);
int deleteq (queue_pointer *front);
int main()
{
graph[0] = createnode(1);
graph[0]->link = createnode(2);
graph[1] = createnode(0);
graph[1]->link = createnode(3);
graph[1]->link->link = createnode(4);
graph[2] = createnode(0);
graph[2]->link = createnode(5);
graph[2]->link->link = createnode(6);
graph[3] = createnode(1);
graph[3]->link = createnode(7);
graph[4] = createnode(1);
graph[4]->link = createnode(7);
graph[5] = createnode(2);
graph[5]->link = createnode(7);
graph[6] = createnode(2);
graph[6]->link = createnode(7);
graph[7] = createnode(3);
graph[7]->link = createnode(4);
graph[7]->link->link = createnode(5);
graph[7]->link->link->link = createnode(6);
printf("정점의 운행 순서:");
bfs (0);
printf(" \n");
}
node_pointer createnode (int data)
{
node_pointer ptr;
ptr = (node_pointer)malloc(sizeof(struct node));
ptr->vertex = data;
ptr->link = NULL;
return ptr;
}
void bfs (int v)
{
node_pointer w;
queue_pointer front, rear;
front = rear = NULL;
printf ("V%d-> ", v);
visited[v] = TRUE;
addq (&front, &rear, v);
while (front)
{
v = deleteq (&front);
for (w=graph[v]; w;w=w->link)
if (!visited[w->vertex])
{
printf ("V%d-> ", w->vertex);
addq (&front, &rear, w->vertex);
visited[w->vertex] = TRUE;
}
}
}
void addq (queue_pointer *front, queue_pointer *rear, int data)
{
queue_pointer temp;
temp = (queue_pointer)malloc(sizeof(struct queue));
temp->vertex = data;
temp->link = NULL;
if (*front)
(*rear)->link = temp;
else
*front = temp;
*rear = temp;
}
int deleteq (queue_pointer *front)
{
queue_pointer temp;
int data;
temp = *front;
data = temp->vertex;
*front = temp->link;
free(temp);
return data;
}