[그래프] 서로소 집합 Union-Find, 위상정렬, 최소신장트리

그래프

• 무향 간선 : 방향이 존재하지 않는 간선
• 유향 간선 : 방향이 존재하는 간선
• 인접 Adjacent : 정점A, B를 바로 잇는 간선이 존재한다면 A, B는 인접하다.
• 차수 Degree : 정점에 존재하는 간선의 수
  • in-degree : 정점에 들어오는 간선의 수
  • out-degree : 정점에서 나가는 간선의 수
• 그래프의 종류
  • 무향 그래프 : 무항 간선으로 이루어진 그래프
  • 유향 그래프 : 유향 간선으로 이루어진 그래프
  • 가중치 그래프 : 가중치를 갖는 간선으로 이루어진 그래프
  • 완전 그래프 : 임의의 두 정점에 대해 이를 잇는 간선이 존재하는 그래프 (모든 노드가 연결되어있고, 인접해있음)
  • 연결 그래프 : 임의의 두 정점에 대해 이를 잇는 경로path가 존재하는 그래프
  • 트리 그래프 : 순환(사이클)을 갖지 않는 연결 그래프(=임의의 두 정점에 대해 경로가 1개 존재한다) → 즉, 하나의 간선을 지웠을 때 더 이상 하나의 그래프로 이루어지지 않고, 두 개 이상의 그래프로 분리된다.(=연결 그래프가 아니다) + 간선을 추가했을 때 사이클이 생긴다.

그래프 표현

① 간선 리스트 Edge List

k	start	end	cost
1	1	2	6
2	1	3	2
3	2	4	1
4	3	2	3
5	3	4	5

② 인접 행렬 Adjacency Matrix

: V가 크면 못 씀. (공간복잡도 때문에)

start/end	1	2	3	4
1	0	6	2	0
2	0	0	0	1
3	0	3	0	5
4	0	0	0	0

③ 인접 리스트 Adjacent List

start	1	2	3	4
List	↓	↓	↓	↓
end,cost	2, 6	4, 1	2, 3
	3, 2		4, 5

...	① 간선 리스트	② 인접 행렬	③ 인접 리스트
공간	$E$	$V^2$	$V+E$
정점 A에 있는 간선을 모두 찾는데 걸리는 시간	$E$	$V$	$deg(A)$
정점 A,B가 연결되어 있는지 확인하는 시간	$E$	$1$	$\min{(deg(A), deg(B))}$
정점 삽입	$1$	$V^2$ (행렬을 새로운 행렬로 옮기는데)	$1$ (만약 List로 구현한다면 $V$가 됨.)
간선 삽입	$1$	$1$	$1$

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

• Union 연산 : 각 원소가 속한 집합을 하나로 합치는 연산.
• Find 연산 : 원소가 속한 집합 대표번호를 리턴하는 연산.

위상정렬(Topological Sort)

• DAG(Directed Acyclic Graph) : 순환을 가지지 않는 방향그래프.
  • 선행자(predecessor), 후행자(successor)
    • 즉각 선행자(immediate predecessor), 즉각 후행자(predecessor successor)
• in-degree가 0인 노드는 바로 방문할 수 있다.
• 만약 방문한다면 그 노드의 out-degree 간선을 없앨 수 있다. (→ 즉, 이 과정을 통해 다른 노드(즉각 후계자)의 in-degree가 줄어들 수도 있다.)
• 위상정렬의 결과는 유일하지 못 하는데, 문제에서 이 기준을 보통 정해준다.
  • 이를 priority_queue + compare 함수로 구현할 수 있음.

트리(Tree)

• 사이클이 존재하지 않는 그래프.신장 트리(Spanning Tree)
• 무향 연결 그래프의 부분그래프이고, 그래프의 모든 정점을 포함하는 트리인 그래프.
  • V개의 노드가 존재할 때, V-1개의 간선이 필요하다.
  • V개 이상이면 사이클이 존재하고, V-2개이면 여러개의 그래프가 된다.
• 즉, 노드 V개를 간선으로 연결해 모든 노드로 가는 경로가 존재하는 최소 그래프(트리)를 만들고 싶을 때 V-1개의 간선이 필요하다.최소 신장 트리(Minimum Spanning Tree / MST)
• 크루스칼 알고리즘 (Kruskal's Algorithm)

1. 간선 리스트를 이용해, 간선들을 비용을 기준으로 오름차순 정렬한다. ($O(E\log{E})$) (→ 그리디함)
2. 이 정렬을 순회하며, 간선들을 연결한다. 만약 간선을 연결했을 때 사이클이 생긴다면 이 간선을 연결하지 않는다. ($O(N)$)
   • 사이클이 존재하는지 확인하는 방법 (DFS($N^2$), BFS, 유니온파인드)
     =====> $O(E\log{E})$프림 알고리즘 (Prim's Algorithm)(다익스트라와 헷갈리지 않도록, 차이점 : 주어진 그래프 내에서 신장 트리에 대한 문제 - 의 최소비용 / 두 노드 간의 경로 문제 - 의 최소비용 경로)
3. 나와 인접한 노드들을 연결한다.
4. 인접한 노드로 이동해 그 중 가장 작은 간선을 선택해서 연결한다.
   • BFS로 방문처리. ($O(N)$ : 모든 노드들을 한 번씩은 방문해야해서.)
   • Queue : 간선을 넣어줌. 즉 간선의 개수만큼 큐에 들어감. 비용의 최소값을 꺼내주면 된다. => 즉, priority queue.$O(\log{n})$
     ====> $O(V\log{E})$