[C언어 알고리즘] 7.3.3 프림 알고리즘 소스 코드

[C언어 알고리즘] 7.3.3 프림 알고리즘 소스 코드

---

다음은 C언어로 작성한 프림(Prim) 알고리즘 소스 코드입니다. 동적 배열과 정점과 간선을 이용한 그래프를 구현하여 사용하고 있습니다.

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

int Graph_GetVtCnt(Graph *graph);

Vertex Graph_GetFront(Graph *graph);

int Edge_Include(Edge *edge,Vertex pt);

 

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

}

int Graph_GetVtCnt(Graph *graph)

{

    return graph->vertexs->usage;

}

Vertex Graph_GetFront(Graph *graph)

{

    Iterator front = Array_Begin(graph->vertexs);

    return (Vertex)front[0];

}

 

//Prim.h

#pragma once

#include "Graph.h"

Graph *Prim(Graph *origin);

 

//Prim.c

#include "Prim.h"

Graph *Prim(Graph *origin);

 

void SelectVertex(Graph *mstree,Graph *origin);

Graph *Prim(Graph *origin)

{

    Graph *mstree = 0;       

        Vertex vt;

    mstree = New_Graph();

        vt = Graph_GetFront(origin);

    Graph_AddVertex(mstree,vt);

    while(Graph_GetVtCnt(mstree)<Graph_GetVtCnt(origin))

    {

        SelectVertex(mstree,origin);

    }

    return mstree;

}

int IsOnlyOneInclude(Edge *edge, Array *selected);

void SelectVertex(Graph *mstree,Graph *origin)

{

    Array *selected = mstree->vertexs;

    Array *ori_edges = origin->edges;   

    Edge *selectedge=0;

 

    Iterator seek = 0, end = 0;

    Edge *edge = 0;

    seek = Array_Begin(ori_edges);

    end = Array_End(ori_edges);

   

    for(seek = seek; seek != end; ++seek)

    {

        edge = (Edge *)(*seek);

        if(IsOnlyOneInclude(edge,selected))

        {

            if(selectedge)

            {

                if(selectedge->weight>edge->weight)

                {

                    selectedge = edge;

                }

            }

            else

            {

                selectedge = edge;               

            }           

        }

    }

    Graph_AddVertex(mstree,selectedge->ep1);

    Graph_AddVertex(mstree,selectedge->ep2);

    Graph_AddEdge(mstree,selectedge->ep1,selectedge->ep2,selectedge->weight);

}

 

int IsOnlyOneInclude(Edge *edge, Array *selected)

{

    Iterator seek = 0, end = 0;

    int cnt = 0;

    Vertex vt;

    seek = Array_Begin(selected);

    end = Array_End(selected);

    for(seek = seek; seek != end; ++seek)

    {

        vt = (Vertex)(*seek);

        if(Edge_Include(edge,vt))

        {

            cnt++;

        }

    }

    return cnt==1;

}

 

//Program.c

#include "Prim.h"

Graph * InitSimulation();

int main()

{

    Graph *origin = 0;

    Graph *mstree = 0;

 

    origin = InitSimulation();

    mstree = Prim(origin);

    Graph_View(mstree);

 

    Delete_Graph(origin);

    Delete_Graph(mstree);

    return 0;

}

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",3);

    Graph_AddEdge(graph,"A","E",4);

    Graph_AddEdge(graph,"B","D",3);

    Graph_AddEdge(graph,"B","H",2);

    Graph_AddEdge(graph,"C","D",3);

    Graph_AddEdge(graph,"C","G",4);

    Graph_AddEdge(graph,"D","H",5);

    Graph_AddEdge(graph,"D","E",3);

    Graph_AddEdge(graph,"D","F",3);

    Graph_AddEdge(graph,"E","F",2);

    Graph_AddEdge(graph,"F","G",6);

    Graph_AddEdge(graph,"G","H",3);

   

    Graph_View(graph);  

    return graph;              

}