그래프 알고리즘 - (1) Graph의 기본
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다.
1. graph란?
graph G = (V, E)로 이루어지는 자료 구조 중 하나이다. V는 vertex(node)의 set, E는 edge의 set이다. graph G를 (V, E)로 표현할 수 있다.
2. graph의 종류
Undirected Graph
G = (V, E) 중 edge set E의 모든 edge는 node가 연결되었다는 것만을 의미하는 것이다. 방향은 신경쓰지 않는다는 의미이며, 따라서 vertex 1과 vertex 2를 잇는 edge를 (1, 2)로 표현하든 (2, 1)로 표현하든 같은 말이다.
Directed Graph
G = (V, E) 중 edge set E의 모든 edge가 어떤 node에서 어떤 node로 연결되었는지를 의미한다. 방향도 신경쓴다는 것이므로, vertex 1과 vertex 2를 잇는 edge (1, 2)과 vertex 2와 vertex 1을 잇는 edge (2, 1)은 다르다.
3. graph의 표현
graph는 adjacent matrix와 adjacent list 2가지 방법으로 표현할 수 있다.
Adjacent matrix
n = |V|라고 할 때, n by n의 array로 vertex가 연결되어있는지를 표현하는 방법이다. arr[i][j] == 1이면 node i와 j가 연결되어 있다는 것이다.
이 경우 O(n^2) 공간복잡도, 두 vertex가 연결되어 있는지를 판별하는 데 O(1)의 시간복잡도를 가지며 모든 edge를 판별하는 데 O(n^2)이 걸린다.
Adjacent list
모든 vertex에 대해 그 vertex와 연결되어 있는 vertex들을 list로 표현하는 방식이다.
이 경우 O(|V| + |E|)의 공간복잡도, 두 vertex u, v가 연결되어 있는지를 판별하는 데에는 O(min(deg(u), deg(v))만큼의 시간이 걸린다. 모든 edge를 판별하는 데는 O(|V| + |E|)만큼의 시간이 걸린다.
여기서 deg(u)는 u와 연결된 vertex들의 개수를 말한다.
adjacent matrix, adjacent list 둘 다 각각의 장단점이 있으므로 상황에 맞는 것을 사용하면 된다.
4. Graph에서 사용하는 단어
Path
graph G = (V, E)의 path π의 모든 v_i와 v_j는 edge list에 속해 있다. 또한 π의 모든 vertex가 distinct하면 simple path라 한다.
$\pi \ =\ v_1v_2...v_{k-1}v_k$
Cycle
path π의 길이가 3보다 길고 v_1 == v_k이고 v_1부터 v_k까지 vertex가 distinct할 때 이 path를 cycle이라 한다.
$\pi \ =\ v_1v_2...v_{k-1}v_k$
Connectivity
undirected graph G의 모든 vertex u와 v에 대해, u와 v의 path가 있으면 그 graph G는 connected라고 한다. 그렇지 않다면 disconnected라고 한다.
- Strongly Connected
vertex u와 v에 대해, u->v의 path AND v->u의 path가 존재할 때 vertex u, v는 strongly connected라고 한다. (양방향)
- Weakly Connected
vertex u와 v에 대해, u->v의 path OR v->u의 path가 존재할 때 vertex u, v는 weakly connected라고 한다. (단방향)
- Connected Component
G의 maximal connected subgraph를 Connected Component라고 한다. maximal subgraph이므로 connected subgraph 중 제일 큰 것을 의미한다.
- Strongly Connected Component
G의 maximal strongly connected subgraph 중 모든 vertex pair (u, v)에 대해 u, v가 Strongly Connected이고 strongly connected subgraph 중 제일 큰 것을 의미한다.
Tree
tree는 connected이고 acyclic한 undirected graph이다.
Thereom. G를 n개의 vertex로 이루어진 graph라고 할 때 아래 3개 조건 중 2개를 만족한다면 다른 하나를 만족하며, 그 G는 tree이다.
- G는 connected이다
- G에는 cycle이 없다
- G는 n-1개의 edge가 있다
Property. undirected graph는 tree이다 iff G의 어떤 vertex pair에 대해서 unique path가 존재한다.
proof)
-> : tree에서 모든 vertex pair는 단 1개의 path가 존재한다. 만약 그렇지 않다면 cycle이 존재하기 때문이다.
<- : 모든 vertex pair에 대해 path가 존재한다는 말은 connected라는 말이고, path가 unique라는 말은 acyclic이라는 말이다.