Notice
Recent Posts
Recent Comments
Link
«   2024/12   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
Tags more
Archives
Today
Total
관리 메뉴

SYDev

[Data Structure] Chapter 14: 그래프(Graph) 본문

Data Structure & Algorithm/Data Structure

[Data Structure] Chapter 14: 그래프(Graph)

시데브 2023. 9. 20. 02:41
정점(vertex)과 간선(edge)로 표현되는
그래프 자료구조에 대해 이해하고, 구현해보자.

 

 

그래프의 이해

  • 정점(vertex): 연결의 대상이 되는 개체 또는 위치를 의미한다.
  • 간선(edge): 이들 사이를 연결하는 선을 의미한다.
  • 다음과 같이 정점과 간선으로 구성된 자료구조를 그래프라고 한다.

정점과 간선

 

 

그래프의 종류

무방향 그래프와 방향 그래프

  • 무방향 그래프(undirected graph): 연결 관계에 있어서 방향성이 없는 그래프를 의미한다.
  • 방향 그래프(directed graph) or 다이그래프(digraph): 간선에 방향정보가 포함되어 있는 그래프를 의미한다.
  • 완전 그래프(complete graph): 각각의 정점에서 다른 모든 정점을 연결한 그래프를 의미한다.
  • 방향 그래프의 간선의 수는 무방향 간선 두 배가 된다.

 

좌측부터 무방향 그래프와 방향 그래프

 

완전 그래프

 

가중치 그래프와 부분 그래프

  • 가중치 그래프(weight graph): 간선에 가중치 정보를 두어서 구성한 그래프를 의미한다.
  • 부분 그래프: 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프를 의미한다.

 

가중치 그래프

 

위 가중치 그래프의 부분 그래프

 

 

그래프의 집합 표현

무방향 그래프

 

  • V(G1) = {A, B, C, D}, V(G2) = {A, B, C, D}
  • E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}, E(G2) = {(A, C), (A, D), (B, C)}

 

방향 그래프

 

  • V(G3) = {A, B, C, D}, V(G4) = {A, B, C, D}
  • E(G3) = {<A, B>, <A, C>, <D, A>}, E(G4) = {<A, C>, <B, C>, <D, A>}

 

그래프의 구현

그래프 자료구조의 ADT

void GraphInit(UALGraph * pg, int nv);
- 그래프의 초기화를 진행한다.
- 두 번째 인자로 정점의 수를 전달한다.

void GraphDestroy(UALGraph * pg);
- 그래프 초기화 과정에서 할당한 리소스를 반환한다.

void AddEdge(UALGraph * pg, int fromV, int toV);
- 매개변수 formV와 toV로 전달된 정점을 연결하는 간선을 그래프에 추가한다.

void ShowGraphEdgeInfo(UALGraph * pg);
- 그래프의 간선정보를 출력한다. 

 

인접 행렬(adjacent matrix) 기반 그래프

 인접 행렬 기반 그래프는 다음과 같이 정방 행렬을 활용한다.

 

좌측부터 무방향 그래프와 방향 그래프의 인접 행렬 표현

 

인접 리스트(adjacent list) 기반 그래프

 인접 리스트 기반 그래프는 다음과 같이 연결 리스트를 활용한다.

 

좌측부터 무방향 그래프와 방향 그래프의 인접 리스트 표현

 

인접 리스트의 구현

  • Chapter 4에서 구현한 DLinkedList.h, DLinkedList.c를 이용한다.

 

 파일명: ALGraph.h

#ifndef __AL_GRAPH__
#define __AL_GRAPH__

#include "DLinkedList.h"

enum {A, B, C, D, E, F, G, H, I, J};

typedef struct _ual
{
    int numV;
    int numE;
    List * adjList;
} ALGraph;

void GraphInit(ALGraph * pg, int nv);

void GraphDestroy(ALGraph * pg);

void AddEdge(ALGraph * pg, int fromV, int toV);

void ShowGraphEdgeInfo(ALGraph * pg);

#endif

>> A~J는 숫자 0~9의 상수로 지정

 

 파일명: ALGraph.c

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"
#include "ALGraph.h"

int WhoIsPrecede(int data1, int data2);

void GraphInit(ALGraph * pg, int nv)
{
    int i;

    pg->adjList = (List*)malloc(sizeof(List)*nv);
    pg->numV = nv;
    pg->numE = 0;

    for(i=0; i<nv; i++)
    {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
    }
}

