[Data Structure] 그래프(graph)

---

그래프

 

 

연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 트리 역시 그래프의 특수한 형태이다.

다음은 그래프의 기본적인 용어이다.

• 정점(vertex) 혹은 노드(node): 각 객체
• 간선(edge) 혹은 링크(link): 각 정점을 연결하는 선 혹은 관계
• 부분 그래프(sub graph): 어떤 그래프의 정점과 간선의 부분집합으로 이루어진 그래프
• 인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점
• 차수(degree): 무방향 그래프에서 하나의 정점에 연결된 다른 정점의 수
• 진입 차수(in-degree): 방향 그래프에서 하나의 정점으로 오는 간선의 수
• 진출 차수(out-degree): 방향 그래프에서 하나의 정점에서 외부로 향하는 간선의 수
• 경로(path): 한 정점에서 다른 정점으로 이동할 때 거쳐가는 정점의 순서
• 경로 길이(path length): 경로를 구성하는 데에 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 간선이 없는 경로
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경로

 

---

종류

 

• 방향 그래프(directed graph) 및 무방향 그래프(undirected graph)

그래프는 크게 방향 그래프와 무방향 그래프 나눌 수 있는데, 간선이 방향성을 가진다면 방향 그래프, 가지지 않는다면 무방향 그래프이다. 아래 그림 중 왼쪽이 무방향 그래프, 오른쪽이 방향 그래프이다.

 

• 부분 그래프(sub graph)

어떤 그래프의 정점과 간선의 부분집합으로 이루어진 그래프이다. 아래 그림 왼쪽 그래프의 부분 그래프 중 하나가 오른쪽 그래프이다.

 

• 가중 그래프(weighted graph)

간선에 비용(cost) 혹은 가중치(weight)가 할당된 그래프이다.

 

• 연결 그래프(connected graph) 및 비연결 그래프(disconnected graph)

연결 그래프는 모든 정점들이 간선에 의해 연결되어 있는 그래프이고, 비연결 그래프는 연결되지 않은 두 정점이 존재하는 그래프이다. 아래 그림 중 왼쪽이 연결 그래프, 오른쪽이 비연결 그래프이다.

 

• 비순환 그래프(acyclic graph)

사이클이 없는 그래프이다.

 

• 완전 그래프(complete graph)

모든 정점이 연결되어 있는 그래프이다.

 

---

구현 | C

 

인접행렬(adjacent matrix)과 인접 리스트(adjacency list)를 이용하여 구현할 수 있다.

인접행렬을 이용하는 경우 인접행렬이 $ A = \left[ a_{m \times n} \right] $ 일 때 $ i $ 에서 $ j $ 로 가는 간선이 그래프에 존재하는 경우 $ a_{ij} = 1 $, 존재하지 않는 경우 $ a_{ij} = 0 $ 으로 값을 대입하는 방식이다. 무방향 그래프에서 $ i $ 와 $ j $ 가 연결되어 있다면 $ a_{ij} =1, a_{ji} = 1 $ 이다.

위 그래프를 인접행렬로 나타내면 아래와 같다.

$$ \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} $$

C 에서는 2차원 배열로 구현하면 된다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50

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

void init(Graph* 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(Graph* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "Number of graph vertices exceeded");
        return;
    }
    g->n++;
}

void insert_edge(Graph* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "Graph vertex number error");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

행렬로 구현하면 인접 리스트를 통한 구현보다 일반적으로 효율적이지 못하다. 단 간선이 많이 존재하는 밀집 그래프(dense graph)인 경우나 정점의 차수를 빠르게 구해야 하는 경우 효율적일 수 있다.

인접 리스트로 구현하는 경우 각 정점에 인접한 정점들을 연결 리스트로 표현한다. 예를 들어 0이 1, 2, 3 과 연결되어 있다면 0 이 1인 노드를 가리키고, 1인 노드가 2인 노드를 가리키고, 2인 노드가 3인 노드를 가리키고, 3인 노드는 NULL을 가리킨다. 같은 방식으로 모든 정점에 대해서 리스트를 만들면 된다.

보다 구체적인 예시를 위해 위 그래프를 인접 리스트로 나타내면 아래와 같다.

인접한 노드를 쉽게 찾을 수 있고, 그래프의 존재하는 모든 간선의 수를 확인하는 시간복잡도가 $ \mathcal{O} ( N + E) $ 이므로 일반적으로 인접행렬보다 효율적이다. 그러나 구현이 까다롭고, 정점의 차수를 구하는 것은 인접행렬을 이용하는 방식이 더 효율적이라는 단점도 있다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50

typedef struct Node {
	int vertex;
	struct Node* next;
} Node;

typedef struct Graph {
	int n;
	Node* adj_list[MAX_VERTICES];
} Graph;

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

void insert_vertex(Graph* g, int v) {
    if (g->n + 1 > MAX_VERTICES) {
        fprintf(stderr, "Number of graph vertices exceeded\n");
        return;
    }
    g->n++;
}

void insert_edge(Graph* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "Graph vertex number error\n");
        return;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = end;
    newNode->next = g->adj_list[start];
    g->adj_list[start] = newNode;
    // 무방향 그래프라면 반대 방향도 추가
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = start;
    newNode->next = g->adj_list[end];
    g->adj_list[end] = newNode;
}