9.2.3 우선 순위 큐를 이용한 너비 우선 탐색 알고리즘 소스 코드

다음은 C언어로 작성한 너비 우선 탐색 알고리즘 소스 코드입니다. 너비 우선 탐색 알고리즘을 우선 순위 큐를 이용하여 작성하였습니다.

//common.h
#pragma once //헤더 파일을 한 번만 포함해서 컴파일
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <memory.h>
#include <time.h>
#pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제

//Array.h
#pragma once
typedef void * Element;
typedef struct _Array Array;
struct _Array
{
	Element *base;
	int capacity;
	int usage;
};
typedef Element *Iterator;

Array *New_Array();
void Delete_Array(Array *arr);
void Array_SetSize(Array *arr,int capacity,Element data);
void Array_PushBack(Array *arr,Element data);
void Array_Insert(Array *arr,Iterator pos,Element data);
void Array_SetAt(Array *arr,int index,Element data);
Element Array_GetAt(Array *arr,int index);
Iterator Array_Begin(Array *arr);
Iterator Array_End(Array *arr);
void Array_Erase(Array *arr,Iterator pos);

//Array.c
#include "Array.h"
#include <malloc.h>
#include <memory.h>
Array *New_Array()
{
	Array *arr = 0;
	arr = (Array *)malloc(sizeof(Array));
	arr->base = 0;
	arr->capacity = arr->usage = 0;
	return arr;
}
void Delete_Array(Array *arr)
{
	if(arr->base)
	{
		free(arr->base);
	}
	free(arr);
}
void Array_SetSize(Array *arr,int capacity,Element data)
{		
	arr->capacity = capacity;
	arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
	for(    ;arr->usage<arr->capacity; arr->usage++)
	{
		arr->base[arr->usage] = data;
	}
}
void Array_PushBack(Array *arr,Element data)
{
	Iterator at = Array_End(arr);
	Array_Insert(arr,at,data);
}
void Array_Insert(Array *arr,Iterator pos,Element data)
{
	int index = pos - arr->base;
	int mcount = arr->usage - index;
	if(arr->capacity == arr->usage)
	{
		if(arr->capacity)
		{
			arr->capacity*=2;
		}
		else
		{
			arr->capacity = 1;
		}
		arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
	}
	memcpy(arr->base+index+1,arr->base+index,sizeof(Element)*mcount);
	arr->base[index] = data;
	arr->usage++;
}
void Array_SetAt(Array *arr,int index,Element data)
{
	if((index>=0)&&(index<arr->usage))
	{
		arr->base[index] = data;
	}
}
Element Array_GetAt(Array *arr,int index)
{
	if((index>=0)&&(index<arr->usage))
	{
		return arr->base[index];
	}
	return 0;
}
Iterator Array_Begin(Array *arr)
{
	return arr->base;
}
Iterator Array_End(Array *arr)
{
	return arr->base+arr->usage;
}
void Array_Erase(Array *arr,Iterator pos)
{
	int index = pos - arr->base;
	int mcount = arr->usage - index -1;
	memcpy(pos,pos+1,sizeof(Element)*mcount);
	arr->usage--;
}

//LinkedList.h
#pragma once
typedef void * Element;
typedef struct _Node Node;
typedef Node *Link;
struct _Node
{
	Link next;
	Link prev;
	Element data;
};

typedef struct _LinkedList LinkedList;
struct _LinkedList
{
	Link head;
	Link tail;
	int usage;
};


LinkedList *New_LinkedList();
void Delete_LinkedList(LinkedList *linkedlist);
void LinkedList_PushBack(LinkedList *linkedlist,Element data);
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data);
Link LinkedList_Begin(LinkedList *linkedlist);
Link LinkedList_End(LinkedList *linkedlist);
void LinkedList_Erase(LinkedList *linkedlist,Link pos);

