12. 그래프 ADT (Graph ADT)

그래프 ADT는 정점^vertex의 집합 $V$와 간선^edge의 집합 $E$로 이루어진다. 정점은 노드^node라고도 표현한다.
각 노드와 간선은 원소, 즉 정보를 저장한다.

간선에는 방향의 유무에 따라 유향 간선^{directed edge}과 무향 간선^{undirected edge}이 있는데, 모든 간선이 유향 간선인 그래프는 유향 그래프라 한다.

그래프 용어

• 간선 $a$에 연결된 노드를 각각 간선의 끝점이라 한다.
• 노드 $V$에 연결된 간선 $a, b, c$를 각각 노드 $V$에 부착되었다고 한다.
• 간선 $a$로 연결된 노드 $U, V$를 서로 인접한 노드라 한다.
• 한 노드 $X$가 5개의 간선과 연결되어 있다면, 해당 노드의 차수는 5라 한다.
• 어떤 간선 $h, i$가 각각 노드 $V, U$를 연결하면, 간선 $h, i$를 병렬 간선이라 한다.
• 간선 $j$가 노드 $V$에서 노드 $V$로 연결된다면, 루프라 한다.
• 어떤 노드 $U$에서 $T$로 가는 간선들을 경로라 한다.
  • 이때, 경로 내의 모든 정점과 간선을 한번씩만 방문하면, 단순경로라 한다.
• 어떤 노드 $U$에서 시작하여 $U$에서 끝나는 경로를 사이클이라 한다.

그래프의 밀집도

그래프 내에 노드들을 연결하는 간선이 많을 경우 밀집 그래프, 적을 경우 희소 그래프라 한다.

그래프의 밀집도에 따라 시간복잡도 $O(n^2), O(nm)$인 알고리즘의 성능이 변화한다. ($n$은 노드의 개수, $m$은 간선의 개수)

밀집 그래프의 경우 $O(nm)$ 알고리즘이 빠르고, 희소 그래프에선 $O(n^2)$ 알고리즘이 빠르다.

자유 트리

모든 노드가 연결되어 있고, 사이클이 없는 무향 그래프 $T$를 자유 트리라 한다.
사이클이 없는 무향 그래프는 숲이라 한다.

스패닝 트리 (신장 트리)

어떤 그래프에서, 부그래프 가운데 트리인 신장 그래프를 신장 트리 혹은 스패닝 트리라 한다.
한 그래프가 트리가 아니라면, 해당 그래프에 대한 여러 신장 트리가 존재한다.

그래프의 구현

그래프의 구현 방법에는 세 가지가 있다.

• 간선 리스트^{edge list} 구조
• 인접 리스트^{abjacency list} 구조
• 인접 행렬^{abjacency matrix} 구조

간선 리스트 구조

노드들을 저장하는 리스트와 간선들을 저장하는 리스트를 따로 만든다.
각 노드는 원소를 담고, 간선들은 시점 노드와 종점 노드의 포인터와 원소를 담는다.

인접 리스트 구조

인접 리스트 구조는, 간선 리스트 구조에 더하여 각 노드가 부착 리스트를 갖는다.
부착 리스트에는 해당 노드에 부착된 간선들의 포인터가 저장된다.

인접 행렬 구조

인접 행렬 구조는 간선 리스트 구조에 더하여 인접 행렬을 갖고, 각 노드는 정수 번호를 부여받는다.
인접 행렬은 $n\times n$크기의 행렬이다. 해당 행렬의 $(i,j)$ 원소에는 $i$번 노드와 $j$번 노드 사이의 간선의 포인터가 저장되고, 해당 노드들 사이에 간선이 없을 경우 널이 저장된다.