[자료구조] Graph(그래프)

yohn·2024년 6월 12일

목록 보기

3/11

1. Graph란?

Graph(그래프)는 vertex(정점, 노드)와 각 vertex들을 잇는 edge(간선)의 집합이다. 한 vertex는 여러 edge들을 가질 수 있으며, edge에 방향성이 있어 한 방향으로만 이동할 수 있는 그래프를 directed graph, 그렇지 않고 양방향으로 이동할 수 있는 그래프를 undirected graph라고 한다.
Graph는 계층(hierarchy)가 없고, cycle이 존재할 수 있다. Cycle은 어떤 한 노드에서 출발해서 다시 자신의 노드로 돌아올 수 있다면 존재하는 것이다.

Directed graph의 예시

Undirected graph의 예시

2. Vertex Degree

Vertex degree는 한 노드와 연결되어 있는 노드의 개수를 의미한다. 예를 들어, 위 그래프에서는 degree(2) = 2, degree(4) = 3, degree(9) = 1이다.
모든 vertex degree의 합은 그래프의 edge의 수의 2배와 같다.

In-Degree

In-Degree는 directed graph에서만 정의되는 개념으로, 한 노드로 들어가는 edge의 수를 의미한다. 예를 들어, 위 그래프에서 indegree(2) = 2, indegree(10) = 0이다.

Out-Degree

Out-Degree는 In-Degree의 반대 개념이다. 즉, 한 노드에서 나오는 edge의 수를 의미한다. 예를 들어, 위 그래프에서 outdegree(2) = 0, outdegree(10) = 2이다.

모든 In-Degree의 합과 Out-Degree의 합은 그래프의 edge의 수와 같다.

$\text{sum of in-degrees} = \text{sum of out-degrees} = e\text{(the number of edges)}$

3. Tree와의 차이점

그래프는 계층(hierarchy)이 없으나, 트리는 계층이 있다. 따라서 트리에는 깊이(높이)라는 개념이 존재한다.
그래프에는 cycle이 존재할 수 있으나, 트리에는 존재할 수 없다.

4. Path Finding

그래프의 edge에는 가중치(cost)가 추가될 수 있다. 이때 한 노드에서 다른 노드까지 이동하는 데에 거쳐간 edge의 모든 가중치 합을 path length라고 한다.
또, 한 노드에서 다른 노드까지 이동할 수 있는 방법을 찾는 것을 path finding이라고 한다. 방법은 여러 개가 있을 수 있고, 방법이 없을 수도 있다.

예를 들어, 위와 같은 그래프가 있을 때 1에서 8까지 가는 방법은 1 $\to$ 3 $\to$ 7 $\to$ 8도 있고, 1 $\to$ 2 $\to$ 4 $\to$ 6 $\to$ 8도 있다. 그러나 첫 번째 방법의 path length는 4 + 1 + 3 = 8이고, 두 번째 방법의 path length는 1 + 6 + 9 + 10 = 26이다. 이때, path length를 최소로 하면서 원하는 노드에 도달하는 방법을 찾는 것이 중요하다.

5. Connected Component

Connected Component는 연결되어 있는 최대 크기의 subgraph를 의미한다. 위 그래프에서는 노드 1 ~ 8을 연결하는 subgraph와, 노드 9 ~ 11을 연결하는 subgraph가 각각 connected component이다. 전체 그래프가 connected component 하나로 이루어져 있는 경우를 connected graph라고 한다. 한 그래프가 connected graph가 아닌 경우에는 한 노드에서 다른 노드로 가는 방법이 존재하지 않을 수도 있다.
또, 한 cycle의 edge 하나를 지우는 것은 connectedness에 영향을 주지 않는다.

6. Spanning Tree

Spanning Tree는 한 그래프의 subgraph이자 tree로, 원래 그래프의 모든 vertex를 포함한다. 이때 이 subgraph에는 cycle이 존재하지 않아야 한다.

예를 들어, 이러한 그래프가 존재할 때 이 그래프에서의 spanning tree 예시는 아래 그림과 같다.

이때 이 spanning tree의 cost 총합인 spanning tree cost는 51이다.

만약 이렇게 spanning tree를 만든 경우, spanning tree cost는 41이다.
이렇게 spanning tree를 만드는 방법에는 여러 가지가 있으며, spanning tree cost가 최소인 minimum spanning tree를 만드는 것이 중요하다.

7. Graph의 표현

Adjacency Matrix(인접 행렬)

Adjacency matrix는 n개의 vertex가 있을 때 $n\times n$ 크기의 행렬로 표현된다. 행렬의 모든 값은 0 또는 1이며, $(i, j)$ 의 값은 $i$ 와 $j$ 가 edge를 통해 이어져 있는 경우 1, 이어져 있지 않은 경우 0이다.

예를 들어, 왼쪽 그림과 같은 그래프가 있다면 이 그래프의 인접 행렬은 오른쪽 그림처럼 나타낼 수 있다.
모든 인접 행렬의 diagonal entries는 0이고, 그래프가 undirected graph인 경우 모든 인접 행렬은 symmetric matrix이다.

인접 행렬을 표현하기 위해서는 $n^2$ 의 공간이 필요하며, undirected graph의 경우 lower 또는 upper triangle만 저장해도 된다. 이 경우 $\frac{(n-1)n}{2}$ 의 공간이 필요하다. 또한 주어진 vertex와 인접한 vertex를 모두 찾는 데에 $O(n)$ 의 시간이 소요된다.