그래프?

정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다.

---

그래프를 표현하는 세가지 방법

1. 간선 리스트

말그대로 배열에 간선들을 저장한다.

가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아니고서야 많이 사용되지는 않는다.

2. 인접 행렬

정점이 N개라면 NxN행렬을 만들어서 각각에 연결된 모든 간선들을 표시한다.

장점은 어떠한 두 정점이 연결되어 있는지를 확인한다 던지 할 경우 2차원 배열에서 탐색하기 때문에 인덱스로 상수시간 탐색이 가능하다는것.
단점은 간선의 수가 적던 많던 무조건 NxN의 공간을 사용하기 때문에 특히 정점에 비해 간선의 수가 적은 경우 매우 비효율적이라고 할 수 있다.

3. 인접 리스트

가장 많이 사용되는 그래프 표현 방식
먼저 1차원 배열을 생성하고 배열의 요소로, 각 배열 인덱스가 사용하는 간선의 정보를 동적배열로 생성하여 저장한다.

---

서로소 집합 ( Disjoint Set, Union-Find)

교집합이 공집합인 집합들의 정보를 확인하고 조작할 수 있는 자료구조로서 보통 Union 연산과, Find 연산으로 이루어진다.

서로소집합의 원리는 각 집합들의 합집합을 특정한 트리로 나타낸다는 점이다.

그렇기 때문에 어떠한 원소가 어떤 대푯값을 갖는 집합에 속했는지 알아보는 Find연산의 경우 해당 노드의 루트값만 알면 되기 때문에 수행시간은 트리의 높이(lgN)에 비례하게 된다.

Union 연산의 경우 각 원소의 루트노드가 다르다면 하나의 루트 노드를 다른 하나의 루트노드의 자식노드로 넣어버려서 두 트리를 합친다.

⭐️서로소 집합의 의의는 바로 효율적인 find 함수에 있다.

단순히 find함수가 루트노드를 거슬러올라가서 찾기만 한다면, union연산이 계속된다고 가정할 때 트리는 뱀과같은 기다란 모습이 되어버린다. 이는 최악의 경우 트리의 높이를 모든 정점의 개수(N)과 같이 만들게 되며, 서로소집합의 의의를 사라지게 만든다.

그렇기 때문에 find연산시에 단순히 루트노드를 탐색해서 반환하기만 해선 안된다. 대신, 거슬러 올라가면서 호출하는 모든 정점들의 부모노드를 루트노드로 만들어버린다. 모양이로 비유하면 가로로 쭉 늘려버리는 것이다.

---

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

무향 연결 가중 그래프 G에서 간선의 가중치의 합이 최소인 신장 트리
[백준 1922번: 네트워크 연결](https://www.acmicpc.net/problem/1922))

프림 알고리즘

정점선택 기반 알고리즘.
정점을 하나 선택한 후, 정점에 연결된 간선 중 가장 가중치가 작은 간선을 선택한다.

1. visit함수 초기화, 덱이 비어있을때 까지 반복.

2. 덱에 첫번째 정점을 넣고 1. 반복문 시작.

3. pq에 해당 정점의 모든 간선을 집어넣는다.

4. pq에서 정점하나를 뽑되 방문했던 노드면 스킵

5. 해당 정점을 덱에 넣고 visit = true;

크루스칼 알고리즘

간선 리스트를 가중치에 따라 오름차순으로 정렬한다음 하나씩 뽑는다. 두 정점이 연결되어있지 않다면 두 정점을 union해서 연결한다.

이 때 연결은 단순히 인접한다는 뜻이 아니다. 위의 네트워크 연결처럼 이어져있다는 뜻, 즉 서로소집합의 개념에서 같은 집합이라는 뜻이다

이 때 각 정점들이 같은 연결상황(집합)에 속하는지 판별하고 합치는 과정에서 서로소집합의 개념이 사용된다.

프림 vs 크루스칼

Prim의 알고리즘의 시간 복잡도는 O(n^2) 이다.
Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 이다.

그러므로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 Kruskal 알고리즘이 적합하고
그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우는 Prim 알고리즘이 적합하다고 할 수 있겠다.

---

비순환 방향 그래프 (Directed Acyclic Graph / DAG)

DAG는 이름대로 순환을 가지지 않고 방향만 갖는다.
일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다.
(학교 이수과정이라던가? 문명 테크트리)

위상정렬 ( Topological Sort )

[백분 2252번: 줄 세우기](https://www.acmicpc.net/problem/2252))

DAG에서 방향성을 거르지 않고 정점들을 나열하는 것.
(일반적으로 위상정렬의 결과는 유일하지가 않다.)

예를들어 10개의 정점이 주어지고 대소관계(간선)을 한 5가지만 준다고 할 때 가장 작은 것부터 정렬한다.

주의할점 : 처음 그래프를 초기화할때 in-degree를 저장하는 배열을 별도로 생성해서 그래프를 초기화할때 함께 갱신시킨다.

먼저 간선들 중 자신을 가리키는 간선(in-degree)가 없는 정점을 찾는다.
그리고 찾은 정점을 출력하고 출력한 정점과 그 정점에서 출발하는 간선을 삭제시킨다.
아직 그래프가 남아있다면 위 과정을 반복한다.