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

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

---

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

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;

}

 

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