8.3.4 프림 알고리즘 소스 코드

다음은 프림 알고리즘을 C언어로 작성한 소스 코드입니다.

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