8.4.2 크루스칼 알고리즘 소스 코드

다음은 C언어로 작성한 크루스칼 알고리즘 소스 코드입니다.

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