void GraphDestroy(ALGraph * pg)
{
    if(pg->adjList != NULL)
        free(pg->adjList);
}

void AddEdge(ALGraph * pg, int fromV, int toV)
{
    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);

    pg->numE +=1;
}


void ShowGraphEdgeInfo(ALGraph * pg)
{
    int i;
    int vx;

    for(i=0; i<pg->numV; i++)
    {
        printf("%c와 연결된 정점: ", i + 65);

        if(LFirst(&(pg->adjList[i]), &vx));
        {
            printf("%c ", vx + 65);

            while(LNext(&(pg->adjList[i]), &vx))
                printf("%c ", vx + 65);
        }

        printf("\n");
    }
}

int WhoIsPrecede(int data1, int data2)
{
    if(data1 < data2)
        return 0;
    else
        return 1;
}

 

 파일명: ALGraphMain.c

#include <stdio.h>
#include "ALGraph.h"

int main(void)
{
    ALGraph graph;
    GraphInit(&graph, 5);

    AddEdge(&graph, A, B);
    AddEdge(&graph, A, D);
    AddEdge(&graph, B, C);
    AddEdge(&graph, C, D);
    AddEdge(&graph, D, E);
    AddEdge(&graph, E, A);

    ShowGraphEdgeInfo(&graph);
    GraphDestroy(&graph);

    return 0;
}
A와 연결된 정점: B D E 
B와 연결된 정점: A C 
C와 연결된 정점: B D 
D와 연결된 정점: A C E 
E와 연결된 정점: A D

 

main 함수에서 생성한 그래프

 

 

그래프의 탐색

깊이 우선 탐색

깊이 우선 탐색(Depth First Search: DFS)의 핵심은 다음 세 가지이다.

 

- 탐색을 진행할 때, 현재 정점과 연결된 하나의 정점으로만 이동한다.
- 현재 정점과 연결된 모든 정점이 이미 방문된 상태일 때, 이동과정의 역순으로 진행한다.
- 탐색을 시작한 위치(정점)에서 탐색을 마친다.

 

DFS의 과정

 

깊이 우선 탐색의 구현

  • DFS의 구현을 위해서는 스택, 배열 두 가지가 필요하다.
  • 스택 - 경로 정보의 추적을 목적으로 한다.
  • 배열 - 방문 정보의 기록을 목적으로 한다.
  • Chapter 06에서 구현한 ArrayBaseStack.h  ArrayBaseStack.c을 이용한다.
  • Chapter 04에서 구현한 DLinkedList.h  DLinkedList.c을 이용한다.

 

DFS 구조

 

 파일명: ALGraphDFS.h

#ifndef __AL_GRAPG_DFS__
#define __AL_GRAPG_DFS__

#include "DLinkedList.h"

enum {A, B, C, D, E, F, G, H, I, J};

typedef struct _ual
{
    int numV;
    int numE;
    List * adjList;
    int * visitInfo;    //탐색이 진행된 정점의 정보
} ALGraph;

void GraphInit(ALGraph * pg, int nv);

void GraphDestory(ALGraph * pg);

void AddEdge(ALGraph * pg, int fromV, int toV);

void ShowGraphEdgeInfo(ALGraph * pg);

//정점의 정보 출력: DFS 기반
void DFShowGraphVertex(ALGraph * pg, int startV);

#endif

 

 파일명: ALGraphDFS.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DLinkedList.h"
#include "ALGraphDFS.h"
#include "ArrayBaseStack.h"

int WhoIsPrecede(int data1, int data2);

void GraphInit(ALGraph * pg, int nv)
{
    int i;

    pg->adjList = (List*)malloc(sizeof(List)*nv);
    pg->numE = 0;
    pg->numV = nv;

    for(i=0; i<nv; i++)
    {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
    }

    pg->visitInfo = (int*)malloc(sizeof(int) * (pg->numV));

    memset(pg->visitInfo, 0, sizeof(int) * (pg->numV));
}

void GraphDestory(ALGraph * pg)
{
    if(pg->adjList != NULL)
        free(pg->adjList);
    
    if(pg->visitInfo != NULL)
        free(pg->visitInfo);
}

void AddEdge(ALGraph * pg, int fromV, int toV)
{
    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);

    pg->numE +=1;
}