//LinkedList.c
#include "LinkedList.h"
#include <malloc.h>
#include <memory.h>
Link New_Node(Element data)
{
	Link link = (Link)malloc(sizeof(Node));
	link->data = data;
	link->next = link->prev = 0;
	return link;
}
void HangNode(Link link,Link pos)
{
	link->prev = pos->prev;
	link->next = pos;
	pos->prev->next = link;
	pos->prev = link;
}
void DisconnectNode(Link pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
}
LinkedList *New_LinkedList()
{
	LinkedList *linkedlist = 0;
	linkedlist = (LinkedList *)malloc(sizeof(LinkedList));
	linkedlist->head = New_Node(0);
	linkedlist->tail = New_Node(0);
	linkedlist->head->next = linkedlist->tail;
	linkedlist->tail->prev = linkedlist->head;
	linkedlist->usage = 0;
	return linkedlist;
}
void Delete_LinkedList(LinkedList *linkedlist)
{
	Link seek = linkedlist->head;
	
	while( seek != linkedlist->tail)
	{
		seek = seek->next;
		free(seek->prev);
	}
	free(linkedlist->tail);
	free(linkedlist);
}
void LinkedList_PushBack(LinkedList *linkedlist,Element data)
{
	LinkedList_Insert(linkedlist,linkedlist->tail,data);
}
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data)
{
	Link link = New_Node(data);
	HangNode(link,pos);
	linkedlist->usage++;
}
Link LinkedList_Begin(LinkedList *linkedlist)
{
	return linkedlist->head->next;
}
Link LinkedList_End(LinkedList *linkedlist)
{
	return linkedlist->tail;
}
void LinkedList_Erase(LinkedList *linkedlist,Link pos)
{
	DisconnectNode(pos);
	linkedlist->usage--;
}

//PriorityQueue.h
#pragma once
#include "LinkedList.h"

typedef struct _PriorityQueue PriQueue;
typedef int (*Compare)(Element el1,Element el2);
struct _PriorityQueue
{
    LinkedList *list;
    Compare compare;
};
PriQueue *New_PriorityQueue(Compare compare);
void Delete_PriQueue(PriQueue *pq);
void PriQueue_Put(PriQueue *pq, Element data);
Element PriQueue_Get(PriQueue *pq);
int PriQueue_IsEmpty(PriQueue *pq);

//PriorityQueue.c
#include "PriorityQueue.h"
#include <malloc.h>
#include <memory.h>
PriQueue *New_PriorityQueue(Compare compare)
{
    PriQueue *pq = (PriQueue *)malloc(sizeof(PriQueue));
    pq->list = New_LinkedList();
    pq->compare = compare;
    return pq;
}
void Delete_PriQueue(PriQueue *pq)
{
    Delete_LinkedList(pq->list);
    free(pq);
}
void PriQueue_Put(PriQueue *pq, Element data)
{
    Link seek = LinkedList_Begin(pq->list);
    Link end = LinkedList_End(pq->list);
    for(    ;seek != end; seek=seek->next)
    {
        if(pq->compare(seek->data, data)>0)
        {
            break;
        }
    }
    LinkedList_Insert(pq->list,seek,data);
}
Element PriQueue_Get(PriQueue *pq)
{    
    Link begin;
    if(PriQueue_IsEmpty(pq))
    {
        return 0;
    }
    begin = LinkedList_Begin(pq->list);
    LinkedList_Erase(pq->list,begin);
    return begin->data;
}
int PriQueue_IsEmpty(PriQueue *pq)
{
    return pq->list->usage == 0;
}

//Graph.h
#pragma once
#include "Array.h"
typedef const char * Vertex;
typedef struct _Edge Edge;
struct _Edge
{
	Vertex ep1;
	Vertex ep2;
	int weight;
};

typedef struct _Graph Graph;
struct _Graph
{
	Array *vertexs;
	Array *edges;
};

Graph *New_Graph();
void Delete_Graph(Graph *graph);
int Graph_AddVertex(Graph *graph,Vertex pt);
int Graph_AddEdge(Graph *graph,Vertex ep1, Vertex ep2, int weight);
int Graph_ExistVertex(Graph *graph,Vertex pt);
int Graph_ExistEdge(Graph *graph,Vertex ep1, Vertex ep2);
void Graph_View(Graph *graph);
void Graph_ViewVertexs(Graph *graph);
void Graph_ViewEdges(Graph *graph);
void Graph_FindNeighvor(Graph *graph,Vertex ep, Array *neighvor);
int Graph_GetWeight(Graph *graph,Vertex ep1, Vertex ep2);

