[Data Structures] Graph | 그래프

Graph

그래프

- 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로,
  Vertex로 대상이나 개체를 표현하고,
  Edge로는 이들 간의 관계를 표현한다.

---

Examples of Algorithm using Graph Structure

[Spanning Tree; 신장 트리]
* Breadth-First Search (BFS) (너비 우선 탐색) (URL)
* Depth-First Search (DFS) (깊이 우선 탐색) (URL)
- Strongly Connected Components (강연결 요소) (URL)는 DFS를 활용한 알고리즘이다.

[Minimum Spanning Tree; 최소 신장 트리]
* Prim's Algorithm (프림 알고리즘) (URL)
* Kruskal's Algorithm (크루스칼 알고리즘) (URL)

[Topological Sorting]
* Topological Sorting (위상 정렬) (URL)

[Single-Source Shortest Path; 단일 시작점 최단 경로]
* Dijkstra's Algorithm (다익스트라 알고리즘) (URL)
* Bellman-Ford Algorithm (벨만-포드 알고리즘) (URL)
* Shortest Path in DAG (사이클이 없는 방향 그래프의 최단 경로) (URL)
- 한 시작 정점에 대해, 다른 모든 정점들로 향한, \(n-1\)개의 최단 경로를 계산해내는 알고리즘들이다.
- 이들 알고리즘에서는 임의의 두 정점 간 경로가 존재하지 않으면, 이 경로의 길이는 \(\infty\)로 정의하며,
  두 정점을 직접 연결하는 간선이 없는 경우, 가중치가 \(\infty\)인 간선이 있다 간주한다.

[All-Pairs Shortest Path; 모든 쌍 최단 경로]
* Floyd-Warshall Algorithm (플로이드-워샬 알고리즘) (URL)
* Johnson's Algrithm (존슨 알고리즘) (URL)
- 존재하는 모든 (시작 정점, 도착 정점) Pair에 대한, \(n(n-1)\)개의 최단 경로를 계산해내는 알고리즘들이다.
- 한 시작 정점에 대해, 다른 모든 정점들로 향한, \(n-1\)개의 최단 경로를 계산해내는 알고리즘들이다.
- 이들 알고리즘에서는 임의의 두 정점 간 경로가 존재하지 않으면, 이 경로의 길이는 \(\infty\)로 정의하며,
  두 정점을 직접 연결하는 간선이 없는 경우, 가중치가 \(\infty\)인 간선이 있다 간주한다.

[Best-First Search; 최적 우선 탐색]
* Prim's Algorithm (프림 알고리즘) (URL)
* Dijkstra's Algorithm (다익스트라 알고리즘) (URL)
- 각 정점에는 각자의 매력 함수 값이 부여되어 있고,
  시작 정점에서부터 방문하지 않은 정점들 중 매력 함수 값이 가장 이상적인 정점부터 방문하는 탐색 알고리즘이다.
  (즉, 방문할 정점을 Greedy하게 선택한다.)
- 프림 알고리즘에서 매력 함숫값은 현재 상태에서 방문하지 않은 정점을 연결하는데 드는 최소 비용이다.
- 다익스트라 알고리즘에서 매력 함숫값은 현재까지 계산된, 시작 정점에서 방문하지 않은 정점까지의 최소 거리이다.

---

Terminology (용어 정리)

\(G = (V, E)\)
- Vertex들의 집합 \(V\)와 Edge들의 집합 \(E\)로 구성된 그래프 \(G\)를 의미하는 표현이다.

Adjacent (a. 인접한)
- Edge로 연결된 두 Vertex가 있다면, "두 Vertex는 서로 인접해있다."라 표현한다.

Directed Graph (유향 그래프, 방향 그래프)
- Edge에 방향이 부여되어 있는 그래프이다.

Undirected Graph (무향 그래프, 무방향 그래프)
- Edge에 방향이 없는 그래프이다.

Weighted Graph (가중치 그래프)
- Edge에 가중치가 부여되어 있는 그래프이다.

Unweighted Graph (가중치가 없는 그래프)
- Edge에 가중치가 부여되어 있지 않은 그래프이다.
- 즉, 가중치가 없는 Edge는 임의의 두 Vertex가 연결되어 있는지 아닌지만 표현하는 수단이 된다.

Minimum Spanning Tree (MST; 최소 신장 트리)
- Weighted Graph에서 Weight값의 합이 가장 작은 Edge를 모아서 구성한 트리를 의미한다.

Incoming Edge (진입 간선) & Outgoing Edge (진출 간선)

