안녕하세요. 김용성입니다.
오늘은 그래프에 대한 개념을 설명하고, C로 간단하게 구현을 해보는 시간을 갖도록 하겠습니다.

그래프

그래프하면 어떤 것이 떠오르나요? 초등학교 때 배웠던 막대 그래프? 아니면 고등학교 때 배웠던 x,y축 그래프?
컴퓨터에서 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조를 말합니다.🤗 대표적인 그래프의 예로는 지하철 노선도가 있습니다. 우리는 지하철 노선도에서 여러개의 역들이 어떻게 연결되어있는지 관계를 파악하고 쉽게 최단 경로를 찾을 수가 있죠.

그래프의 종류

그래프의 종류로는 무방향 그래프와 방향 그래프가 있습니다.
이름에서 알 수 있듯이 이 둘은 방향성을 가지고 있느냐, 아니냐로 나누어지게 되는데요. 무방향 그래프의 간선은 간선을 통해 양쪽 방향으로 갈수 있음을 나타내며, 정점 A와 정점 B가 간선을 통해 연결되어있다고 할 때, (A,B)로 나타낼 수가 있죠. 마찬가지로 (B,A)로도 나타낼 수 있기 때문에 (A,B)=(B,A)가 됩니다.
방향 그래프에서의 간선은 단방향성의 성질을 가지고 있어요. 방향 그래프에서의 간선은 '>'를 이용하여 나타내며 <A,B>와 <B,A>는 서로 다른 간선이되죠.

네트워크

간선에 가중치를 할당하게 되면 간선의 역할이 두 정점간의 연결 관계를 나타낼 뿐만 아니라 연결 강도(연결 비용이라던가 연결 거리) 등의 보다 복잡한 관계를 표현할 수가 있습니다. 이렇게 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 혹은 네트워크라 합니다.

위와 같은 그래프를 보면 A와 B 사이의 간선 즉, (A,B)가 5라는 값을 나타내고 있는 것으로 둘 사이 간선의 연결 비용이 5라는 의미를 내포합니다.

정점의 차수

그래프에서 가장 중요한 개념 중 하나라고 말할 수 있는 차수는 특정 정점에서 몇개의 인접 정점에 연결되어 있는지에 대한 개수를 의미합니다. 예를 들어 다음과 같은 그래프가 있다고 가정해봅시다.

위와 같은 그래프에서 A,B,C,D 각각의 차수는 어떻게 될까요?
A=3, B=2, C=2, D=3 이 될 것입니다. 이렇게 구한 차수들의 합을 구하면
10이라는 결과가 나오는데요. 모든 차수의 합은 간선 수의 2배라는 것에 대해 알아두시면 좋습니다.

정점의 차수 총합=간선의 개수*2

(참고로 방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수, 외부로 향하는 간선의 개수를 진출 차수라고 칭합니다.)

사이클

경로 중에서 반복되는 간선이 없을 경우에 이러한 경로를 단순 경로라고 합니다.
위 그림을 살펴보면 A에서 B까지 가는 경로는 A,C,D,B가 있습니다.
만약에 단순 경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클이라 합니다. 위 그림에서는 A,C,D,A를 예로 들 수 있겠네요.

연결 그래프

무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되어 있다고 하며 그래프 G는 연결 그래프라고 부르며 그렇지 않은 그래프를 비연결 그래프라고 합니다.

완전 그래프

그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프라고 합니다. 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n(n-1)x2가 되죠. 만약 완전 그래프에서 n=4라면 간선의 수는 4x3/2=6이 됩니다.
다음 그림과 같은 형태를 우리는 완전 그래프라고 지칭합니다.

C로 그래프 구현

C코드를 통해서 그래프를 구현하기에 앞서 그래프를 추상 데이터 타입으로 정의해보도록 하겠습니다.

• 객체: 정점의 집합과 간선의 집합
• 연산:
  create_graph() ::= 그래프를 생성.
  init(g) ::= 그래프 g를 초기화.
  insert_vertex(g,v) ::= 그래프 g에 정점 v를 추가.
  insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v) 추가.
  delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제.
  delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v) 생성.
  is_empty(g) ::= 그래프 g가 공백 상태인지 확인.
  adgacent(v) ::= 정점 v에 인접한 정점들의 리스트 반환.
  destroy_graph(g) ::= 그래프 g를 제거.

