[C언어 알고리즘] 6.2.8 깊이우선탐색(DFS) 알고리즘 소스 코드
//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--;
}
//EHStack.h
#pragma once
#include "LinkedList.h"
typedef LinkedList EHStack;
EHStack *New_EHStack();
void Delete_EHStack(EHStack *ehs);
void EHStack_Push(EHStack *ehs, Element data);
Element EHStack_Pop(EHStack *ehs);
int EHStack_IsEmpty(EHStack *ehs);
//EHStack.c
#include "EHStack.h"
#include <malloc.h>
#include <memory.h>
EHStack *New_EHStack()
{
return New_LinkedList();
}
void Delete_EHStack(EHStack *ehs)
{
Delete_LinkedList(ehs);
}
void EHStack_Push(EHStack *ehs, Element data)
{
LinkedList_PushBack(ehs,data);
}
Element EHStack_Pop(EHStack *ehs)
{
Element element = 0;
if( ! EHStack_IsEmpty(ehs))
{
Link last = LinkedList_End(ehs);
last = last->prev;
element = last->data;
LinkedList_Erase(ehs,last);
}
return element;
}
int EHStack_IsEmpty(EHStack *ehs)
{
return ehs->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 "Graph.h"
#include "EHStack.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 main()
{
EHStack *ehs = 0;
Heuristic *heu = 0;
Graph *graph = 0;
Array *next_heus = 0;
Iterator seek=0, end=0;
graph = InitSimulation();
ehs = New_EHStack();
heu = MakeInitHeuristic(graph,"A","H");
EHStack_Push(ehs,heu);
while( ! EHStack_IsEmpty(ehs) )
{
heu = (Heuristic *)EHStack_Pop(ehs);
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
{
EHStack_Push(ehs,heu);
}
}
Delete_Array(next_heus);
}
Delete_Graph(graph);
Delete_EHStack(ehs);
return 0;
}
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
| [C언어 알고리즘] 7.3 프림(Prim) 알고리즘(최소신장트리 알고리즘) (0) | 2016.12.04 |
|---|---|
| [C언어 알고리즘] 7.2 SJF(Shortest Job First) 알고리즘 (0) | 2016.12.04 |
| [C언어 알고리즘] 7.1.1 거스름 돈 알고리즘 소스 코드 (0) | 2016.12.02 |
| [C언어 알고리즘] 7.1 거스름 돈 알고리즘 (0) | 2016.12.02 |
| [C언어 알고리즘] 7. 탐욕(Greedy) 알고리즘 (0) | 2016.12.02 |
| [C언어 알고리즘] 6.2.7 깊이우선탐색(DFS) 알고리즘 테스트 코드 작성 (0) | 2016.12.01 |
| [C언어 알고리즘] 6.2.6 깊이우선탐색(DFS) 알고리즘의 경험 정보 구현 (0) | 2016.12.01 |
| [C언어 알고리즘] 6.2.5 깊이우선탐색(DFS) 알고리즘의 경험(Heuristic) 정보 설계 (0) | 2016.12.01 |
| [C언어 알고리즘] 6.2.4 그래프 테스트 소스 코드 (0) | 2016.12.01 |
| [C언어 알고리즘] 6.2.3 그래프 테스트(DFS 알고리즘에 사용할 그래프) (0) | 2016.12.01 |