[카테고리:] <span>C언어 알고리즘</span>

이 책에서는 프림 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요.

프림 알고리즘을 구현하기 전에 그래프 알고리즘에 몇 가지 함수를 추가하기로 해요.

먼저 정점의 개수를 구하는 함수를 제공하기로 해요.

int Graph_GetVtCnt(Graph *graph);

그리고 그래프의 맨 앞에 있는 정점을 구하는 함수도 제공해요.

Vertex Graph_GetFront(Graph *graph);

마지막으로 간선에 특정 정점을 끝점으로 하는지 판별하는 함수를 제공하기로 해요.

int Edge_Include(Edge *edge,Vertex pt);

정점의 개수를 구하는 함수는 단순히 그래프에 있는 정점 컬렉션의 개수를 반환하게 구현하세요.

int Graph_GetVtCnt(Graph *graph)
{
    return graph->vertexs->usage;
}

그래프의 맨 앞에 있는 정점을 구하는 함수에서는 정점 컬렉션의 시작 위치의 정점을 반환하세요.

Vertex Graph_GetFront(Graph *graph)
{
    Iterator front = Array_Begin(graph->vertexs);
    return (Vertex)front[0];
}

간선에 특정 정점을 끝점으로 하는지 판별하는 함수에서는 두 개의 끝점과 비교한 결과를 반환하겠죠.

int Edge_Include(Edge *edge,Vertex pt)
{
    return (strcmp(edge->ep1,pt)==0)||(strcmp(edge->ep2,pt)==0);
}

다음은 수정한 그래프 헤더 파일의 내용입니다.

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