//Graph.c
#include "Graph.h"
#include <malloc.h>
#include <string.h>
#include <stdio.h>
Edge *New_Edge(Vertex ep1, Vertex ep2, int weight)
{
	Edge *edge = 0;
	edge = (Edge *)malloc(sizeof(Edge));
	edge->ep1 = ep1;
	edge->ep2 = ep2;
	edge->weight = weight;
	return edge;
}
Vertex Edge_AnOther(Edge *edge,Vertex pt)
{
	if(strcmp(edge->ep1,pt)==0)
	{
		return edge->ep2;
	}
	if(strcmp(edge->ep2,pt)==0)
	{
		return edge->ep1;
	}
	return "";
}
int Edge_Include(Edge *edge,Vertex pt)
{
	return (strcmp(edge->ep1,pt)==0)||(strcmp(edge->ep2,pt)==0);
}
Graph *New_Graph()
{
	Graph *graph = 0;
	graph = (Graph *)malloc(sizeof(Graph));
	graph->vertexs = New_Array();
	graph->edges = New_Array();
	return graph;
}
void Delete_Graph(Graph *graph)
{
	Iterator seek = 0, end = 0;
	Edge *edge = 0;
	seek = Array_Begin(graph->edges);
	end = Array_End(graph->edges);
	for(seek = seek; seek != end; ++seek)
	{
		edge = (Edge *)(*seek);
		free(edge);
	}
	Delete_Array(graph->vertexs);
	Delete_Array(graph->edges);
	free(graph);
}
int Graph_AddVertex(Graph *graph,Vertex pt)
{
	if(Graph_ExistVertex(graph,pt))
	{
		return 0;
	}
	Array_PushBack(graph->vertexs,(Element)pt);
	return 1;
}
int Graph_AddEdge(Graph *graph,Vertex ep1, Vertex ep2, int weight)
{
	if(Graph_ExistVertex(graph,ep1) && Graph_ExistVertex(graph,ep2))
	{
		Edge *edge = 0;
		if(Graph_ExistEdge(graph,ep1,ep2))
		{
			return 0;
		}
		edge = New_Edge(ep1,ep2,weight);
		Array_PushBack(graph->edges,edge);
		return 1;
	}
	return 0;
}
int Graph_ExistVertex(Graph *graph,Vertex pt)
{
	Iterator seek = 0, end = 0;
	Vertex stored_pt = 0;
	seek = Array_Begin(graph->vertexs);
	end = Array_End(graph->vertexs);
	for(seek = seek; seek != end; ++seek)
	{
		stored_pt = (Vertex)(*seek);
		if(strcmp(stored_pt,pt)==0)
		{
			return 1;
		}
	}
	return 0;
}
int Graph_ExistEdge(Graph *graph,Vertex ep1, Vertex ep2)
{
	Iterator seek = 0, end = 0;
	Edge *stored_eg = 0;
	seek = Array_Begin(graph->edges);
	end = Array_End(graph->edges);
	for(seek = seek; seek != end; ++seek)
	{
		stored_eg = (Edge *)(*seek);
		if(Edge_Include(stored_eg,ep1)&&Edge_Include(stored_eg,ep2))
		{
			return 1;
		}
	}
	return 0;	
}
void Graph_View(Graph *graph)
{
	Graph_ViewVertexs(graph);
	Graph_ViewEdges(graph);
}
void Graph_ViewVertexs(Graph *graph)
{
	Iterator seek = 0, end = 0;
	Vertex pt = 0;
	printf("정점 개수:%d\n",graph->vertexs->usage);
	seek = Array_Begin(graph->vertexs);
	end = Array_End(graph->vertexs);
	for(seek = seek; seek != end; ++seek)
	{
		pt = (Vertex)(*seek);
		printf("%s\n",pt);
	}	
}
void Graph_ViewEdges(Graph *graph)
{
	Iterator seek = 0, end = 0;
	Edge *edge = 0;
	printf("간선 개수:%d\n",graph->edges->usage);
	seek = Array_Begin(graph->edges);
	end = Array_End(graph->edges);
	for(seek = seek; seek != end; ++seek)
	{
		edge = (Edge *)(*seek);
		printf("(%s ,%s):%d\n",edge->ep1,edge->ep2,edge->weight);
	}	
}
void Graph_FindNeighvor(Graph *graph,Vertex ep, Array *neighvor)
{
	Iterator seek = 0, end = 0;
	Edge *edge = 0;
	
	seek = Array_Begin(graph->edges);
	end = Array_End(graph->edges);
	for(seek = seek; seek != end; ++seek)
	{
		edge = (Edge *)(*seek);
		if(Edge_Include(edge,ep))
		{
			Vertex opt;
			opt = Edge_AnOther(edge,ep);
			Array_PushBack(neighvor,(Element)opt);
		}
	}	
}
int Graph_GetWeight(Graph *graph,Vertex ep1, Vertex ep2)
{
	Iterator seek = 0, end = 0;
	Edge *edge = 0;
	
	seek = Array_Begin(graph->edges);
	end = Array_End(graph->edges);
	for(seek = seek; seek != end; ++seek)
	{
		edge = (Edge *)(*seek);
		if(Edge_Include(edge,ep1)&&Edge_Include(edge,ep2))
		{
			return edge->weight;
		}
	}	
	return -1;
}

