프로그래밍에서 그래프(Graph)를 표현하는 방법

프로그래밍에서 그래프(Graph)를 표현하는 방법

그래프 (Graph)

그래프란 정점(Vertex)과 간선(Edge)으로 구성하는 자료구조를 뜻한다.

알고리즘 문제를 풀기 위해 반드시 알아두어야 할 자료구조 중 하나가 바로 “그래프”이다. 그래프의 대표적인 알고리즘에는 DFS(Deep First Search) / BFS(Breath First Serarch)가 있다.

이와 같은 알고리즘을 사용하기 위해 그래프를 표현하는 방법을 우선 알아야 할 것 같아 글로 남기려고 한다. 그래프를 표현하는 방법은 크게 두 가지라고 한다.

 

그래프 표현 방법

인접행렬(Adjacency Matrix)

인접행렬
인접행렬

위 그림과 같이 행렬에 그래프를 표현하는 “인접행렬”방식이 있다. 그림에서는 정점(Vertex)가 알파벳이지만, 프로그래밍에서 각 행렬을 숫자로 표현, 이를 2차원 배열에 넣으면 위와 같이 표현이 될 것이다.

또한, 0과 1이 아닌, 어떠한 값을 넣는다면 “가중치(Weight)” 표현도 가능하다.

인접행렬의 장점은 간단하게 구현이 가능하며(단순 배열) CRUD에 있어 뒤에 소개할 “인접 리스트”보다 속도면에서 빠를 것이다. 하지만 정적(Static)이며, 필요 없는 공간도 많아 메모리 효율에는 좋지 않을 것이다.

인접리스트(Adjacency list)

Adjacency list
Adjacency list

Linked list 에 그래프를 표현한 것이 “인접 리스트” 이다. 맨 앞의 정점은 다음 정점의 Pointer를 가지며, 그림에서는 표현이 안되어 있지만 “가중치”를 넣어 표현하는 것 또한 가능하다.

장/단점은 “인접행렬”과 반대이다. 메모리 효율이 좋은 대신 CRUD의 속도가 행렬을 사용한 것 보다 좋지는 않다. 프로그래밍 언어에 따라 Linked list를 구현해서 사용해야 할 수도 있다.

 

C 에서 구현

구현은 위의 “인접리스트”의 그림에 나온 그래프를 예시로 구현해본다.

인접리스트

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/*
그래프 표현(인접행렬)
  1. 정점 : 8개 (9*9 배열 필요)
*/
#define _VERTEX_ 9

void initMatrix(int **matrix)
{
    int i, j;

    for(i=0 ; i<_VERTEX_ ; i++)
    {
        for(j=0 ; j<_VERTEX_ ; j++)
        {
            if(i==0)
            {
                matrix[i][j] = j;
            }
            else if(j==0)
            {
                matrix[i][j] = i;
            }
            else
            {
                matrix[i][j] = 0;
            }
        }
    }
    return;
}
void addVertex(int **matrix, int vertex1, int vertex2)
{
    int **adMatrix = matrix;
    adMatrix[vertex1][vertex2] = 1;
    return;
}
void delVertex(int **matrix, int vertex1, int vertex2)
{
    int **adMatrix = matrix;
    adMatrix[vertex1][vertex2] = 0;

    return;
}
void outMatrix(int **matrix)
{
    int i, j;

    for(i=0 ; i<_VERTEX_ ; i++)
    {
        for(j=0 ; j<_VERTEX_ ; j++)
        {
            printf("%4d ", matrix[i][j]);
        }
        puts("");
    }

    return;
}