void ShowGraphEdgeInfo(ALGraph * pg)
{
    int i;
    int vx;

    for(i=0; i<pg->numV; i++)
    {
        printf("%c와 연결된 정점: ", i + 65);

        if(LFirst(&(pg->adjList[i]), &vx));
        {
            printf("%c ", vx + 65);

            while(LNext(&(pg->adjList[i]), &vx))
                printf("%c ", vx + 65);
        }

        printf("\n");
    }
}

//visitV에 방문
int VisitVertex(ALGraph * pg, int visitV)
{
    if (pg->visitInfo[visitV] == 0) //처음 방문하면 TRUE
    {
        pg->visitInfo[visitV] = 1;  //방문했으니 FALSE
        printf("%c ", visitV + 65);
        return TRUE;
    }
    return FALSE;
}

//정점의 정보 출력: DFS 기반
void DFShowGraphVertex(ALGraph * pg, int startV)
{
    Stack stack;
    int visitV = startV;
    int nextV;

    StackInit(&stack);
    VisitVertex(pg, visitV);
    SPush(&stack, visitV);

    while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)   //첫 정점에 연결된 정점 방문
    {
        int visitFlag = FALSE;

        if(VisitVertex(pg, nextV) == TRUE)
        {
            SPush(&stack, visitV);
            visitV = nextV;
            visitFlag = TRUE;
        }
        else
        {
            while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE)    //첫 시도가 이미 방문한 상태인 경우 다른 정점 방문
            {
                if(VisitVertex(pg, nextV) == TRUE)
                {
                    SPush(&stack, visitV);
                    visitV = nextV;
                    visitFlag = TRUE;
                    break;
                }
            }
        }

        if(visitFlag == FALSE)  //현재 정점에 연결된 모든 정점이 모두 방문한 상태인 경우
        {
            if(SIsEmpty(&stack) == TRUE)    //시작점으로 돌아온 경우
                break;
            else
                visitV = SPop(&stack);      //왔던 길 되돌아가는 과정
        }
    }

    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

int WhoIsPrecede(int data1, int data2)
{
    if(data1 < data2)
        return 0;
    else
        return 1;
}

 

 파일명: DFSMain.c

#include <stdio.h>
#include "ALGraphDFS.h"

int main(void)
{
    ALGraph graph;
    GraphInit(&graph, 7);

    AddEdge(&graph, A, B);
    AddEdge(&graph, A, D);
    AddEdge(&graph, B, C);
    AddEdge(&graph, D, C);
    AddEdge(&graph, D, E);
    AddEdge(&graph, E, F);
    AddEdge(&graph, E, G);

    ShowGraphEdgeInfo(&graph);

    DFShowGraphVertex(&graph, A);
    printf("\n");
    DFShowGraphVertex(&graph, C);
    printf("\n");
    DFShowGraphVertex(&graph, E);
    printf("\n");
    DFShowGraphVertex(&graph, G);
    printf("\n");

    GraphDestory(&graph);

    return 0;
}
A와 연결된 정점: B D 
B와 연결된 정점: A C 
C와 연결된 정점: B D 
D와 연결된 정점: A C E 
E와 연결된 정점: D F G 
F와 연결된 정점: E
G와 연결된 정점: E
A B C D E F G
C B A D E F G
E D A B C F G
G E D A B C F

>> WhoIsPrecede 함수 정의를 바꾸면, 현재 위치에서 다음 위치로 이동하는 순서를 조정할 수 있다.

 

 

너비 우선 탐색

너비 우선 탐색(Breadth First Search: BFS)의 핵심은 다음 두 가지이다.

 

- 탐색을 진행할 때, 현재 정점과 연결된 모든 정점을 방문한다.
- 방문이 먼저 진행된 정점에서 먼저 탐색을 진행한다.

 

너비 우선 탐색의 구현

  • BFS의 구현을 위해서는 큐, 배열 두 가지가 필요하다.
  • 큐 - 방문 차례의 기록 목적으로 한다.
  • 배열 - 방문 정보의 기록을 목적으로 한다.
  • Chapter 07에서 구현한 CircularQueue.h  CircularQueue.c을 이용한다.
  • Chapter 04에서 구현한 DLinkedList.h  DLinkedList.c을 이용한다.

BFS의 구조

 

 파일명: ALGraphBFS.h

