인접 행렬을 이용한 너비 우선 탐색 알고리즘을 C언어로 작성한 소스 코드입니다.
//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--;
}
//EHQueue.h
#pragma once
#include "LinkedList.h"
typedef LinkedList EHQueue;
EHQueue *New_EHQueue();
void Delete_EHQueue(EHQueue *ehq);
void EHQueue_Put(EHQueue *ehq, Element data);
Element EHQueue_Get(EHQueue *ehq);
int EHQueue_IsEmpty(EHQueue *ehq);
//EHQueue.c
#include "EHQueue.h"
EHQueue *New_EHQueue()
{
return New_LinkedList();
}
void Delete_EHQueue(EHQueue *ehq)
{
Delete_LinkedList(ehq);
}
void EHQueue_Put(EHQueue *ehq, Element data)
{
LinkedList_PushBack(ehq,data);
}
Element EHQueue_Get(EHQueue *ehq)
{
Element element = 0;
if( ! EHQueue_IsEmpty(ehq))
{
Link first = LinkedList_Begin(ehq);
element = first->data;
LinkedList_Erase(ehq,first);
}
return element;
}
int EHQueue_IsEmpty(EHQueue *ehq)
{
return ehq->usage == 0;
}
//Graph.h
#pragma once
#include "Array.h"
typedef struct{//그래프 형식 정의
int vn; //정점 개수
int **matrix;//그래프 인접 행렬
} Graph;
Graph *NewGraph(int max_vertex);//그래프 동적 생성
void DeleteGraph(Graph *graph);//그래프 소멸
void AddEdge(Graph *graph, int start, int goal);//간선 추가
void ViewGraph(Graph *graph);//그래프 정보 출력
void ViewIndegree(Graph *g);//진입차수 확인
void ViewOutdegree(Graph *g);//진출차수 확인
int Graph_FindNeighvor(Graph *graph,int lvt, Array *next_vts);
//Graph.c
#include "Graph.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Graph *NewGraph(int max_vertex)
{
int i = 0;
Graph *graph = (Graph *)malloc(sizeof(Graph));//그래프 메모리 동적 할당
graph->vn = max_vertex;//최대 정점 개수 설정
graph->matrix = (int **)malloc(sizeof(int *)*max_vertex);//매트릭스 메모리 할당
for (i = 0; i < max_vertex; i++)
{
graph->matrix[i] = (int *)malloc(sizeof(int)*max_vertex);//매크릭스 [i-row] 메모리 할당
memset(graph->matrix[i], 0, sizeof(int)*max_vertex);//메모리 0으로 초기화
}
return graph;
}
void DeleteGraph(Graph *graph)
{
int i = 0;
for (i = 0; i < graph->vn; i++)//최대 정점 개수만큼
{
free(graph->matrix[i]);//매트릭스 [i-row] 메모리 소멸
}
free(graph->matrix);//매트릭스 메모리 해제
free(graph);//그래프 메모리 해제
}
void AddEdge(Graph *graph, int vt1, int vt2)
{
graph->matrix[vt1][vt2] = 1;//간선설정
graph->matrix[vt2][vt1] = 1;//간선설정
}
void ViewGraph(Graph *graph)
{
int i =0;
int j =0;
for(i=0;i<graph->vn;i++)
{
printf("%d 에서 갈 수 있는 정점:",i);
for(j=0;j<graph->vn;j++)
{
if(graph->matrix[i][j])
{
printf("%d ",j);
}
}
printf("\n");
}
}
void ViewIndegree(Graph *g)
{
int i, j;
int degree;
printf("In-degree\n");
for (i = 0; i < g->vn; i++)
{
degree = 0;//0으로 설정
for (j = 0; j < g->vn; j++)
{
if (g->matrix[j][i])//올 수 있는 곳이 있으면
{
degree++;//차수 1 증가
}
}
printf("%d ", degree);//차수 출력
}
printf("\n");
}
void ViewOutdegree(Graph *g)
{
int i, j;
int degree;
printf("Out-degree\n");
for (i = 0; i < g->vn; i++)
{
degree = 0;//0으로 설정
for (j = 0; j < g->vn; j++)
{
if (g->matrix[i][j])//갈 수 있는 곳이 있으면
{
degree++;//차수 1 증가
}
}
printf("%d ", degree);//차수 출력
}
printf("\n");
}
int Graph_FindNeighvor(Graph *graph,int lvt, Array *nvts)
{
int i;
for (i = 0; i < graph->vn; i++)
{
if(graph->matrix[lvt][i])//올 수 있는 곳이 있으면
{
Array_PushBack(nvts,(Element)i);
}
}
return 0;
}
//Heuristic.h
#pragma once
#include "Array.h"
#include "Graph.h"
typedef struct _Heuristic Heuristic;
struct _Heuristic
{
Array *exprs;
Graph *graph;
int start;
int goal;
};
Heuristic *MakeInitHeuristic(Graph *graph,int start,int goal);
void DeleteHeuristic(Heuristic *now);
void FindNextHeuristics(Heuristic *now, Array *next_heus);
int 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, int vt)
{
Iterator seek=0, end=0;
int expr_vt;
seek = Array_Begin(now->exprs);
end = Array_End(now->exprs);
for(seek = seek; seek != end; ++seek)
{
expr_vt = (int)(*seek);
if(expr_vt==vt)
{
return 1;
}
}
return 0;
}
Heuristic *MakeNextHeu(Heuristic *now,int vt)
{
Heuristic *heu = 0;
Iterator seek=0, end=0;
int expr_vt;
heu = MakeInitHeuristic(now->graph,now->start,now->goal);
seek = Array_Begin(now->exprs);
end = Array_End(now->exprs);
expr_vt = (int)(*seek);
for(seek++; seek != end; ++seek)
{
expr_vt = (int)(*seek);
Array_PushBack(heu->exprs,(Element)expr_vt);
}
Array_PushBack(heu->exprs,(Element)vt);
return heu;
}
Heuristic *MakeInitHeuristic(Graph *graph,int start,int 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);
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;
int 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 = (int)(*seek);
if( !IsExistVertex(now,next_vt) )
{
next = MakeNextHeu(now,next_vt);
Array_PushBack(next_heus,next);
}
}
}
int GetLastVertex(Heuristic *now)
{
Iterator end = Array_End(now->exprs);
--end;
return (int)(*end);
}
int IsGoal(Heuristic *now)
{
return now->goal==GetLastVertex(now);
}
void ViewHeuristic(Heuristic *now)
{
Iterator seek=0, end=0;
seek = Array_Begin(now->exprs);
end = Array_End(now->exprs);
for(seek = seek; seek != end; ++seek)
{
printf("%d ",(int)*seek);
}
printf("\n");
}
//Program.c
#include "EHQueue.h"
#include "Heuristic.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
Graph *MakeGraph();
void DoBFSAlgorithm(Graph *graph, int v,int g);
int main(void)
{
Graph *graph = 0;
graph = MakeGraph();
DoBFSAlgorithm(graph,0,7);
DeleteGraph(graph);//그래프 소멸
return 0;
}
Graph *MakeGraph()
{
Graph *graph;
graph = NewGraph(8);//그래프 동적 생성
AddEdge(graph, 0, 1);//간선 추가
AddEdge(graph, 0, 2);//간선 추가
AddEdge(graph, 0, 3);//간선 추가
AddEdge(graph, 1, 2);//간선 추가
AddEdge(graph, 2, 3);//간선 추가
AddEdge(graph, 2, 4);//간선 추가
AddEdge(graph, 2, 5);//간선 추가
AddEdge(graph, 3, 4);//간선 추가
AddEdge(graph, 5, 6);//간선 추가
AddEdge(graph, 6, 7);//간선 추가
ViewGraph(graph);
return graph;
}
void DoBFSAlgorithm(Graph *graph, int v,int g)
{
EHQueue *ehq = 0;
Heuristic *heu = 0;
Array *next_heus = 0;
Iterator seek=0, end=0;
printf("%d에서 %d로 갈 수 있는 모든 경로\n",v,g);
ehq = New_EHQueue();
heu = MakeInitHeuristic(graph,0,7);
EHQueue_Put(ehq,heu);
while( ! EHQueue_IsEmpty(ehq) )
{
heu = (Heuristic *)EHQueue_Get(ehq);
next_heus = New_Array();
FindNextHeuristics(heu,next_heus);
seek = Array_Begin(next_heus);
end = Array_End(next_heus);
for(seek=seek; seek != end; ++seek)
{
heu = (Heuristic *)(*seek);
if(IsGoal(heu))
{
ViewHeuristic(heu);
DeleteHeuristic(heu);
}
else
{
EHQueue_Put(ehq,heu);
}
}
Delete_Array(next_heus);
}
Delete_EHQueue(ehq);
}