//Heuristic.h
#pragma once
#include "Array.h"
#include "Graph.h"
typedef struct _Heuristic Heuristic;
struct _Heuristic
{
    Array *exprs;
    Graph *graph;
    Vertex start;
    Vertex goal;
    int total_weight;
};

Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal);
void DeleteHeuristic(Heuristic *now);
void FindNextHeuristics(Heuristic *now, Array *next_heus);
Vertex GetLastVertex(Heuristic *now);
int IsGoal(Heuristic *now);
void ViewHeuristic(Heuristic *now);

//Heuristic.c
#include "Heuristic.h"
#include <malloc.h>
#include <string.h>
#include <stdio.h>

int IsExistVertex(Heuristic *now, Vertex vt)
{
    Iterator seek=0, end=0;
    Vertex expr_vt;
    seek = Array_Begin(now->exprs);
    end = Array_End(now->exprs);
    for(seek = seek; seek != end; ++seek)
    {
        expr_vt = (Vertex)(*seek);
        if(strcmp(expr_vt,vt)==0)
        {
            return 1;
        }
    }
    return 0;
}
Heuristic *MakeNextHeu(Heuristic *now,Vertex vt)
{
    Heuristic *heu = 0;
    Iterator seek=0, end=0;
    Vertex expr_vt;
    
    heu = MakeInitHeuristic(now->graph,now->start,now->goal);
    seek = Array_Begin(now->exprs);
    end = Array_End(now->exprs);
    expr_vt = (Vertex)(*seek);
    for(seek++; seek != end; ++seek)
    {
        expr_vt = (Vertex)(*seek);
        Array_PushBack(heu->exprs,(Element)expr_vt);	
    }
    heu->total_weight = now->total_weight;
    heu->total_weight += Graph_GetWeight(heu->graph,expr_vt,vt);
    Array_PushBack(heu->exprs,(Element)vt);	
    return heu;
}
Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal)
{
    Heuristic *heu = 0;
    heu = (Heuristic *)malloc(sizeof(Heuristic));
    heu->exprs = New_Array();
    heu->graph = graph;
    heu->start = start;
    heu->goal = goal;
    Array_PushBack(heu->exprs,(Element)start);
    heu->total_weight = 0;
    return heu;
}
void DeleteHeuristic(Heuristic *now)
{
    Delete_Array(now->exprs);
    free(now);
}