#ifndef __AL_GRAPG_BFS__
#define __AL_GRAPG_BFS__

#include "DLinkedList.h"

enum {A, B, C, D, E, F, G, H, I, J};

typedef struct _ual
{
    int numV;
    int numE;
    List * adjList;
    int * visitInfo;    
} ALGraph;

void GraphInit(ALGraph * pg, int nv);

void GraphDestory(ALGraph * pg);

void AddEdge(ALGraph * pg, int fromV, int toV);

void ShowGraphEdgeInfo(ALGraph * pg);

//정점의 정보 출력: BFS 기반
void BFShowGraphVertex(ALGraph * pg, int startV);

#endif

 

 파일명: ALGraphBFS.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DLinkedList.h"
#include "ALGraphBFS.h"
#include "CircularQueue.h"

int WhoIsPrecede(int data1, int data2);

void GraphInit(ALGraph * pg, int nv)
{
    int i;

    pg->adjList = (List*)malloc(sizeof(List)*nv);
    pg->numE = 0;
    pg->numV = nv;

    for(i=0; i<nv; i++)
    {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
    }

    pg->visitInfo = (int*)malloc(sizeof(int) * (pg->numV));

    memset(pg->visitInfo, 0, sizeof(int) * (pg->numV));
}

void GraphDestory(ALGraph * pg)
{
    if(pg->adjList != NULL)
        free(pg->adjList);
    
    if(pg->visitInfo != NULL)
        free(pg->visitInfo);
}

void AddEdge(ALGraph * pg, int fromV, int toV)
{
    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);

    pg->numE +=1;
}

void ShowGraphEdgeInfo(ALGraph * pg)
{
    int i;
    int vx;

    for(i=0; i<pg->numV; i++)
    {
        printf("%c와 연결된 정점: ", i + 65);

        if(LFirst(&(pg->adjList[i]), &vx));
        {
            printf("%c ", vx + 65);

            while(LNext(&(pg->adjList[i]), &vx))
                printf("%c ", vx + 65);
        }

        printf("\n");
    }
}

//visitV에 방문
int VisitVertex(ALGraph * pg, int visitV)
{
    if (pg->visitInfo[visitV] == 0) //처음 방문하면 TRUE
    {
        pg->visitInfo[visitV] = 1;  //방문했으니 FALSE
        printf("%c ", visitV + 65);
        return TRUE;
    }
    return FALSE;
}

//정점의 정보 출력: DFS 기반
void BFShowGraphVertex(ALGraph * pg, int startV)
{
    Queue queue;
    int visitV = startV;
    int nextV;

    QueueInit(&queue);

    VisitVertex(pg, visitV);

    while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)   //첫 정점에 연결된 정점 방문
    {
        if(VisitVertex(pg, nextV) == TRUE)
            Enqueue(&queue, nextV);

        while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE)
        {
            if(VisitVertex(pg, nextV) == TRUE)
                Enqueue(&queue, nextV);
        }

        if (QIsEmpty(&queue) == TRUE)
            break;
        else
            visitV = Dequeue(&queue);
    }


    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

int WhoIsPrecede(int data1, int data2)
{
    if(data1 < data2)
        return 0;
    else
        return 1;
}

 

 파일명: BFSMain.c

#include <stdio.h>
#include "ALGraphBFS.h"

int main(void)
{
    ALGraph graph;
    GraphInit(&graph, 7);

    AddEdge(&graph, A, B);
    AddEdge(&graph, A, D);
    AddEdge(&graph, B, C);
    AddEdge(&graph, D, C);
    AddEdge(&graph, D, E);
    AddEdge(&graph, E, F);
    AddEdge(&graph, E, G);

    ShowGraphEdgeInfo(&graph);

    BFShowGraphVertex(&graph, A);
    printf("\n");
    BFShowGraphVertex(&graph, C);
    printf("\n");
    BFShowGraphVertex(&graph, E);
    printf("\n");
    BFShowGraphVertex(&graph, G);
    printf("\n");

    GraphDestory(&graph);

    return 0;
}
A와 연결된 정점: B D 
B와 연결된 정점: A C 
C와 연결된 정점: B D 
D와 연결된 정점: A C E 
E와 연결된 정점: D F G 
F와 연결된 정점: E
G와 연결된 정점: E
A B D C E F G
C B D A E F G
E D F G A C B
G E D F A C B

 

 

최소 비용 신장 트리

