Graph - BFS

넓이 우선 탐색

큐를 이용해서 구현

http://richong.tistory.com/115에 존재하는 그래프를 넓이 우선탐색 알고리즘을 했을 경우이다.

1. 첫 방문 정점을 큐에 넣음

2. 큐에서 빼면서, 방문하고, 인접 점 방문하지 않았으면 을 큐에 넣는다.

3. 반복한다.

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX 30
#define FALSE 0
#define TRUE 1

typedef struct Graph_Node
{
	char vertex;
	struct Graph_Node *link;
}Node, *PNODE;

typedef struct Qeue{
	char vertex;
	struct Qeue *link;
}Qeue, *PQeue;

typedef struct Qeue_Head{
	PQeue head;
}Qeue_Head, *PQeue_Head;


typedef struct Graph_Type{
	char n; //정점의 갯수
	PNODE adj_Head[MAX]; //인접리스트를 나열하기 위한 Head
	char visited[MAX];
}Graph_Head, *PGraph_Head;

//Global var
PGraph_Head gGhead;
PQeue_Head  gQhead;

void Create_Graph(char arg_N)
{
	gGhead = (PGraph_Head)malloc(sizeof(Graph_Head));
	memset(gGhead, 0x00, sizeof(Graph_Head));
	gGhead->n = arg_N;
}

void Insert_Edge(char u, char v)
{
	PNODE new_Node = (PNODE)malloc(sizeof(Node));
	PNODE tmp_Node;
	//첫번째 삽입 연산인지 확인
	if (gGhead->adj_Head[u] == NULL){
		gGhead->adj_Head[u] = new_Node;
		new_Node->vertex = v;
		new_Node->link = NULL;
		return;
	}

	tmp_Node = gGhead->adj_Head[u];

	while (tmp_Node->link != NULL){
		tmp_Node = tmp_Node->link;
	}
	tmp_Node->link = new_Node;
	new_Node->link = NULL;
	new_Node->vertex = v;
	return;
}

void Print_adj(){
	for (int index = 0; index < gGhead->n; index++){
		PNODE tmp_Node = gGhead->adj_Head[index];
		printf("%c의 인접 노드 ", index + 65);
		while (tmp_Node->link != NULL){
			printf("%c -> ", tmp_Node->vertex+65);
			tmp_Node = tmp_Node->link;
		}
		printf("%c\n", tmp_Node->vertex + 65);
	}
}

void Create_Qeue()
{
	gQhead = (PQeue_Head)malloc(sizeof(Qeue_Head));
	memset(gQhead, 0x00, sizeof(Qeue_Head));
}

void Insert_Qeue(char vertex){

	PQeue new_Node = (PQeue)malloc(sizeof(Qeue));
	PQeue tmp_Node = gQhead->head;

	if (gQhead->head == NULL){
		gQhead->head = new_Node;
		new_Node->link = NULL;
		new_Node->vertex = vertex;
		return;
	}

	while (tmp_Node ->link != NULL)
	{
		tmp_Node = tmp_Node->link;
	}

	tmp_Node->link = new_Node;
	new_Node->vertex = vertex;
	new_Node->link = NULL;
	return;
}

void print_Qeue(){

	PQeue tmp_Node = gQhead->head;

	while (tmp_Node ->link != NULL){
		printf("[%c] ", tmp_Node->vertex + 65);
		tmp_Node = tmp_Node->link;
	}
	printf("[%c] ", tmp_Node->vertex + 65);

}
char Delete_Qeue(){

	PQeue tmp_Node = gQhead->head;
	PQeue tmp2_Node = NULL;

	if (gQhead->head == NULL){
		printf("Empty Qeue!!\n");
		return 'E';
	}

	//마지막 
	if (tmp_Node ->link == NULL)
	{
		gQhead->head = NULL;
		return tmp_Node->vertex;
	}
	tmp2_Node = tmp_Node->link;
	gQhead->head = tmp2_Node;

	return tmp_Node->vertex;
}




void BFS(char vertex)
{
	PQeue tmp_Node = NULL;
	//첫 정점을 Qeue에 넣음
	Insert_Qeue(vertex);

	printf("\n##################BFS######################\n\n");
	//Qeue가 빌때까지 반복
	while (gQhead->head != NULL)
	{
		//큐에서 빼오고
		int vertex = Delete_Qeue();
		PNODE tmp2_Node =  gGhead->adj_Head[vertex];
		
		//방문 하지 않은 점에만 해당
		while (!gGhead->visited[vertex])
		{
			//해당 점을 방문하고
			gGhead->visited[vertex] = TRUE;
			printf("%c -> ", vertex + 65);
			//해당 인접 큐에 점을 넣기
			while (tmp2_Node->link != NULL)
			{
				Insert_Qeue(tmp2_Node->vertex);
				tmp2_Node = tmp2_Node->link;
			}
			Insert_Qeue(tmp2_Node->vertex);
		}
	}
	printf("\n\n###########################################");
}


int main()
{
	////////////////////////////Graph Setting/////////////////////////////////
	Create_Graph(7);
	Insert_Edge(0, 1);
	Insert_Edge(0, 2);

	Insert_Edge(1, 3);
	Insert_Edge(1, 4);

	Insert_Edge(2, 4);

	Insert_Edge(3, 1);
	Insert_Edge(3, 6);

	Insert_Edge(4, 1);
	Insert_Edge(4, 1);
	Insert_Edge(4, 6);

	Insert_Edge(5, 6);

	Insert_Edge(6, 3);
	Insert_Edge(6, 4);
	Insert_Edge(6, 5);
	Print_adj();
	///////////////////////////////////////////////////////////////////////////

	////////////////////////////Qeue Setting//////////////////////////////////
	Create_Qeue();

	BFS(0);
	////////////////////////////////////////////////////////////////////////////
	getchar();
}

결과 값