Shortest Path (최단 경로)
- Weighted Directed Graph \(G = (V, E)\)에서 Path \(p = <v_0, v_1, \cdots, v_k>\)의 가중치는 아래와 같이 정의된다.
  \(w(p) = \sum\limits_{i=1}^{k} w(v_{i-1}, v_i)\)

- 이 때, 정점 \(u\)에서 정점 \(v\)까지의 Shortest Path Weight(최단 경로 가중치)는 아래와 같이 정의된다.
\(\delta(u, v) =
\begin{cases}
\mathrm{min}\{w(p) : u \rightsquigarrow^p v\} \qquad \qquad \, \mathrm{(if \; the \; path \; from \; Vertex} \; u \; \mathrm{to \; Vertex} \; v \; \mathrm{is \; exist})\\\\
\infty \qquad \qquad \qquad \qquad \qquad \qquad \mathrm{(Otherwise)}
\end{cases}\)

- 이러한 경우, 정점 \(u\)에서 정점 \(v\)까지의 최단 경로는 가중치 \(w(p) = \delta(u, v)\)를 갖는 경로 \(p\)로 정의된다.

Strongly Connected Components (강연결 요소)
- Directed Graph \(G = (V, E)\)에서 모든 \((u ,v) \in E\)에 대해,
  경로 \(u \rightsquigarrow v\) 와 경로 \(v \rightsquigarrow u\) 가 동시에 존재하면,
  그래프 \(G\)는 "Strongly Connected"("강하게 연결되어 있다")라 표현한다.
- 즉, 어떤 두 정점을 잡더라도 양방향으로 서로에게 이르는 경로가 존재하면 "강하게 연결되어 있다"라 표현할 수 있다.
- 그래프상에서 강하게 연결된 부분 그래프들을 각각 Strongly Connected Components(강연결 요소)라 부른다.

Clique (클릭)
- Graph \(G = (V, E)\)의 Clique \(C \subset G\)는 Complete Graph이다.
  (즉, \(C\)는 완전 그래프인 \(G\)의 부분 그래프이다.) 
- Maximal Clique(극대 클릭)은 포함 관계에 따라, 극대인 클릭을 의미하는 것으로,
  더 이상 정점을 추가할 수 없는 클릭이다.
- Maximum Clique(최대 클릭)은 크기가 가장 큰 클릭을 의미하는 것으로,
  Graph \(G\)의 Maximum Clique의 크기를 Clique Number(클릭 수)라 하며, \(w(G)\)로 표기한다.

---

Representation (표현 방법)

- Graph의 세부적 표현 방법(저장 방법)으로는
  Adjacency-Matrix Representation (인접 행렬 표현)과
  Adjacency-List Representation (인접 리스트 표현),
  Adjacency-Array & Adjacency-Hash Table Representation (인접 배열과 인접 해시 테이블 표현)이 대표적이다.

---

1. Adjacency-Matrix Representation (인접 행렬 표현)

Undirected Graph에 대한 Adjacency-Matrix Representation	Directed Graph에 대한 Adjacency-Matrix Representation

- \(n\)개의 Vertex로 구성된 Graph의 Edge를 \(n\times n\) Matrix에 표현하는 방법이다.
- Vertex \(i\)에서 Vertex \(j\)로 향하는 Edge의 가중치 혹은 연결 여부 값을 Matrix의 \((i, j)\)에 저장한다.
- 즉, Directed Graph에서는 Matrix의 \((i, j)\)에 저장된 값과 \((j, i)\)값이 다를 수 있지만,
  Undirected Graph에서는 Matrix의 \((i, j)\)에 저장된 값과 \((j, i)\)값이 같아야 한다.
  (그래서, Undirected Graph에서는 Matrix의 Diagonal(주대각선)을 기준으로 대칭이거나,
   한 쪽 삼각형엔 값을 아예 저장하지 않는다. = 무조건 대칭이기 때문에 한 쪽 삼각형만 사용할 것이기 때문이다.)

* Time Complexity = \(\Theta(n^2)\) (\(n\) : The number of Vertices)
- \(n\times n\) Matrix에 대한 초기화 과정이 필수적으로 수반되기 때문이다.

* Space Complexity = \(\Theta(n^2)\) (\(n\) : The number of Vertices)
- \(n\)개의 Vertex로 이루어진 그래프를 구성하기 위해서는 \(n\times n\) Matrix가 필요하기 때문이다.

※ Edge의 밀도가 아주 높은 그래프에서는 인접 행렬 표현이 적합하다.

---

2. Adjacency-List Representation (인접 리스트 표현)