되게 많죠? 그렇지만 속을 들여다보면 간선 추가/삭제, 정점 추가/삭제, 그리고 리스트 반환 등 꼭 필요한 것들만 존재한다고 생각하실거예요.

그래프의 표현 방법

이제 그래프의 표현 방법에 대해서 알아보아야겠죠?
그래프를 표현하는 방법으로는 다음과 같이 두가지의 방법이 존재합니다.

• 인접 행렬: 2차원 배열을 사용하여 그래프를 표현
• 인접 리스트: 연결 리스트를 사용하는 그래프를 표현

위의 두가지 표현 방법은 각각 메모리 사용량과 처리 시간에 대해서 장단점을 가지므로, 문제에 적합한 표현 방법을 선택해야 합니다.

인접 행렬

그래프의 정점 수가 n이라면 nxn의 2차원 배열인 인접 행렬로 나타낼 수가 있어요. 연결되어 있다면 1, 연결되어 있지 않다면 0(자기 자신도)을 넣음으로써 간단하게 나타낼 수 있죠. 다음과 같이 말입니다.

이러한 인접 행렬은 두 정점을 연결하는 간선의 존재 여부를 바로 파악할 수가 있다는 장점이 있습니다. 시간 복잡도로 나타내도 O(1)로 나타낼 수가 있죠. 또한 정점의 차수 또한 O(n)의 시간복잡도로 구할 수가 있습니다. 그러나 만약 정점의 개수에 비해 간선의 수가 너무 적다면 희소 그래프가 되어 메모리의 낭비가 아주 커지게 된다는 단점이 존재합니다.
그러면 이번에는 인접 행렬을 이용하여 간단하게 그래프 코드를 구현해볼까요?

인접행렬 코드

그래프에 관련된 변수들을 하나의 구조체 GraphType에 정리해보도록 하겠습니다.
먼저 그래프에 존재하는 정점의 개수 n이 필요하고, 인접 행렬을 이용하여 구현화려면 또한 크기가 nxn인 2차원 배열인 인접 행렬이 필요합니다. 우리는 인접 행렬의 이름을 adj_mat이라고 하고 이를 정의해보도록 하겠습니다.

그리고 여기서는 정점의 개수를 n, 그리고 해당 구조체를 통해 최대로 정의할 수 있는 그래프의 정점의 개수는 50이라고 가정하겠습니다.

#define MAX_VERTICES 50 // 정점 개수 최대값 정의
typedef struct GraphType{
    int n; // 실 정점의 개수
    int adg_mat[MAX_VERTICES][MAX_VERTICES];
}

물론 이렇게 구현하면 한정된 개수의 정점까지만 그래프에 삽입할 수 있는데요. 동적 배열로 구현한다면 사용자가 정점을 삽입할 때마다 크기를 조정할 수 있게도 만들 수 있습니다. 전체 프로그램은 다음과 같습니다.

인접행렬 그래프 코드

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

#define MAX_VERTICES 50

