그래프 (Graph)
들어가는 말
그래프(Graph)는 쓰다 또는 그리다를 뜻하는 그리스어 graphein에서 유래한 말이다.
그래프 이론에서 그래프는 여러 대상과 그 관계를 점과 선으로 나타낸 구조를 뜻한다.
그래프와 관련한 유명한 문제로는 쾨니히스베르크의 일곱 다리 문제가 있다.
레온하르트 오일러는 1736년에 육지와 다리를 각각 정점(vertex)과 간선(edge)으로 추상화하여 이 문제를 해결했다.
이 접근은 현대 그래프 이론의 출발점으로 여겨진다.
앞서 우리는 트리를 살펴봤다.
트리도 그래프의 한 종류지만, 하나의 루트를 기준으로 관계가 위에서 아래로 뻗어나가는 계층 구조라는 제약을 가진다.
루트 노드를 제외한 각 노드는 부모 노드를 하나만 가지며, 그 결과 루트에서 각 노드에 도달하는 경로는 언제나 하나뿐이다.
현실의 관계가 언제나 이런 계층 구조로만 이루어져 있지는 않다.
지하철 노선도를 생각해보면, 한 역에서 여러 다른 역으로 이동할 수 있고, 같은 목적지라도 환승 경로에 따라 여러 갈래로 도달할 수 있다.
이는 각 노드의 부모가 하나로 제한되는 트리로는 표현할 수 없는 관계다.
길찾기 역시 마찬가지다.
여러 장소를 잇는 길은 위계 없이 이곳저곳으로 얽혀 있고, 하나의 장소는 여러 갈래의 길과 동시에 연결된다.
컴퓨터 네트워크에서도 하나의 장치는 여러 장치와 동시에 연결되어 정보를 주고받는다.
이러한 연결 관계에는 어떤 장치가 “부모”이고 어떤 장치가 “자식”인지에 대한 위아래 구분이 없다.
그래프는 이처럼 하나의 루트나 정해진 위계 없이, 여러 대상 사이의 복잡한 연결 관계를 자유롭게 표현하는 자료구조다.
트리가 하나의 루트를 중심으로 계층을 이루도록 제약을 둔 특수한 경우라면, 그래프는 그 제약을 걷어낸 더 일반적인 형태라고 할 수 있다.
그래프의 구성 요소
A ----- B
| / |
| / |
| / |
C ----- D정점(Vertex)
자료를 저장하고 다른 대상과 연결 관계를 맺는 기본 단위를 정점이라고 한다.
앞서 트리가 그래프의 한 종류라고 설명했기 때문에, 정점을 보고 노드라고 생각했을 수도 있다.
정점과 노드는 대체로 같은 의미로 쓰이지만, 그래프에서는 정점이라는 용어를 더 자주 사용한다.
그래프 이론은 위상수학(topology)을 비롯한 기하학에서 뻗어 나온 수학의 한 분야라서, 다각형의 꼭짓점을 뜻하는 정점이라는 말이 널리 쓰인다.
간선(Edge)
정점과 정점 사이를 연결하는 선으로, 둘 사이의 관계를 나타낸다.
위 그래프의 간선은 A-B, A-C, B-C, B-D, C-D다.
인접(Adjacent)
하나의 간선으로 직접 연결된 두 정점은 서로 인접했다고 한다.
위 그림에서 A는 B와 C에 인접하지만 D에는 직접 인접하지 않는다.
또한 B와 C도 하나의 간선으로 직접 연결되어 있으므로 서로 인접한다.
차수(Degree)
하나의 정점에 연결된 간선의 수를 그 정점의 차수라고 한다.
위 그림에서 A는 B와 C에 연결되어 있어 차수가 2다.
B는 A, C, D에 연결되어 있고, C는 A, B, D에 연결되어 있어 둘의 차수는 3이다.
D는 B와 C에 연결되어 있어 차수가 2다.
경로(Path)
간선을 따라 한 정점에서 다른 정점으로 이동할 때 거치는 정점들의 순서를 경로라고 한다.
예를 들어 A에서 D로 가는 경로에는 A → B → D와 A → C → D가 있다.
경로에 포함된 간선의 수를 경로의 길이라고 하며, 두 경로의 길이는 모두 2다.
사이클(Cycle)
한 정점에서 출발해 시작 정점으로 되돌아오기 전까지 같은 정점이나 간선을 반복하지 않는 닫힌 경로를 사이클이라고 한다.
위 그림의 A → B → C → A는 사이클이다.
트리는 사이클을 허용하지 않는 그래프다.
그래프의 종류
무방향 그래프(Undirected Graph)
A ----- B간선에 방향이 없는 그래프다.
A에서 B로 이동할 수 있으며, B에서 A로도 이동할 수 있다.
방향 그래프(Directed Graph)
A -----> B간선에 방향이 있는 그래프다.
A에서 B로는 이동할 수 있지만, B에서 A로는 이동할 수 없다.
가중치 그래프(Weighted Graph)
(10)
A -------- B
\ /
(3) \ / (5)
\ /
C간선에는 비용, 거리, 시간 등을 나타내는 수치인 가중치(Weight)가 부여될 수 있다.
가중치 그래프는 무방향 그래프일 수도, 방향 그래프일 수도 있다.
그래프의 구현 방법
그래프를 표현하는 대표적인 방법으로는 인접 행렬과 인접 리스트가 있다.
그래프의 규모와 자주 수행할 연산에 따라 적합한 방식이 달라지며, 메모리 사용량에도 차이가 생긴다.
인접 행렬(Adjacency Matrix)
인접 행렬은 정점 사이의 간선 정보를 2차원 배열에 저장하는 방식이다.
행은 출발 정점, 열은 도착 정점을 나타내며, 두 정점 사이에 간선이 있으면 해당 위치에 값을 저장한다.
인접 행렬은 두 정점이 연결되었는지 O(1) 시간에 바로 확인할 수 있다.
반면 정점이 V개이면 간선 수와 관계없이 V × V 크기의 배열이 필요하므로 공간 복잡도는 O(V²)다.
따라서 간선이 많은 밀집 그래프에 적합하다.
무방향 그래프
A ----- B
| |
C ----- D| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
무방향 그래프에서는 두 정점이 양방향으로 연결되므로 A와 B가 연결되어 있으면 A행 B열과 B행 A열의 값은 모두 1이다.
방향 그래프
A -----> B
| |
| |
v v
C <----- D| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 0 | 1 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 1 | 0 |
방향 그래프에서는 간선의 방향에 따라 행렬의 값을 각각 저장한다.
A에서 B로 향하는 간선은 있으므로 A행 B열은 1이지만, B에서 A로 향하는 간선은 없으므로 B행 A열은 0이다.
인접 리스트(Adjacency List)
인접 리스트는 각 정점에 연결된 정점들을 연결 리스트로 저장하는 방식이다.
정점 수를 V, 간선 수를 E라고 하자.
인접 리스트는 실제로 존재하는 간선만 저장하므로 공간 복잡도가 O(V + E)다.
하지만 두 정점이 연결되었는지 확인하려면 한 정점의 인접 리스트를 탐색해야 한다.
간선이 적은 희소 그래프에서는 인접 리스트가 보통 더 효율적이다.
무방향 그래프
A ----- B
| |
C ----- DA: B -> C
B: A -> D
C: A -> D
D: B -> C방향 그래프
A -----> B
| |
| |
v v
C <----- DA: B -> C
B: D
C:
D: C인접 행렬과 인접 리스트 비교하기
두 구현의 방문 순서와 재귀 호출 흐름은 같다.
달라지는 부분은 그래프를 저장하는 방식과 다음에 방문할 정점을 찾는 방법이다.
그래프에 있는 정점의 수는 V, 정점 사이를 잇는 간선의 수는 E로 나타낸다.
| 항목 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 그래프 저장 방식 | V × V 크기의 2차원 배열 |
정점마다 연결된 정점만 저장 |
| 다음 정점 확인 | 모든 정점을 확인 | 실제로 연결된 정점만 확인 |
| DFS 시간 복잡도 | O(V²) |
O(V + E) |
| BFS 시간 복잡도 | O(V²) |
O(V + E) |
| 메모리 사용량 | O(V²) |
O(V + E) |
| 적합한 그래프 | 간선이 많은 그래프 | 간선이 적은 그래프 |
소스 코드
이 글은 그래프 표현 방식에 중점을 두므로 탐색 기법은 다루지 않는다.
main.c
#include "graph_matrix.h"
// #include "graph_list.h"
enum
{
A,
B,
C,
D,
VERTEX_COUNT
};
int main(void)
{
Graph graph;
graph_init(&graph, VERTEX_COUNT);
graph_add_undirected_edge(&graph, A, B);
graph_add_undirected_edge(&graph, A, C);
graph_add_undirected_edge(&graph, B, D);
graph_add_undirected_edge(&graph, C, D);
graph_print(&graph);
graph_destroy(&graph);
return 0;
}인접 행렬
graph_matrix.h
#ifndef GRAPH_MATRIX_H
#define GRAPH_MATRIX_H
#include <stdbool.h>
typedef struct Graph
{
int vertex_count;
int* matrix;
} Graph;
void graph_init(Graph* graph, int vertex_count);
void graph_destroy(Graph* graph);
void graph_add_undirected_edge(Graph* graph, int vertex1, int vertex2);
bool graph_are_adjacent(const Graph* graph, int source, int destination);
void graph_print(const Graph* graph);
#endif /* GRAPH_MATRIX_H */graph_matrix.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph_matrix.h"
void graph_init(Graph* graph, int vertex_count)
{
int matrix_size = vertex_count * vertex_count;
graph->vertex_count = vertex_count;
graph->matrix = malloc(sizeof(int) * matrix_size);
memset(graph->matrix, 0, sizeof(int) * matrix_size);
}
void graph_destroy(Graph* graph)
{
free(graph->matrix);
graph->matrix = NULL;
graph->vertex_count = 0;
}
void graph_add_undirected_edge(Graph* graph, int vertex1, int vertex2)
{
graph->matrix[vertex1 * graph->vertex_count + vertex2] = 1;
graph->matrix[vertex2 * graph->vertex_count + vertex1] = 1;
}
bool graph_are_adjacent(const Graph* graph, int source, int destination)
{
return graph->matrix[source * graph->vertex_count + destination];
}
void graph_print(const Graph* graph)
{
printf(" ");
for (int col = 0; col < graph->vertex_count; ++col)
printf("%c ", 'A' + col);
printf("\n");
for (int row = 0; row < graph->vertex_count; ++row)
{
printf("%c ", 'A' + row);
for (int col = 0; col < graph->vertex_count; ++col)
printf("%d ", graph->matrix[row * graph->vertex_count + col]);
printf("\n");
}
}인접 리스트
graph_list.h
#ifndef GRAPH_LIST_H
#define GRAPH_LIST_H
#include <stdbool.h>
typedef struct VertexNode
{
int vertex;
struct VertexNode* next;
} VertexNode;
typedef struct Graph
{
int vertex_count;
VertexNode** heads;
} Graph;
void graph_init(Graph* graph, int vertex_count);
void graph_destroy(Graph* graph);
void graph_add_undirected_edge(Graph* graph, int vertex1, int vertex2);
bool graph_are_adjacent(const Graph* graph, int source, int destination);
void graph_print(const Graph* graph);
#endif /* GRAPH_LIST_H */graph_list.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph_list.h"
void graph_init(Graph* graph, int vertex_count)
{
graph->vertex_count = vertex_count;
graph->heads = malloc(sizeof(VertexNode*) * vertex_count);
memset(graph->heads, 0, sizeof(VertexNode*) * vertex_count);
}
void graph_destroy(Graph* graph)
{
for (int vertex = 0; vertex < graph->vertex_count; ++vertex)
{
VertexNode* current = graph->heads[vertex];
while (current != NULL)
{
VertexNode* next = current->next;
free(current);
current = next;
}
graph->heads[vertex] = NULL;
}
free(graph->heads);
graph->heads = NULL;
graph->vertex_count = 0;
}
static VertexNode* create_vertex_node(int vertex)
{
VertexNode* node = malloc(sizeof(VertexNode));
node->vertex = vertex;
node->next = NULL;
return node;
}
void graph_add_undirected_edge(Graph* graph, int vertex1, int vertex2)
{
VertexNode* vertex1_neighbor = create_vertex_node(vertex2);
VertexNode* vertex2_neighbor = create_vertex_node(vertex1);
vertex1_neighbor->next = graph->heads[vertex1];
graph->heads[vertex1] = vertex1_neighbor;
vertex2_neighbor->next = graph->heads[vertex2];
graph->heads[vertex2] = vertex2_neighbor;
}
bool graph_are_adjacent(const Graph* graph, int source, int destination)
{
VertexNode* node = graph->heads[source];
while (node != NULL)
{
if (node->vertex == destination)
return true;
node = node->next;
}
return false;
}
void graph_print(const Graph* graph)
{
for (int source = 0; source < graph->vertex_count; ++source)
{
printf("%c:", 'A' + source);
VertexNode* node = graph->heads[source];
while (node != NULL)
{
printf(" %c", 'A' + node->vertex);
node = node->next;
}
printf("\n");
}
}