[알고리즘 C언어] 6.2.2 그래프 구현(DFS 알고리즘에 사용할 그래프)

C언어로 그래프를 구현합시다. 여기에서는 정점과 간선 집합인 그래프를 구현할 거예요.

동적으로 그래프를 생성하는 함수를 구현합시다.

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)
{

먼저 이미 존재하는 정점인지 확인합니다. 만약 존재한다면 0을 반환합니다.

    if(Graph_ExistVertex(graph,pt))
    {
        return 0;
    }

정점을 보관하고 1을 반환합니다.

    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;

두 개의 정점 사이에 간선이 이미 있다면 0을 반환합니다.

        if(Graph_ExistEdge(graph,ep1,ep2))
        {
            return 0;
        }

두 개의 정점이 모두 존재하고 두 정점 사이에 간선이 없는 것을 확인했다면 간선을 동적으로 생성한 후에 보관합니다. 간선을 동적으로 생성하는 함수는 별도로 구현합시다.

        edge = New_Edge(ep1,ep2,weight);
        Array_PushBack(graph->edges,edge);
        return 1;
    }

두 개의 정점이 모두 포함하고 있지 않을 때는 0을 반환합니다.

    return 0;
}

동적으로 간선을 생성하는 함수를 구현합시다.

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

그래프에 특정 정점이 존재하는지 확인하는 함수를 구현합시다.

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

만약 보관한 정점과 입력 인자로 받은 정점을 비교하였을 때 차이가 없으면 존재하는 것이므로 1을 반환합니다.

        if(strcmp(stored_pt,pt)==0)
        {
            return 1;
        }
    }

끝까지 찾아도 없으면 0을 반환합니다.

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

만약 보관한 간선에 입력 인자로 받은 두 개의 정점을 포함하고 있으면 두 정점 사이의 간선이 있는 것이므로 1을 반환합니다.

        if(Edge_Include(stored_eg,ep1)&&Edge_Include(stored_eg,ep2))
        {
            return 1;
        }
    }

끝까지 찾아도 없으면 0을 반환합니다.

    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 Edge_Include(Edge *edge,Vertex pt)
{

간선의 두 정점 중에 입력 인자로 받은 정점과 문자열 비교했을 때 차이가 없는 정점이 있으면 포함하고 있는 것입니다.

    return (strcmp(edge->ep1,pt)==0)||(strcmp(edge->ep2,pt)==0);
}

간선에 특정 정점이 아닌 나머지 정점을 구하는 함수를 작성합시다.

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

참고로 그래프에서 정점과 정점 사이의 거리를 비중 혹은 무게로 많이 표시합니다. 이 책에서 매 번 간선의 거리를 말할 때 무게(거리)라고 표현하고 있는데 논리적으로 보면 거리가 맞는 말이고 일반적으로 그래프에서 사용하는 용어는 비중 혹은 무게로 말할 때가 많기 때문입니다.