Graph

Graph 이론 알고리즘

BFS/DFS 와 같은 알고리즘과 더불어 최단 경로 문제도 그래프 알고리즘의 한 유형이다. 문제에서 서로 다른 개체가 연결되어 있다는 힌트를 보면 그래프 알고리즘을 생각해야 한다.

Graph Algorithm

그래프 문제는 두 가지 방법을 이용하여 구현한다.

1. 인접 행렬 (Adjacency Matrix): 2차원 배열 사용  
    - 메모리 공간이 많이 필요하지만 특정 노드 간의 간선 비용을 O(1) 시간에 바로 알 수 있음  
2. 인접 리스트 (Adjacency List): 리스트 사용  
    - 간선의 개수 O(E)만큼만 메모리가 필요하지만 O(V)의 시간이 소요된다.  

서로소 집합 (Disjoint Set)

서로소 집합이란 공통 원소가 없는 두 집합을 의미하며 자료구조는 union과 find 연산으로 구성된다.

• union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• find: 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산
  트리를 이용해 서로소 집합을 계산하는 알고리즘은 다음과 같이 동작한다.
  ```
• 1. 각 간선을 확인하며 두 노드의 루트 노드를 확인
     • 1-1 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행
     • 1-2 루트 노드가 서로 같다면 cycle 발생
• 1. 모든 union에 대해 1번 반복
     c
     int find_root(int * root, int x) { if (root[x] != x) { root[x] = find_root(root, root[x]); } return root[x]; }

void union_root(int * root, int a, int b) { a = find_root(root, a); b = find_root(root, b); if (a<b) root[b] = a; else root[a] = b; }

위의 코드에서 a와 b 두 노드의 root가 같다면 cycle이 발생한다고 판단할 수 있다.  
  
### 신장 트리 (Spanning Tree)  
신장 트리란 어떠한 그래프가 있을 때 모든 노드를 포함하면서 cycle이 존재하지 않는 부분 그래프이다. 이는 하나의 그래프에 대해 여러 케이스가 나올 수 있다. 여러 신장 트리 중 최소 비용을 만들 수 있는 트리를 찾는 알고리즘이 `최소 신장 트리`이다. 대표적으로 크루스칼 알고리즘이 이에 해당한다.  
  
### 크루스칼 알고리즘 (Kruskal Algorithm)  
이는 대표적인 최소 신장 트리이다. 이는 아래와 같이 동작한다.  

1. 간선 데이터를 비용에 따라 오름차순 정렬한다.
2. 간선을 하나씩 확인하면서 cycle을 검사한다.
3. 모든 간선에 대해 2를 반복한다.
   ```
   크루스칼 알고리즘은 간선의 개수가 E일 때, O(ElogE)의 시간 복잡도를 갖는다.

위상 정렬 (Topology Sort)

이는 정렬 알고리즘의 일종으로 순서가 정해져 있는 작업을 차례대로 수행할 때 사용하는 알고리즘이다. 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이 특징이다. 이는 아래와 같이 동작한다.

1. 진입차수가 0인 노드를 큐에 넣는다.  
2. 큐가 빌 때까지 다음을 반복한다.  
    2-1 큐에서 노드를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.  
    2-2 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.  

위상 정렬은 모든 노드와 각 노드에서 출발하는 간선을 확인하기 때문에 O(V+E)의 시간복잡도를 갖는다.