void FindNextHeuristics(Heuristic *now, Array *next_heus)
{
    Array *next_vts = 0;
    Iterator seek=0, end=0;
    Vertex next_vt;
    Heuristic *next;
    
    next_vts = New_Array();		
    Graph_FindNeighvor(now->graph,GetLastVertex(now),next_vts);
    
    seek = Array_Begin(next_vts);
    end = Array_End(next_vts);
    for(seek = seek; seek != end; ++seek)
    {
        next_vt = (Vertex)(*seek);
        if( !IsExistVertex(now,next_vt) )
        {
            next = MakeNextHeu(now,next_vt);
            Array_PushBack(next_heus,next);
        }		
    }
}
Vertex GetLastVertex(Heuristic *now)
{	
    Iterator end = Array_End(now->exprs);
    --end;
    return  (Vertex)(*end);	
}
int IsGoal(Heuristic *now)
{	
    return strcmp(now->goal,GetLastVertex(now))==0;
}
void ViewHeuristic(Heuristic *now)
{
    Iterator seek=0, end=0;
    printf("총 거리:%d ",now->total_weight);
    seek = Array_Begin(now->exprs);
    end = Array_End(now->exprs);	
    for(seek = seek; seek != end; ++seek)
    {
        printf("%s ",(Vertex)*seek);
    }	
    printf("\n");
}

//Program.c
#include <stdio.h>
#include "Graph.h"
#include "PriorityQueue.h"
#include "Heuristic.h"
Graph * InitSimulation()
{
    Graph *graph = New_Graph();		
    Graph_AddVertex(graph,"A");
    Graph_AddVertex(graph,"B");
    Graph_AddVertex(graph,"C");
    Graph_AddVertex(graph,"D");
    Graph_AddVertex(graph,"E");
    Graph_AddVertex(graph,"F");
    Graph_AddVertex(graph,"G");
    Graph_AddVertex(graph,"H");
    
    Graph_AddEdge(graph,"A","B",5);
    Graph_AddEdge(graph,"A","D",4);
    Graph_AddEdge(graph,"A","E",4);
    Graph_AddEdge(graph,"B","D",4);
    Graph_AddEdge(graph,"B","H",2);
    Graph_AddEdge(graph,"C","D",2);
    Graph_AddEdge(graph,"C","G",3);
    Graph_AddEdge(graph,"D","H",5);
    Graph_AddEdge(graph,"D","E",3);
    Graph_AddEdge(graph,"D","F",3);
    Graph_AddEdge(graph,"E","F",3);
    Graph_AddEdge(graph,"F","G",6);
    Graph_AddEdge(graph,"G","H",3);
    
    Graph_View(graph);
    return graph;		
}
int CompareHeu(void *v1,void *v2)
{
    Heuristic *h1 = (Heuristic *)v1;
    Heuristic *h2 = (Heuristic *)v2;
    return h1->total_weight - h2->total_weight;
}
int main()
{
    PriQueue *pq = 0;
    Heuristic *result = 0;
    Heuristic *heu = 0;
    Graph *graph = 0;
    Array *next_heus = 0;
    Iterator seek=0, end=0;
    
    graph = InitSimulation();
    pq = New_PriorityQueue(CompareHeu);
    heu = MakeInitHeuristic(graph,"A","G");
    PriQueue_Put(pq,heu);
    
    while( ! PriQueue_IsEmpty(pq) )
    {
        heu = (Heuristic *)PriQueue_Get(pq);
        ViewHeuristic(heu);
        next_heus = New_Array();
        FindNextHeuristics(heu,next_heus);
        DeleteHeuristic(heu);
        seek = Array_Begin(next_heus);
        end = Array_End(next_heus);
        for(seek=seek; seek != end; ++seek)
        {
            heu = (Heuristic *)(*seek);            
            if((result ==0)||(result->total_weight > heu->total_weight))
            {
                if(IsGoal(heu))
                {
                    if(result){ DeleteHeuristic(result); }
                    result = heu;
                }
                else
                {
                    PriQueue_Put(pq,heu);
                }
            }           
        }
        Delete_Array(next_heus);
    }
    
    printf("최단 거리\n");
    ViewHeuristic(result);
    Delete_Graph(graph);	
    Delete_PriQueue(pq);    
    return 0;
}