[카테고리:] <span>자료구조와 알고리즘</span>

인접 행렬을 이용한 너비 우선 탐색 알고리즘을 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);
}