Undirected Graph에 대한 Adjacency-List Representation	Directed Graph에 대한 Adjacency-List Representation

- 임의의 한 Vertex에 인접한 각각의 Vertex들을 Node에 저장하여 List 구조로 매달아 놓는 표현방법이다.
- 1번의 행렬 표현과 달리, 존재하지 않는 Edge는 리스트 표현 상에서 나타나지 않는다.
- 하나의 Edge에 대한 Node는 Undirected Graph에서 두 개로 존재하고,
  Directed Graph에서는 하나로 존재한다.
  (Undirected Graph에서 하나의 Edge는 인접한 두 Vertex에서 모두 표현되어야 하기 때문이다.)
- Unweighted Graph에서 Node의 구조는 <Vertex 이름, 다음 Vertex를 가리키는 포인터 필드>로 구성되고,
  Weighted Graph에서 Node의 구조는 <Vertex 이름, 가중치, 다음 Vertex를 가리키는 포인터 필드>로 구성된다.

※ Edge의 밀도가 아주 높지 않은 그래프에서는 인접 리스트 표현이 적합하다.
- Edge의 밀도가 높은 그래프를 인접 리스트 방법으로 표현할 경우,
  List Operation에 대한 Overhead가 증가하게 된다.
  (특히, Edge가 많은 경우, 한 번의 Operation이 Edge의 개수에 비례하는 시간을 소요할 수 있다.)
- 또한, 인접 리스트 표현은 Edge의 개수에 비례한 만큼의 메모리를 요구하므로, 메모리 효율적이다.
- 그러나, 인접 리스트 표현은 단순히 두 Vertex사이에 Edge가 존재하는지에 대한 여부만을 따질 때에는 불리하다.
  (단순히 인접 여부만을 조사하는 경우엔 3번 방법인, 인접 해시 테이블 표현이 유리하다.)

---

3. Adjacency-Array & Adjacency-Hash Table Representation (인접 배열과 인접 해시 테이블 표현)

- 인접 리스트 표현과 같이, Edge의 개수에 비례하는 메모리 공간만을 소요하면서,
  행렬 표현과 같이, 두 Vertex사이에 Edge가 존재하는지를 빠르게 판단할 수 있게 하는 표현방법이다.
- 만약 각각의 Vertex에 할당된 Array를 미리 정렬해 놓았다면,
  임의의 Vertex에 인접한 Vertex의 개수가 k라 할 때,
  Binary Search를 통해 \((O(\log_2 k) + 1)\)의 시간 내에 특정 Vertex가 인접해 있는지를 검색해낼 수 있다.
  (예를 들어, 100개의 Vertex로 구성된 그래프에서 어떤 Vertex에 특정 Vertex와의 인접 여부를 알고자 할 때,
  인접 리스트 표현에서는 최대 100번의 비교연산이 필요하지만,
  인접 배열 표현에서는 최대 7번의 비교연산으로 알아낼 수 있다.)

* 인접 배열 구현 방법

(1)번 방법	(2)번 방법 - 각 Vertex Header에는 본인이 점유한 인접 배열의   마지막 원소의 인덱스값을 저장해놓고 있다.

1) 인접 배열을 각 Vertex마다 하나씩 부여하고, 각각의 Vertex Header에 배열의 크기 정보를 저장해놓는다.

2) 하나의 인접 배열에 모든 Vertex들의 인접 Vertex 정보를 저장해놓고,
  각각의 Vertex Header에는 자신이 점유하고 있는 인접 배열의 인덱스 범위 정보를 저장해놓는다.

3) 인접 배열을 적재율(\(\alpha\))=0.5의 해시 테이블*로 구현한다.
- 이 경우, 평균 2회 이하의 비교 연산으로 Vertex의 인접 여부를 조사해낼 수 있게 된다.
- 적재율을 0.5로 설정함으로써, 인접 배열의 공간이 두 배로 늘어난다 할지언정,
  그래봤자 리스트 표현에서 요구하는 메모리 공간과 같아지는 것이므로 큰 단점이라 볼 수는 없다. 
- 또한, 1번 방법과 같이 해시 테이블로 구현한 인접 배열을 각 Vertex마다 부여할 수도 있고,
  2번 방법과 같이 하나로 운용할 수도 있다.
- 그러나, 3번 방법은 어떤 Vertex에서 인접한 Vertex들을 차례로 Traversal하는 경우에는 적합하지 않고,
  두 Vertex 사이의 인접 여부를 조사하는 경우에 한하여 이상적인 성능을 낸다.

* Hash Table (해시 테이블) (URL)

[Data Structures] Hash Table | 해시 테이블

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)