단순경로와 사이클

  • 경로(path): 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 의미한다.
  • 단순 경로(simple path): 동일한 간선을 중복하여 포함하지 않는 경로를 의미한다.
  • 사이클(cycle): 시작과 끝이 같은 단순 경로를 의미한다.
  • 신장 트리(spanning tree): 사이클을 형성하지 않는 그래프를 의미한다.

단순 경로, 사이클과 신장 트리

 

최소 비용 신장 트리

 신장 트리는 다음 두 가지의 특징을 가진다.

- 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
- 그래프 내에서 사이클을 형성하지 않는다.

 

  • 최소 비용 신장 트리(minimum cost spanning tree): 신장 트리의 모든 간선 가중치 합이 최소인 그래프를 의미한다.

최소 신장 트리

 

 최소 비용 신장 트리의 구성에 사용되는 대표적인 알고리즘 두 가지는 다음과 같다.

  • 크루스칼(Kruskal) 알고리즘: 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 혹은 삭제해나가는 방식
  • 프림(Prim) 알고리즘: 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

 

크루스칼 알고리즘의 이해

  • 크루스칼 알고리즘은 정렬을 어떻게 하는지에 따라 방식이 달라진다.
  • 그래프는 간선의 수 + 1 = 정점의 수 조건을 만족한다.
가중치를 기준으로 간선을 오름차순으로 정렬하는 경우
1. 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.
2. 사이클을 형성하는 간선을 추가하지 않는다.
3. 간선의 수가 정점의 수보다 하나 적을 때 MST 완성

오름차순으로 정렬하는 경우

 

가중치를 기준으로 간선을 내림차순으로 정렬하는 경우
1. 낮은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거한다.
2. 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않는다.
3. 간선의 수가 정점의 수보다 하나 적을 때 MST 완성

내림차순으로 정렬하는 경우

 

크루스칼 알고리즘의 구현

  • Chapter 09에서 구현한 우선순위 큐를 활용하기 위해 PriorityQueue.h, PriorityQueue.c
  • 우선순위 큐의 기반이 되는 힙을 활용하기 위해 UsefulHeap.h, UsefulHeap.c
  • 연결 리스트 활용을 위해 DLinkedList.h, DLinkedList.c
  • 배열 기반 스택 활용을 위해 ArrayBaseStack.h, ArrayBaseStack.c

 파일명: ALEdge.h

#ifndef __AL_EDGE__
#define __AL_EDGE__

typedef struct _edge
{
    int v1;
    int v2;
    int weight;
} Edge;

#endif

>> 간선의 가중치 정보 저장

 

 파일명: ALGraphKrukal.h

#ifndef __AL_GRAPG_DFS__
#define __AL_GRAPG_DFS__

#include "DLinkedList.h"
#include "PriorityQueue.h"
#include "ALEdge.h"

enum {A, B, C, D, E, F, G, H, I, J};

typedef struct _ual
{
    int numV;
    int numE;
    List * adjList;
    int * visitInfo;  
    PQueue pqueue;  //간선의 가중치 정보 저장
} ALGraph;

void GraphInit(ALGraph * pg, int nv);

void GraphDestory(ALGraph * pg);

void AddEdge(ALGraph * pg, int fromV, int toV, int weight);

void ShowGraphEdgeInfo(ALGraph * pg);

void DFShowGraphVertex(ALGraph * pg, int startV);

//최소 비용 신장 트리의 구성
void ConKruskalMST(ALGraph * pg);

void ShowGraphEdgeWeightInfo(ALGraph * pg);

#endif

 

 파일명: ALGraphKrukal.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DLinkedList.h"
#include "ALGraphKruskal.h"
#include "ArrayBaseStack.h"

int WhoIsPrecede(int data1, int data2);
int PQWeightComp(Edge d1, Edge d2);

void GraphInit(ALGraph * pg, int nv)
{
    int i;

    pg->adjList = (List*)malloc(sizeof(List)*nv);
    pg->numE = 0;
    pg->numV = nv;

    for(i=0; i<nv; i++)
    {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
    }

    pg->visitInfo = (int*)malloc(sizeof(int) * (pg->numV));

    memset(pg->visitInfo, 0, sizeof(int) * (pg->numV));

    PQueueInit(&(pg->pqueue), PQWeightComp);
}

