[CLSR] 22.1 Representations of graphs (Ch 22. Elementary Graph Algorithms)

그래프를 $G= (V, E)$라 하면 $V$는 정점(vertice)의 집합, $E$는 간선(Edge)의 집합을 의미한다.

$|V|$는 정점의 갯수, $|E|$는 간선의 갯수를 의미.

점근적 표기에서 $V$는 $|V|$를 의미하고, $E$는 $|E|$를 의미한다. 즉, $O(VE)$는 $O(|V||E|)$의 의미로 사용된다.

또한, 수도 코드에서는 그래프 $G$의 정점 집합을 $G.V$로, 간선 집합은 $G.E$로 표기한다. 즉, 수도 코드에서는 정점과 간선을 그래프의 속성으로 본다.

---

• undirected graph : 간선에 방향이 없는 그래프를 의미. $u,v \in V$를 잇는 간선을 $(u,v)$와 $(v, u)$로 나타낼 수 있다면 두 표현이 같은 간선을 나타낸다.(간선 하나는 정점의 집합으로 이루어지므로 중괄호로 표현할 수 있지만, 관행적으로 소괄호로 표현한다)
• directed graph : 간선에 방향이 존재한다. 따라서 $(u,v)$와 $(v,u)$는 다르다. 또한 self-loops가 가능하다(자기 자신으로 향하는 간선)

 

---

그래프는 인접 배열(adjacency lists)과 인접 행렬(adjacency matrix) 두 방식으로 나타낼 수 있다.

• 인접 배열(adjacency lists) : 그래프 $G = (V,E)$가 있을 때, $G$는 $|V|$개의 배열을 포함하는 배열 $Adj$로 이루어진다. 각 $u \in V$에 대해 $Adj[u]$는 간선 $(u,v)\inE$가 존재하는 모든 $v$를 포함한다(즉, 연결된 모든 정점을 포함)(간혹 정점에 대한 포인터를 포함하는 경우도 존재). $(u,v)$의 표기에서 볼 수 있듯이 directed graph인 경우, $u$에서 출발하는 간선을 포함한다. 수도 코드에서 $Adj$는 그래프의 특성으로 간주하여 $G.Adj[u]$와 같은 표기를 사용한다. 인접 배열은 '희소 그래프(sparse graph)'일 때 유리하다. 인접 배열에 요구되는 메모리는 $\Theta(V + E)$이다.
• 인접 행렬(adjacency-matrix) : 각 정점은 1부터 $|V|$까지 번호가 매겨지고 그래프 $G$는 $|V| \times |V|$의 행렬인 $A = (a_{ij})$로 이루어진다. $a_{ij} = \begin{cases} 1 & if (i,j) \in E \\ 0 & otherwise \end{cases} $이다. 인접 행렬은 '밀집 그래프(dense graph)'일 때 유리.

(a)는 directed graph이고 (b)와 (c)는 이에 해당하는 인접 배열 표현과 인접 행렬 표현(CLRS p.590)

• 희소 그래프(sparse graph) : 간선의 수 $|E|$가 정점의 수의 제곱 $|V|^2$(최대 간선 수?)보다 확연히 적은 그래프.
• 밀집 그래프(dense graph) : 간선의 수 $|E|$가 정점의 수의 제곱 $|V|^2$에 가까운 그래프.