그래프 개념과 구현

그래프^Graph는 정점^vertex와 간선^edge으로 구성된 데이터 구조입니다. 노드 사이에 간선으로 연결되며, 간선은 방향을 가질 수도 있고 방향을 가지지 않을 수도 있습니다. 즉, 그래프는 아래와 같은 두 가지 속성을 지니고 있습니다.

1. 노드^node라고도 부르는 정점의 유한 집합으로 구성됩니다.

2. (u, v) 형태의 순성쌍으로 이루어진 간선의 유한 집합으로 구성됩니다. (u, v)는 정점 u에서 정점 v로 이어지는 간선을 나타냅니다. 방향이 있는 그래프^{directed graph}에서 (u, v)와 (v, u)는 같지 않습니다. 간선은 시간이나 거리, 요금과 같은 가중치^weight, 값, 비용을 나타낼 수도 있습니다.

위에서 본 그래프의 속성에서 살펴본 것처럼 그래프의 간선이 여러 종류의 값을 나타낼 수 있기 때문에 그래프는 실생활의 문제에 많이 응용할 수 있습니다. 각 도시를 정점으로 나타내고, 도시 사이의 거리를 간선으로 나타내면 그래프로 표현할 수 있습니다. 또한, 네트워크를 그래프로 나타낼 수도 있습니다. 뿐만 아니라 페이스북과 같은 소셜 네트워크에도 그래프를 활용해, 사람은 정점으로 사람간의 관계를 간선으로 나타낼 수 있습니다.

그러면 이 그래프를 프로그램에서 어떻게 구현해야 할까요? 가장 많이 사용되는 두 가지는 배열을 이용하는 방법과 리스트를 이용하는 방법입니다. 배열을 행렬로 볼 수 있기 때문에 배열을 이용하는 방법은 인접 행렬^{adjacency matrix}을 이용한다고 말합니다. 즉, adjacency matrix, adjacency list, incidence matrix, incidence list 등을 이용해 그래프를 표현할 수 있습니다.

먼저 인접 행렬^{adjacency matrix}를 이용해 그래프를 표현해 봅시다. 아래 이미지와 같은 정점과 간선으로 구성된 그래프가 있다고 가정해봅시다.

위 그래프는 아래와 같이 2차원 배열을 통해 표현할 수 있습니다. 이차원 배열의 크기는 정점의 수 V에 의존하며 $V \times V$가 배열의 크기가 됩니다. 정점 $i$에서 정점 $j$에 이르는 간선이 있을 경우 배열의 원소를 1로 표현합니다. 방향이 없는 그래프의 인접 행렬은 항상 대칭적인 속성을 지닙니다. 위에서 살펴본 것처럼 간선이 시간이나 거리 등과 같은 가중치를 나타낸다면, 인접 행렬의 각 원소를 가중치로 표현할 수 있습니다. 즉, adj[i][j] = weight와 같이 표현할 수 있습니다.

그래프를 인접 행렬로 표현했을 때의 장점과 단점은 무엇일까요? 일단, 굉장히 직관적이므로 구현하는 것이 쉽습니다. 또한, 배열을 이용하면 인덱스를 통한 접근 시간^{access time}이 상수 시간 $O(1)$에 할 수 있습니다. 따라서 어떤 간선을 제거하거나 정점 u와 v를 연결하는 간선이 존재하는지 알아보기 위한 검색을 상수 시간에 할 수 있습니다. 하지만 이차원 배열로 표현하기 때문에 $O(V^2)$ 공간을 차지합니다. 정점을 연결하는 간선이 매우 적더라도^sparse 같은 공간을 차지하므로 비효율적입니다. 새로운 정점을 추가하는 데에도 시간이 오래 걸립니다.

이제 인접 리스트^{adjacency list}를 이용해 그래프를 표현해 봅시다. 배열 리스트를 이용한 방법을 살펴봅시다. 배열의 크기는 정점의 수와 같습니다. $i$번째 배열은 $i$와 연결된 정점의 리스트를 표현합니다. 이 방법에서도 간선을 가중치로 나타낼 수 있습니다.

인접 리스트를 이용하면 $O(\left | V \right | + \left | E \right |)$ 공간이 소모됩니다. 하지만 정점 u에서 v를 잇는 간선을 검색하려면 $O(V)$ 시간이 소요돼 효율적이지 못하다는 단점이 있습니다.

C++에서는 vector를 이용해 동적 배열을 구현할 수 있으며, Java에서는 ArrayList를 사용해 동적 배열을 구현해 연결 리스트가 아닌 인접 리스트를 나타낼 수 있습니다.

python 소스코드

import tensorflow as tf
print(tf.__version__)
  

java 소스코드

C++ 소스코드