void GraphDestory(ALGraph * pg)
{
    if(pg->adjList != NULL)
        free(pg->adjList);
    
    if(pg->visitInfo != NULL)
        free(pg->visitInfo);
}

void AddEdge(ALGraph * pg, int fromV, int toV, int weight)
{
    Edge edge = {fromV, toV, weight};

    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);

    pg->numE +=1;

    PEnqueue(&(pg->pqueue), edge);
}

void RemoveWayEdge(ALGraph * pg, int fromV, int toV)    //한쪽 방향의 간선 소멸
{
    int edge;

    if(LFirst(&(pg->adjList[fromV]), &edge))
    {
        if(edge == toV)
        {
            LRemove(&(pg->adjList[fromV]));
            return;
        }

        while(LNext(&(pg->adjList[fromV]), &edge))
        {
            if(edge == toV)
            {
                LRemove(&(pg->adjList[fromV]));
                return;
            }
            
        }
    }
}

void RemoveEdge(ALGraph * pg, int fromV, int toV)   //간선의 소멸
{
    RemoveWayEdge(pg, fromV, toV);
    RemoveWayEdge(pg, toV, fromV);
    (pg->numE)--;
}

void RecoverEdge(ALGraph * pg, int fromV, int toV, int weight)
{
    LInsert(&(pg->adjList[fromV]), toV);
    LInsert(&(pg->adjList[toV]), fromV);
    (pg->numE)++;
}

int VisitVertex(ALGraph * pg, int visitV)
{
    if (pg->visitInfo[visitV] == 0) 
    {
        pg->visitInfo[visitV] = 1;  
        //printf("%c ", visitV + 65);
        return TRUE;
    }
    return FALSE;
}

int IsConnVertex(ALGraph * pg, int v1, int v2)
{
    Stack stack;
    int visitV = v1;
    int nextV;

    StackInit(&stack);
    VisitVertex(pg, visitV);
    SPush(&stack, visitV);

    while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)   
    {
        int visitFlag = FALSE;

        //정점을 돌아다니는 도중 목표를 찾으면 TRUE 반환
        if(nextV == v2)
        {
            memset(pg->visitInfo, 0, sizeof(int)*pg->numV);
            return TRUE;
        }

        if(VisitVertex(pg, nextV) == TRUE)
        {
            SPush(&stack, visitV);
            visitV = nextV;
            visitFlag = TRUE;
        }
        else
        {
            while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE)    //첫 시도가 이미 방문한 상태인 경우 다른 정점 방문
            {
                if (nextV == v2)
                {
                    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
                    return TRUE;
                }

                if(VisitVertex(pg, nextV) == TRUE)
                {
                    SPush(&stack, visitV);
                    visitV = nextV;
                    visitFlag = TRUE;
                    break;
                }
            }
        }

        if(visitFlag == FALSE)  //현재 정점에 연결된 모든 정점이 모두 방문한 상태인 경우
        {
            if(SIsEmpty(&stack) == TRUE)    //시작점으로 돌아온 경우
                break;
            else
                visitV = SPop(&stack);      //왔던 길 되돌아가는 과정
        }
    }

    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
    return FALSE;   //목표를 찾지 못함 -> 연결되지 않음
}

void ShowGraphEdgeInfo(ALGraph * pg)
{
    int i;
    int vx;

    for(i=0; i<pg->numV; i++)
    {
        printf("%c와 연결된 정점: ", i + 65);

        if(LFirst(&(pg->adjList[i]), &vx));
        {
            printf("%c ", vx + 65);

            while(LNext(&(pg->adjList[i]), &vx))
                printf("%c ", vx + 65);
        }

        printf("\n");
    }
}

void DFShowGraphVertex(ALGraph * pg, int startV)
{
    Stack stack;
    int visitV = startV;
    int nextV;

    StackInit(&stack);
    VisitVertex(pg, visitV);
    SPush(&stack, visitV);

    while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)   //첫 정점에 연결된 정점 방문
    {
        int visitFlag = FALSE;

        if(VisitVertex(pg, nextV) == TRUE)
        {
            SPush(&stack, visitV);
            visitV = nextV;
            visitFlag = TRUE;
        }
        else
        {
            while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE)    //첫 시도가 이미 방문한 상태인 경우 다른 정점 방문
            {
                if(VisitVertex(pg, nextV) == TRUE)
                {
                    SPush(&stack, visitV);
                    visitV = nextV;
                    visitFlag = TRUE;
                    break;
                }
            }
        }

        if(visitFlag == FALSE)  //현재 정점에 연결된 모든 정점이 모두 방문한 상태인 경우
        {
            if(SIsEmpty(&stack) == TRUE)    //시작점으로 돌아온 경우
                break;
            else
                visitV = SPop(&stack);      //왔던 길 되돌아가는 과정
        }
    }

    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