int main(int argc, char *argv[])
{
    int i;

    int **adMatrix = NULL;
    adMatrix = (int**)malloc(sizeof(int*)*_VERTEX_);

    for(i=0 ; i<_VERTEX_ ; i++)
    {
        adMatrix[i] = (int*)malloc(sizeof(int)*_VERTEX_);
    }

    initMatrix(adMatrix);
    
    addVertex(adMatrix, 1, 2);
    addVertex(adMatrix, 1, 3);

    addVertex(adMatrix, 2, 1);
    addVertex(adMatrix, 2, 4);
    
    addVertex(adMatrix, 3, 1);
    addVertex(adMatrix, 3, 4);
    
    addVertex(adMatrix, 4, 2);
    addVertex(adMatrix, 4, 3);
    addVertex(adMatrix, 4, 5);

    addVertex(adMatrix, 5, 4);
    addVertex(adMatrix, 5, 6);
    addVertex(adMatrix, 5, 7);
    addVertex(adMatrix, 5, 8);
    
    addVertex(adMatrix, 6, 5);
    addVertex(adMatrix, 6, 7);
    
    addVertex(adMatrix, 7, 5);
    addVertex(adMatrix, 7, 6);
    addVertex(adMatrix, 7, 8);

    addVertex(adMatrix, 8, 5);
    addVertex(adMatrix, 8, 7);

    outMatrix(adMatrix);

    return 0;
}

구현이 빠르고 생각하는 대로 막 짜도 아무 애러 없이 잘 보여준다.

인접리스트

C는 Linked list 개념이 없어 Struct로 구현해주면 된다.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define _VERTEX_ 9

typedef struct adList_s 
{
    int vertex;
    int weight;
    struct adList_s *nextPtr;
} adList_t;

adList_t **initList()
{
    int i;

    adList_t **adList= (adList_t**)malloc(sizeof(adList_t*)*_VERTEX_);
    for(i=0 ; i<_VERTEX_ ; i++)
    {
        adList[i] = (adList_t*)malloc(sizeof(adList_t));
        adList[i][0].vertex = i;
    }

    return adList;
}

void addVertex(adList_t **adList, int vertex1, int vertex2)
{
    adList_t *tmp = (adList_t*)malloc(sizeof(adList_t));
    tmp->vertex = vertex2;

    if(adList[vertex1]->nextPtr == NULL)
    {
        tmp->nextPtr = NULL;
        adList[vertex1]->nextPtr = tmp;
    }
    else
    {
        tmp->nextPtr = adList[vertex1]->nextPtr;
        adList[vertex1]->nextPtr = tmp;
    }
    
    adList[vertex1]->nextPtr = tmp;

    return;
}

void outMatrix(adList_t **list)
{
    int i;
    adList_t *tmp = NULL;

    for(i=0 ; i<_VERTEX_ ; i++)
    {
        tmp = list[i];
        while(tmp != NULL)
        {
            printf("%d ", tmp->vertex);
            tmp = tmp->nextPtr;
        }
        puts("");
    }

    return;
}

int main()
{
    adList_t **list = initList();

    addVertex(list, 1, 2);
    addVertex(list, 1, 3);

    addVertex(list, 2, 1);
    addVertex(list, 2, 4);
    
    addVertex(list, 3, 1);
    addVertex(list, 3, 4);
    
    addVertex(list, 4, 2);
    addVertex(list, 4, 3);
    addVertex(list, 4, 5);

    addVertex(list, 5, 4);
    addVertex(list, 5, 6);
    addVertex(list, 5, 7);
    addVertex(list, 5, 8);
    
    addVertex(list, 6, 5);
    addVertex(list, 6, 7);
    
    addVertex(list, 7, 5);
    addVertex(list, 7, 6);
    addVertex(list, 7, 8);

    addVertex(list, 8, 5);
    addVertex(list, 8, 7);

    outMatrix(list);

    return 0;
}

정말 간단하게 구현했으며, 간단하게 구현했는데도 불구하고 2~3번의 Memory segment error를 구경할 수 있으며, 중복으로 Insert 되는 경우도 생각하여 코딩해야 할 것 같다.

%d 블로거가 이것을 좋아합니다: