[C언어 자료구조] 8.4 그래프 소스 코드

8.4 그래프 소스 코드

---

//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--;

}

 

---

//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;

}

 

---

//Program.c

#include "Graph.h"

int main()

{

    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);

    Delete_Graph(graph);

    return 0;  

}

 

---

 

이상으로 기본적인 자료구조를 살펴보았습니다. 보다 깊은 학습을 원하는 이들은 이 외에 다른 자료구조 및 알고리즘에 관한 학습도 해 보길 권합니다. 모두 수고하셨습니다.