void ConKruskalMST(ALGraph * pg)
{
    Edge recvEdge[20];  //복원할 간선 정보 저장
    Edge edge;
    int eidx = 0;
    int i;

    while(pg->numE+1 > pg->numV)    //MST 간선의 수 + 1 = 정점의 수
    {
        edge = PDequeue(&(pg->pqueue));     //가중치가 가장 높은 간선부터 순서대로 꺼낸다.
        RemoveEdge(pg, edge.v1, edge.v2);

        if(!IsConnVertex(pg, edge.v1, edge.v2))     //간선을 삭제하고 나서 두 정점을 연결하는 경로가 있는지 확인
        {
            RecoverEdge(pg, edge.v1, edge.v2, edge.weight); //우선순위 큐에 다시 넣지 않는 이유는, 한 번 검토한 간선은 재검토하지 않기 위해서
            recvEdge[eidx++] = edge;
        }
    }

    for(i=0; i<eidx; i++)
        PEnqueue(&(pg->pqueue), recvEdge[i]);
}

void ShowGraphEdgeWeightInfo(ALGraph * pg)
{
    PQueue copyPQ = pg->pqueue;
    Edge edge;

    while(!PQIsEmpty(&copyPQ))
    {
        edge = PDequeue(&copyPQ);
        printf("(%c-%c), w:%d \n", edge.v1+65, edge.v2+65, edge.weight);
    }
}

int WhoIsPrecede(int data1, int data2)
{
    if(data1 < data2)
        return 0;
    else
        return 1;
}

int PQWeightComp(Edge d1, Edge d2)
{
    return d1.weight - d2.weight;
}

>> RemoveEdge, IsConnVertex, RecoverEdge는 ConFrukalMST에서 활용하기 위해 새로 선언 및 정의하는 함수

  • RemoveEdge: 그래프에서 간선을 삭제
  • IsConnVertex: 두 정점이 연결되어 있는지 확인
  • RecoverEdge: 삭제된 간선을 다시 삽입

 

 파일명: KrukalMain.c

#include <stdio.h>
#include "ALGraphKruskal.h"

int main(void)
{
    ALGraph graph;
    GraphInit(&graph, 6);

    AddEdge(&graph, A, B, 9);
    AddEdge(&graph, B, C, 2);
    AddEdge(&graph, A, C, 12);
    AddEdge(&graph, A, D, 8);
    AddEdge(&graph, D, C, 6);
    AddEdge(&graph, A, F, 11);
    AddEdge(&graph, F, D, 4);
    AddEdge(&graph, D, E, 3);
    AddEdge(&graph, E, C, 7);
    AddEdge(&graph, F, E, 13);

    ConKruskalMST(&graph);      
    ShowGraphEdgeInfo(&graph);
    ShowGraphEdgeWeightInfo(&graph);

    GraphDestory(&graph);

    return 0;
}
A와 연결된 정점: D 
B와 연결된 정점: C 
C와 연결된 정점: B D 
D와 연결된 정점: A C E F 
E와 연결된 정점: D 
F와 연결된 정점: D
(A-D), w:8
(D-C), w:6
(F-D), w:4
(D-E), w:3
(B-C), w:2

 

  • 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11

'Data Structure & Algorithm > Data Structure' 카테고리의 다른 글

[Data Structure] Chapter 13-2: 충돌(Collision) 문제의 해결책  (0) 2023.09.18
[Data Structure] Chapter 13-1: 빠른 탐색을 보이는 해쉬 테이블  (0) 2023.09.17
[Data Structure] Chapter 12: 균형 잡힌 이진 탐색 트리 - AVL 트리  (0) 2023.09.13
[Data Structure] Chapter 11-2: 이진 탐색 트리  (0) 2023.09.12
[Data Structure] Chapter 11-1: 탐색의 이해와 보간 탐색  (0) 2023.09.11
'Data Structure & Algorithm/Data Structure' Related Articles more