[C언어 알고리즘] 7.3.1 프림 알고리즘에 맞게 그래프 소스 코드 수정

[C언어 알고리즘] 7.3.1 프림 알고리즘에 맞게 그래프 소스 코드 수정

---

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

 

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

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

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

}