typedef struct GraphType{
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;


// 그래프 초기화
void init(GraphType* g){
    int r,c;
    g->n=0;
    for(r=0;r<MAX_VERTICES;r++)
        for(c=0;c<MAX_VERTICES;c++)
           g->adj_mat[r][c]=0;
}


//정점 삽입
void insert_vertex(GraphType* g,int v){
    if (((g->n)+1)>MAX_VERTICES){
        fprintf(stderr,"overflow");
        return;
    }
    g->n++;
}

//간선 삽입
void insert_edge(GraphType* g,int start,int end){
    if(start>=g->n||end>=g->n){
        fprintf(stderr,"vertex key error");
        return;
    }
    g->adj_mat[start][end]=1;
    g->adj_mat[end][start]=1;
}

// 인접 행렬 출력 함수
void print_adj_mat(GraphType* g){
    for(int i=0;i<g->n;i++){
        for(int j=0;j<g->n;j++){
            printf("%2d",g->adj_mat[i][j]);
        }
        printf("\n");
    }
}

void main()
{
    GraphType *g;
    g=(GraphType *)malloc(sizeof(GraphType));
    init(g);
    for(int i=0;i<4;i++)
       insert_vertex(g,i);
    insert_edge(g,0,1);
    insert_edge(g,0,2);
    insert_edge(g,0,3);
    insert_edge(g,1,2);
    insert_edge(g,2,3);
    print_adj_mat(g);
    
    free(g);

}

위 main 함수는 제가 위에 올린 그림과 같은 그래프를 만들어 줍니다.
따라서 출력내용은 다음과 같습니다.

0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

인접 리스트

인접 리스트는 그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것입니다. 각 연결 리스트의 노드들은 인접 정점들을 저장하게 되며 각 연결 리스트들은 헤더 노드를 가지고 있고 이 헤더 노드들은 하나의 배열로 구성되어 있습니다. 따라서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근할 수가 있습니다.

인접 행렬과는 다소 다른 부분이 존재하는데, 무방향 그래프를 나타낼 시에 간선 (i,j)를 정의할 때 (j,i)를 한번 더 표현해주어야 합니다. 또한 연결 리스트에 정점들이 입력되는 순서에 따라 연결 리스트 내에서 정점들의 순서가 달라질 수 있습니다.

위 그림을 보면 연결리스트로 정점으로부터의 인접정점들이 담긴 리스트가 생겨나는 것을 볼 수 있습니다.

0->1->2->3 : 3
1->0->2 : 2
2->0->1->3 : 3
3->0->2 : 2

리스트를 추상화한 모습을 보면 정점의 개수가 4개, 간선이 5개인 그래프를 표현하기 위해서는 리스트가 총 4개 그리고 연결된 노드들은 총 10개가 필요함을 확인할 수 있습니다.

이제 인접 리스트를 통한 그래프의 특성을 알아보아야 합니다.
정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프를 표시하기 위해서는 n개의 연결리스트가 필요하고, n개의 헤더 노드와 2e개의 노드가 필요합니다.

이제 인접리스트 그래프를 코드로 표현해보도록 하겠습니다.

인접리스트 그래프 코드

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

#define MAX_VERTICES 50

typedef struct GraphNode{
    int vertex;
    struct GraphNode* link;
} GraphNode;

typedef struct GraphType{
    int n;
    GraphNode* adj_list[MAX_VERTICES];
} GraphType;

void init(GraphType* g){
    int v;
    g->n=0;
    for(v=0;v<MAX_VERTICES;v++)
        g->adj_list[v]=NULL;
}

void insert_vertex(GraphType* g,int v){
    if(((g->n)+1)>MAX_VERTICES){
        fprintf(stderr,"overflow");
        return;
    }
    g->n++;
}

void insert_edge(GraphType* g,int u,int v){
    GraphNode* node;
    if(u>=g->n||v>=g->n){
        fprintf(stderr,"vertex index error");
        return;
    }
    node= (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex=v;
    node->link=g->adj_list[u];
    g->adj_list[u]=node;
}

void print_adj_list(GraphType* g){
    for(int i=0;i<g->n;i++){
        GraphNode* p=g->adj_list[i];
        printf("정점 %d의 인접 리스트",i);
        while(p!=NULL){
            printf("->%d",p->vertex);
            p=p->link;
        }
        printf("\n");
    }
}

int main()
{
    GraphType *g;
    g=(GraphType*)malloc(sizeof(GraphType));
    init(g);
    for(int i=0;i<4;i++)
        insert_vertex(g,i);
    insert_edge(g,0,1);
    insert_edge(g,1,0);
    insert_edge(g,0,2);
    insert_edge(g,2,0);
    insert_edge(g,0,3);
    insert_edge(g,3,0);
    insert_edge(g,1,2);
    insert_edge(g,2,1);
    insert_edge(g,2,3);
    insert_edge(g,3,2);
    print_adj_list(g);

    free(g);

    return 0;


}

실행 결과는 다음과 같습니다.

정점 0의 인접 리스트 -> 3 -> 2 -> 1
정점 1의 인접 리스트 -> 2 -> 0
정점 2의 인접 리스트 -> 3 -> 1 -> 0
정점 3의 인접 리스트 -> 2 -> 0

마무리

오늘은 그래프에 대해서 알아보고, 인접행렬과 인접리스트를 통해 그래프를 구현해보는 포스팅을 진행하였는데요. 제가 처음에 언급했듯이 그래프는 노드 간의 연결관계를 쉽게 파악하고 최단 경로를 찾기 용이합니다. 그렇기에 아무래도 그래프의 백미는 BFS,DFS라고 할 수 있는데요. 다음 자료구조론 포스팅에서는 그래프 탐색 DFS, BFS를 다뤄보도록 하겠습니다.

읽어주셔서 감사합니다:)
☺️