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

다음은 C언어로 작성한 크루스칼(Kruskal) 알고리즘 소스 코드입니다. 크루스칼 알고리즘은 대표적인 탐욕 알고리즘으로 그래프에서 최소신장트리를 만드는 알고리즘입니다.

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

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

▷ 실행 결과

정점 개수:8
A
B
C
D
E
F
G
H
간선 개수:13
(A ,B):5
(A ,D):3
(A ,E):4
(B ,D):3
(B ,H):2
(C ,D):3
(C ,G):4
(D ,H):5
(D ,E):3
(D ,F):3
(E ,F):2
(F ,G):6
(G ,H):3
B,H : 2
E,F : 2
A,D : 3
B,D : 3
C,D : 3
D,E : 3
G,H : 3
정점 개수:8
B
H
A
D
C
E
F
G
간선 개수:7
(B ,H):2
(A ,D):3
(B ,D):3
(C ,D):3
(E ,F):2
(D ,E):3
(G ,H):3