# 그래프 알고리즘

## 그래프 알고리즘이란?
- 그래프
- 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 네트워크 형태의 자료구조
- 다양한 현실 세계의 문제를 모델링하는 데에 사용된다
- 그래프 알고리즘
- 그래프라는 자료구조를 사용하여 문제를 해결하는 알고리즘
- 네트워크, 노드 간의 관계, 경로 등을 다루는 다양한 문제에 적용된다

**그래프 알고리즘은 컴퓨터 과학에서 매우 중요한 주제로, 데이터의 관계를 모델링하고 문제를 해결하는데 광범위하게 사용된다.**

## 그래프 알고리즘의 주요 카테고리

1. **탐색 알고리즘**
- 그래프의 정점을 방문하는 방법을 결정하는 알고리즘
- 대표적인 알고리즘으로는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있다.
2. **최단 경로 알고리즘**
- 두 정점 간의 최단 경로를 찾는 알고리즘
- 대표적인 알고리즘으로는 다익스트라(Dijkstra's) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘, 플로이드-와샬(Floyd-Warshall) 알고리즘 등이 있다.
3. **사이클 감지 알고리즘**
- 그래프에 사이클이 존재하는지를 찾는 알고리즘
- 대표적인 알고리즘으로 유니온-파인드(Union-Find) 알고리즘 등이 있고, DFS도 자주 사용된다.
4. **위상 정렬**
- 방향성이 있는 비순환 그래프(DAG)의 정점을 순서대로 나열하는 알고리즘
- 보통 종속성이 있는 작업을 순서대로 실행할 때 사용된다.
5. **최소 신장 트리 알고리즘**
- 모든 정점을 포함하면서 간선의 가중치의 합이 최소가 되는 트리를 찾는 알고리즘
- 대표적인 알고리즘으로는 크루스칼(Kruskal's) 알고리즘과 프림(Prim's) 알고리즘 등이 있다
6. **최대 유량 알고리즘**
- 네트워크 플로우에서 특정 소스에서 특정 싱크로 가능한 한 많은 플로우를 보내는 방법을 찾는 알고리즘
- 대표적인 알고리즘으로는 포드-풀커슨(Ford-Fulkerson) 알고리즘과 에드몬드-카프(Edmonds-Karp) 알고리즘 등이 있다.

## 최단 경로 알고리즘

> 집에서 은행으로 가는 가장 빠른 길은?

### 다익스트라(Dijkstra's) 알고리즘
- 가중치가 부여된 방향성 그래프에서 주어진 시작 정점으로부터 다른 모든 정점들까지의 최단 경로를 찾는 알고리즘.
- 다익스트라 알고리즘은 각 단계에서 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점을 선택하는 `탐욕적` 접근법과 `동적계획법`을 사용한다.
- 다만, 이 알고리즘은 음수 가중치를 갖는 간선에 대해서는 올바른 결과를 내지 못한다.

#### 다익스트라 알고리즘의 동작 과정

1. 출발 노드를 설정한다.
2. 출발 노드로부터 각 노드까지의 최단 거리를 저장하는 배열을 초기화한다.
3. 출발 노드의 최단 거리를 0으로 설정하고, 나머지 노드들의 최단 거리를 무한대로 초기화한다.
4. 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택한다.
5. 선택한 노드와 연결된 노드들의 최단 거리를 계산하여 최단 거리 배열을 업데이트한다.
6. 모든 노드를 방문할 때까지 4와 5를 반복한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">

---
---
---
---
---
---
---
---

</div>
</details>

---

### 벨만-포드(Bellman-Ford) 알고리즘
- 다익스트라 알고리즘과 유사하게, 벨만-포드 알고리즘도 주어진 시작 정점에서 그래프 내의 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다
- 이 알고리즘은 음의 가중치를 가진 간선에 대해서도 올바르게 작동한다
- 벨만-포드 알고리즘은 간선의 relaxation을 그래프의 정점 수 - 1번 반복하여 최단 경로를 찾는다
- 그러나 이는 **음의 사이클**이 없는 경우에만 올바르게 작동한다

#### 벨만-포드 알고리즘의 동작 과정

1. 출발 노드를 설정한다.
2. 출발 노드로부터 각 노드까지의 최단 거리를 저장하는 배열을 초기화한다.
3. 출발 노드의 최단 거리를 0으로 설정하고, 나머지 노드들의 최단 거리를 무한대로 초기화한다.
4. 모든 간선을 순회하는데, 각 간선을 통해 최단 거리를 갱신할 수 있다면 갱신한다.
5. 4를 전체 노드의 수 - 1번 반복한다. (V-1번 반복)
6. 음의 사이클이 있는지 확인하기 위해 한 번 더 모든 간선을 순회하고 갱신이 발생하면 음의 사이클이 존재한다고 판단한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">

---
---
---
---

</div>
</details>

---

### 플로이드-와샬(Floyd-Warshall) 알고리즘
- 모든 정점 간의 최단 경로를 찾는 알고리즘으로 시작점과 도착점을 모든 가능한 쌍에 대해 계산하는 알고리즘이다
- 동적 프로그래밍 기반의 알고리즘으로, 큰 문제를 작은 부분 문제로 분해하여 문제를 해결한다.
- 플로이드-와샬 알고리즘은 음의 가중치를 가진 간선에 대해서도 올바르게 작동하지만, **음의 사이클**이 있으면 올바른 결과를 내지 못한다.

#### 플로이드-와샬 알고리즘의 동작 과정

1. 모든 노드 간의 거리를 저장하는 2차원 배열을 초기화한다. 자기 자신으로의 거리는 0, 직접적인 간선이 없는 노드들 간의 거리는 무한대로 초기화한다.
2. 노드 i에서 노드 j로 가는 직접적인 간선이 있다면, 그 거리를 배열에 저장한다.
3. 세 노드 i, j, k에 대해, i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 거리보다 크다면, i에서 j로 가는 거리를 갱신한다. (i에서 k를 거쳐 j로 가는 거리로)
4. 3의 과정을 모든 노드 쌍 (i, j)에 대해 반복한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">

---
---
---
---
---

</div>
</details>

---

> 참고 : https://visualgo.net/en/sssp

---

## 사이클 감지 알고리즘

- 그래프 내에서 사이클(즉, 어떤 노드에서 시작해서 그 노드로 돌아오는 경로)이 존재하는지를 찾는 알고리즘
- 사이클 감지 알고리즘으로 대표적인 알고리즘에는 깊이 우선 탐색(DFS)과 유니온-파인드 알고리즘이 있다

### 깊이 우선 탐색(DFS)를 이용한 사이클 감지

- DFS는 현재 노드에서 방문하지 않은 이웃 노드를 하나씩 방문하면서 사이클을 찾는다.
- 만약 DFS가 진행되는 도중에 이미 방문한 노드를 다시 방문하게 된다면, 그래프에는 사이클이 존재한다고 판단할 수 있다.

### 유니온-파인드(Union-Find) 알고리즘을 이용한 사이클 감지

#### 유니온 파인드란?
- '합집합 찾기' 알고리즘
- 서로소 집합(Disjoint-Set)알고리즘 이라고도 부른다

#### 유니온 파인드의 과정
- **유니온(Union) 과정:** 유니온이란 '합집합'을 의미한다. 두 개의 서로 다른 집합을 선택하여, 두 집합을 하나로 합치는 과정을 말한다. 유니온 연산을 통해 서로 다른 집합에 속해 있는 두 원소가 같은 집합에 속하게 된다.
- **파인드(Find) 과정:** 파인드란 '찾기'를 의미한다. 어떤 원소가 어떤 집합에 속해 있는지 찾는 과정을 말한다. 즉, 각 원소에 대해 어떤 집합에 속해 있는지를 찾아내는 연산이다.
> **Union-Find**
> 
- **Path compression 과정:** 유니온-파인드 알고리즘의 효율성을 크게 높이는 테크닉. 파인드 연산을 수행하며 거치는 모든 노드들을 집합의 루트에 직접 연결하는 것. 이렇게 하면 트리의 높이를 대폭 줄일 수 있으므로, 이후에 같은 노드에 대한 파인드 연산이 발생할 때의 시간 복잡도를 크게 줄일 수 있다.
> **Path compression**
> 

---

## 위상 정렬(Topology Sort) 알고리즘


- '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
- 싸이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에 대해서만 수행될 수 있다
- 그래프에 싸이클이 있다면, 싸이클에 포함된 노드 중 어떤 노드도 진입 차수가 0이 되지 않아 결과를 만들 수 없기 때문

### 위상 정렬 알고리즘의 동작 과정

1. 모든 노드에 대해 들어오는 간선의 수(진입 차수)를 계산한다.
2. 진입 차수가 0인 모든 노드를 큐에 넣는다.
3. 다음 과정을 큐가 빌 때까지 반복한다:
   - 큐에서 노드를 꺼내 그 노드를 출력하거나 리스트에 추가한다.
   - 해당 노드에서 나가는 모든 간선을 그래프에서 제거한다.
   - 이 때, 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다.

---

## 최소 신장 트리 (Minimum Spanning Tree, MST)

### 신장 트리(Spanning Tree)란?
- 신장트리는 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리로 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다
- 단 그래프에 사이클이 형성이 되면 안된다
- 신장트리는 연결 그래프일 때 깊이 우선 탐색이나 너비 우선 탐색 방을 통하여 구현이 가능하다
- 이때 주어진 연결 그래프에 대한 신장트리는 하나가 아니라 다양할 수 있다


### 최소 신장 트리(Minimum Spanning Tree, MST)란?

- 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
- 그래프의 모든 노드를 포함하면서 간선의 가중치 합이 최소가 되는 트리
- 최소 신장 트리를 구하는 대표적인 두 알고리즘으로는 크루스칼(Kruskal's) 알고리즘과 프림(Prim's) 알고리즘이 있다

### 크루스칼(Kruskal's) 알고리즘

- 탐욕적 기법을 사용하여 최소 신장 트리를 구하는 알고리즘
- 그래프의 간선들을 가중치의 오름차순으로 선택하면서 사이클을 형성하지 않는 최소 신장 트리를 구하는 방법

#### 크루스칼 알고리즘의 동작 과정

1. 그래프의 모든 간선들을 오름차순으로 정렬한다.
2. 빈 집합인 신장 트리를 초기화한다.
3. 각 노드를 독립적인 집합으로 만든다. (Union-Find 사용)
4. 정렬된 간선 목록을 순회하면서 다음을 반복한다:
   - 현재 간선을 검토한다.
   - 현재 간선의 두 노드가 서로 다른 집합에 속해 있다면:
     - 현재 간선을 신장 트리에 추가한다.
     - 두 노드가 속한 집합을 합친다. (Union-Find 사용)
   - 두 노드가 같은 집합에 속해 있다면 현재 간선은 사이클을 형성하므로 버린다.
5. 신장 트리를 반환한다.

<details>
<summary>단계별 확인</summary>
<div markdown="1">

</div>
</details>

---

### 프림(Prim's) 알고리즘

- 탐욕적 기법을 사용하여 최소 신장 트리를 구하는 알고리즘
- 임의의 출발 노드부터 시작하여 현재 트리에 연결된 간선들 중 가장 작은 가중치를 가진 노드와 연결되는 간선을 선택하여 최소 신장 트리를 구하는 방법

#### 프림 알고리즘의 동작 과정

1. 임의의 노드를 선택하여 시작한다. 이 노드를 신장 트리에 추가한다.
2. 신장 트리에 연결된 노드들을 확인하여, 신장 트리에 아직 추가되지 않은 노드 중 가장 가중치가 낮은 간선을 선택한다. 
3. 선택한 간선에 연결된 노드를 신장 트리에 추가합니다. 이때 선택한 간선도 신장 트리에 추가한다.
4. 모든 노드가 신장 트리에 포함될 때까지 2번과 3번 과정을 반복한다.
5. 최종적으로 만들어진 신장 트리를 반환한다. 이 결과는 그래프의 모든 노드를 포함하고, 가중치의 합이 최소인 트리를 형성하게 된다

<details>
<summary>단계별 확인</summary>
<div markdown="1">

</div>
</details>

---
> 참고 : https://visualgo.net/en/mst
---

## 최대 유량 알고리즘(Max Flow Algorithm)

- 네트워크 플로우란 네트워크 플로우(Network Flow)는 그래프 내에서 물류, 통신, 정보, 자원 등의 '흐름'을 모델링하고 분석하는 방법이다
- **최대 유량 알고리즘(Max Flow Algorithm)** 은 이러한 플로우 네트워크에서 소스 노드에서 싱크 노드로 흘러갈 수 있는 플로우의 최대량을 찾는 알고리즘이다
- 최대 유량 알고리즘은 다양한 종류가 있지만, 가장 널리 알려진 것은 포드-풀커슨(Ford-Fulkerson) 알고리즘과 에드몬드-카프(Edmonds-Karp) 알고리즘이 있다
- 기본적으로 두 알고리즘은 부르트포스의 특징을 가진다

### 포드-풀커슨 알고리즘 (Ford-Fulkerson Algorithm)
- **DFS**를 이용한 알고리즘

1. 네트워크에 존재하는 모든 간선의 유량을 0 으로 초기화하고, 역방향 간선의 유량도 0 으로 초기화한다.
2. 소스에서 싱크로 갈 수 있는, 잔여 용량이 남은 경로를 DFS 로 탐색한다.
3. 해당 경로에 존재하는 간선들의 잔여 용량 중, 가장 작은 값을 유량으로 흘려보낸다.
4. 해당 유량에 음수값을 취해, 역방향 간선에도 흘려보낸다. (유량 상쇄)
5. 더 이상 잔여 용량이 남은 경로가 존재하지 않을때까지 반복한다.

### 에드몬드-카프 알고리즘 (Edmonds-Karp Algorithm)
- **BFS**를 이용한 알고리즘

1. 네트워크에 존재하는 모든 간선의 유량을 0 으로 초기화하고, 역방향 간선의 유량도 0 으로 초기화한다.
2. 소스에서 싱크로 갈 수 있는, 잔여 용량이 남은 경로를 BFS 로 탐색한다.
3. 해당 경로에 존재하는 간선들의 잔여 용량 중, 가장 작은 값을 유량으로 흘려보낸다.
4. 해당 유량에 음수값을 취해, 역방향 간선에도 흘려보낸다. (유량 상쇄)
5. 더 이상 잔여 용량이 남은 경로가 존재하지 않을때까지 반복한다.

> 역방향 간선은 역방향으로의 플로우를 가능하게 하며, 이는 원래의 간선에서 플로우를 '취소'하는 데 사용될 수 있다.
> 예를 들어, 노드 A에서 노드 B로 10의 플로우를 보냈다고 가정해 보자. 나중에 더 나은 최대 플로우 솔루션을 찾기 위해 이 플로우를 줄이고 싶을 수 있다. 이 경우, B에서 A로 플로우를 보내는 것은 기본적으로 A에서 B로 보낸 플로우를 줄이는 것과 같다. 그래서 역방향 간선이 필요하며 이렇게 하면 플로우의 양을 조정하면서 최적의 솔루션을 찾을 수 있다.
---

> 참고 : https://visualgo.net/en/maxflow

---

###### tags: `과외(하희영)`