[C언어 알고리즘] 7.4.2 크루스칼 알고리즘 소스 코드

[C언어 알고리즘] 7.4.2 크루스칼 알고리즘 소스 코드

---

다음은 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--;

}

 

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

 

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

}

 

//Kruskal.h

#pragma once

#include "Graph.h"

Graph *Kruskal(Graph *origin);

 

//Kruskal.c

#include "Kruskal.h"

#include "Graph.h"

#include <stdio.h>

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

Array *MakeSortedEdges(Array *edges);

void SelectEdge(Array *graphs,Array *sorted_edges);

Graph *Kruskal(Graph *origin)

{

    Array *sorted_edges=0;

    Array *graphs=0;

    int vt_cnt_mone = 0;

    int ed_cnt=0;

 

    graphs = New_Array();

    sorted_edges = MakeSortedEdges(origin->edges);

    vt_cnt_mone = Graph_GetVtCnt(origin)-1;

    while(ed_cnt<vt_cnt_mone)

    {

        SelectEdge(graphs,sorted_edges);

        ed_cnt++;

    }

    return (Graph *)(*Array_Begin(graphs));

}

 

 

void AddEdge(Array *sorted_edge,Edge *edge);

Array *MakeSortedEdges(Array *edges)

{

    Array *sorted_edges = New_Array();

    Iterator seek = 0, end = 0;

    Edge *edge = 0;

    seek = Array_Begin(edges);

    end = Array_End(edges);

   

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

    {

        edge =  (Edge *)(*seek);

        AddEdge(sorted_edges,edge);

    }

    return sorted_edges;

}

void AddEdge(Array *sorted_edges,Edge *edge)

{

    Iterator seek = 0, end = 0;

    Edge *stored_edge = 0;

    seek = Array_Begin(sorted_edges);

    end = Array_End(sorted_edges);

   

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

    {

        stored_edge =  (Edge *)(*seek);

        if(edge->weight < stored_edge->weight)

        {

            break;

        }

    }

    Array_Insert(sorted_edges,seek,edge);

}

 

int GreedyEdge(Edge *edge,Array *graphs);

void SelectEdge(Array *graphs,Array *sorted_edges)

{   

    Edge *edge = 0;

    int i = 0;   

    for(i=0; i<sorted_edges->usage;i++)

    {       

        edge =  (Edge *)Array_GetAt(sorted_edges,i);

        if(GreedyEdge(edge,graphs))

        {

            return;

        }

        else

        {

            Array_Erase(sorted_edges,sorted_edges->base+i);

            i--;

        }

    }

}

void Merge_Graph(Graph *graph1,Graph *graph2);

int GreedyEdge(Edge *edge,Array *graphs)

{

    Graph *graph=0;

    Graph *graph2=0;

    Iterator a=0;

    Iterator seek = 0, end = 0;   

 

    seek = Array_Begin(graphs);

    end = Array_End(graphs);

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

    {       

        graph  =  (Graph *)(*seek);

        if(Graph_ExistVertex(graph,edge->ep1))

        {           

            if(Graph_ExistVertex(graph,edge->ep2))

            {

                return 0;

            }

            else

            {

                if(a==0)

                {                   

                    a=seek;

                }

                else

                {

                    Array_Erase(graphs,seek);

                    break;

                }

            }

        }

        else

        {

            if(Graph_ExistVertex(graph,edge->ep2))

            {

                if(a==0)

                {

                    a=seek;

                }

                else

                {

                    Array_Erase(graphs,seek);

                    break;

                }

            }          

        }

    }

    if(a==0)

    {

        graph2 = New_Graph(); 

        Array_PushBack(graphs,graph2);

    }

    else

    {

        graph2 = (Graph *)(*a);

        if(seek!=end)

        {  

            Merge_Graph(graph2,graph);                                                                

        }       

    }

    printf("%s,%s : %d\n",edge->ep1,edge->ep2,edge->weight);

    Graph_AddVertex(graph2,edge->ep1);

    Graph_AddVertex(graph2,edge->ep2);

    Graph_AddEdge(graph2,edge->ep1,edge->ep2,edge->weight);

    return 1;

}

void Merge_Graph(Graph *graph1,Graph *graph2)

{

    Iterator seek = 0, end = 0; 

    Edge *ed=0;

    seek = Array_Begin(graph2->vertexs);

    end = Array_End(graph2->vertexs);

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

    {

        Graph_AddVertex(graph1,(Vertex)(*seek));       

    }

    seek = Array_Begin(graph2->edges);

    end = Array_End(graph2->edges);

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

    {

        ed = (Edge *)(*seek);

        Graph_AddEdge(graph1,ed->ep1,ed->ep2,ed->weight);

    }

}

 

//Program.c

#include "Kruskal.h"

Graph * InitSimulation();

int main()

{

    Graph *origin = 0;

    Graph *mstree = 0;

 

    origin = InitSimulation();

    mstree = Kruskal(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;              

}