그래프의 개념과 표현

그래프 알고리즘 (Graph Algorithms)

그래프

- (무방향) 그래프 G = (V, E)

V : 노드(node) 혹은 정점(vertex)을 의미한다.

E : 노드 쌍을 연결하는 엣지(edge) 혹은 링크(link)를 의미한다.

개체(object)들 간의 이진관계를 표현한다.

E(1, 2)는 (2, 1)과도 같은 의미를 내포한다.

보통 두 접점을 연결하는 엣지는 하나 혹은 없다고 가정한다. 또한 self edge도 없다고 가정한다.

n = | V |, m = | E |

방향 그래프와 가중치 그래프

- 방향 그래프(Directed Graph) G = (V, E)

엣지 (u, v)는 u로부터 v로의 방향성을 가지고 있다.

self edge를 허용한다.

- 가중치(weighted) 그래프

엣지마다 가중치(weight)가 지정되어있다.

그래프의 표현

- 인접 행렬 (adjacency matrix)

n x n행렬 A = ($a_{ij}$), where $a_{ij}$ = $\begin{cases}1&if (i,j)∈ E,\\0&otherwise\end{cases}$

저장 공간 : O($n^2$)

임의의 노드 v에 인접한 모든 노드를 찾는 데 걸리는 시간 : O(n)

임의의 엣지 (u, v)가 존재하는지 검사하는 데 걸리는 시간 : O(1)

- 인접 리스트 (adjacency list)

정점 잡합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트가 있다.

n : 각 정점, m : 정점과 인접한 정점의 연결들

노드의 개수가 2m인 이유는 각 노드가 한 엣지를 두고 서로를 연겨랗고 있다는 것을 표현하는 과정에서 두 번 표시되기 때문에 개수가 2m이 된다.

저장 공간 : O(n + m)

임의의 노드 v에 인접한 모든 노드를 찾는 데 걸리는 시간 : O(degree(v)) / 최악의 경우엔 모든 노드와 연결되어 n - 1이 되고 O(n)이 될 수 있지만, 실제로는 이보다는 적을 가능성이 높으므로 인접 행렬보다는 효율이 좋다.

임의의 엣지 (u, v)가 존재하는지 검사하는 데 걸리는 시간 : O(degree(u))

degree(x) : 정점 x에 인접한 노드의 개

방향 그래프

- 인접 행렬은 비대칭적으로 표현된다.

- 인접 리스트는 m개의 노드를 가지게 된다.

가중치 그래프와 인접행렬의 표현

- 엣지의 존재를 나타내는 값으로 1 대신 엣지의 가중치를 저장하게 된다.

- 엣지가 없을 때와 대각선 엣지(self edge)를 표현하는 방법

특별히 정해진 규칙은 존재하지 않다. 그래프와 가중치가 의미하는 바에 따라서 표현 방식이 갈리게 된다.

Ex1) 가중치가 거리 혹은 비용을 의미할 때 엣지가 없다면 ∞으로, 대각선 엣지는 0으로 표현한다.

Ex2) 가중치가 용량을 의미한다면 엣지가 없을 때 0으로, 대각선 엣지는 ∞으로 표현한다.

경로와 연결성

- 무방향 그래프 G = (V, E)에서 노드 u와 노드 v를 연결하는 경로가 존재할 때 v와 u는 서로 연결되어 있다라고 말한다.

- 노드의 모든 쌍들이 서로 연결된 그래프를 연결된(connected) 그래프라고 말한다.

- 연결 요소(connected component)