Graph 이론에 대해 알아보자
Graph
Prim
구현설명
프림 알고리즘은 MST 즉, 최소 신장트리를 만드는 알고리즘 중 하나이며, 그리디 알고리즘의 일종으로 최적해를 보장해준다.
시작 정점을 집합 S에 포함시킨 상태로 시작한다. S에서 V-S를 연결하는 간선 중 최소길이를 찾아서 해당 정점을 S에 포함시킨다.
- 트리를 키워갈 때는 간선중 가장 작은 것을 선택
- 사이클이 이뤄지면 안됨
수도코드
Prim(G, r)
▷ G=(V, E): 주어진 그래프
▷ r: 시작으로 삼을 정점
{
S ← Ф ; ▷ S : 정점 집합
for each u ∈ V
du ← ∞ ;
dr ← 0 ;
while (S ≠ V) { ▷ n회 순환된다
u ← extractMin(V-S, d) ;
S ← S ∪{u};
for each v ∈ L(u) ▷ L(u) : u로부터 연결된 정점들의 집합
if (v ∈ V-S and wuv < dv) then dv ← wuv ;
}
}
extractMin(Q, d)
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다 ;
}
힙을 사용하기 때문이다. 힙의 시간복잡도 O(|V|),프림 알고리즘의 시간복잡도 O(|E|log|V|)
Kruskal
구현설명
Kruskal 알고리즘 또한 Prim 알고리즘과 같이 MST를 만드는 알고리즘이다.
Kruskal 알고리즘은 Greedy algorithm과 같이 매번 최선의 선택을 하여 모든 정점을 최소 비용으로 연결하는 트리를 구하는 것이다.
원래 Greedy algorithm으로 구한 답은 최적의 해답이라고 보장 할 수 없어서 검증이 필요하지만 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명이 되어있다.
이 알고리즘 또한 사이클을 형성하면 안된다. union-find 알고리즘을 이용하여 사이클이 형성되나 확인한다.
시작하면 각각을 전부 집합으로 구성한다. 그 이후 간선을 정렬한다. 가장 작은 간선을 찾아 정점들의 집합을 하나로 합치고 간선을 신장트리에 추가한다. 이것을 반복한다. 고려해야할 점은 사이클이 생성되면 안된다. 따라서 간선을 연결할 때 같은 집합에 속해있는지 확인해야한다. 반복 끝에 신장트리의 갯수가 n-1개가 된다면 끝낸다.
수도코드
Kruskal (G, r)
{
1. T ← Ф ; ▷ T : 신장트리
2. 단 하나의 정점만으로 이루어진 n 개의 집합을 초기화한다;
3. 간선 집합 Q(=E)를 가중치가 작은 순으로 정렬한다;
4. while (T의 간선수 < n-1) {
Q에서 최소비용 간선 (u, v)를 제거한다;
정점 u와 정점 v가 서로 다른 집합에 속하면 {
두 집합을 하나로 합친다;
T ← T∪{(u, v)};
}
}
}
시간복잡도 O(ElogV)
Dijkstra
구현설명
다익스트라 알고리즘은 프림의 알고리즘와 같이 주어진 시작점을 루트로 한다. 그리고 루트로부터 최단 길이 트리(SPT)를 만든다. 알고리즘이 진행되면서 가장 짧고 포함되어지지 않은 정점을 찾아서 포함시킨다.
- SPT에 포함되는 정점을 추적하기 위한 sptSet을 만든다. 즉 그 정점의 최단거리는 계산되어 결정되었다. 처음에 이 set은 비었다.
- 그래프의 모든 정점에 거리(가중치) 값을 준다. 모든 거리는 처음에 무한대로 설정한다. 그리고 source 정점에는 0 값을 주어 처음에 선택되도록 한다.
- 모든 정점이 sptSet에 포함될 때 까지 반복한다.
a) 아직 sptSet에 포함되지 않았고 가장 짧은 길이를 갖진 정점 u를 선택한다.
b) 이를 sptSet에 포함한다.
c) 정점 u에 인접한 모든 정점의 거리를 업데이트한다. 정점의 거리를 업데이트하기 위해, 모든 정점을 반복한다. 모든 정점 v에 대해서, 정점 u의 값과 u-v 간선의 가중치의 합이 정점 v의 값보다 작다면 정점 v의 거리 값을 갱신한다.
특징으로는 모든 정점을 들려야하며 다 돈다면 O(V²)의 시간복잡도를 가지며 구현시에는 우선순위 큐를 사용하면 쉽게 구현이 가능하다. 그리드 알고리즘에 속하며 음의 값을 가지면 안된다.
수도코드
Dijkstra(G, r)
▷ G=(V, E): 주어진 그래프
▷ r: 시작으로 삼을 정점
{
S ← Ф ; ▷ S : 정점 집합
for each u ∈ V
d[u] ← ∞ ;
d[r] ← 0 ;
while (S ≠ V) { ▷ n회 순환된다
u ← extractMin(V-S, d) ;
S ← S ∪{u};
for each v ∈ L(u) { ▷ L(u) : u로부터 연결된 정점들의 집합
if (v ∈ V-S and d[u] +w[u, v] < d[v] ) then {
d[v] ← d[u] + w[u, v];
prev[v] ← u;
}
}
}
}
Bellman-ford
구현설명
벨만포드 알고리즘 또한 모든 정점의 최단거리를 구하는 알고리즘이다. 하지만 다익스트라 알고리즘과의 차이점은 음의 값을 가질 수 있다는 점이 다르다. 그리고 시간 복잡도 또한 O(VE)로 다익스트라보다 긴 시간 복잡도를 가졌다.
- 첫번째로 src로 부터 모든 정점의 거리를 무한대로 초기화 한다. 그리고 src의 거리는 0으로 초기화 한다. 정점의 개수만큼의 dist[] 배열을 만든다.
- 다음으로 최단거리를 계산한다. |V|-1 번 만큼 아래 단계를 반복한다.
a) dist[v] > dist[u] + 간선 uv의 가중치 라면 dist[v]를 dist[u]+ 간선 uv의 가중치로 갱신한다.
수도코드
BellmanFord(G, r)
{
for each u∈V
d[u]← ∞;
d[r] ← 0;
for i ← 1 to |V|-1
for each (u, v) ∈ E
if (d[u] + w[u, v] < d[v]v ) then {
d[v] ← d[u] + w[u, v] ;
prev[v] ← u;
}
▷ 음의 싸이클 존재 여부 확인
for each (u, v) ∈ E
if (d[u] + w[u, v] < d[v]v ) output "해없음";
}
시간복잡도 θ(|E||V|)
floyd-warshal
구현설명
플루이드 와샬 알고리즘은 다익스트라와 벨만포드 알고리즘은 처음에 시작하는 정점을 정하는거와 달리 모든 정점들의 최단 거리를 구하는 알고리즘이다. 플루이드 와샬 알고리즘은 처음 배우고 아직도 기억에 남는 알고리즘이다.
첫번째로 그래프 메트릭스와 같은 솔루션 메트릭스를 초기화 한다. 그 다음 모든 정점을 중간 정점으로 고려하면서 솔루션 메트릭스를 갱신할 것이다. 이 알고리즘의 아이디어는 모든 정점을 하나하나 선택하여 모든 최단거리를 갱신하는 것인데, 선택된 정점을 중간 정점으로 포함하는 것이다. 정점 K를 중간 정점으로 선택한다면, 이미 {1,2,3, … k-1}의 정점들은 중간 정점으로 구려된 후이다. 모든 정점의 쌍 (i, j)을 시작점과 끝점으로 여긴다면, 두가지 가능성이 있다.
- K는 최단거리 (i, j)의 중간 정점이 아니기 때문에 d[i][j]를 그대로 유지한다.
- K가 최단거리 (i, j)의 중간 정점에 포함된다. 때문에 만약 d[i][j]의 값이 d[i][k] + d[k][j] 값보다 크다면 d[i][j]의 값을 d[i][k] + d[k][j] 로 갱신해야한다.
소스코드
내가 문제를 풀이하면서 이해한 소스이다.
k = 거쳐가는 노드 i = 출발 노드 j = 도착노드
for (int k = 0; k< number; k++) {
for (int i=0; i < number; i++) {
for (int j=0; j < number; j++) {
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
위상정렬
구현설명
싸이클이 없는 유향 그래프이며, 모든 정점을 일렬로 나열하는데 순서가 있다면 순서가 유지되어야한다.
DFS로 끝까지가서 백트래킹으로 출력을 하면된다.
수도코드
1)
topologicalSort1(G, v)
{
for ← 1 to n {
진입간선이 없는 정점 u를 선택한다;
A[i] ← u;
정점 u와, u의 진출간선을 모두 제거한다;
}
▷ 이 시점에 배열 A[1…n]에는 정점들이 위상정렬되어 있다
}
2)
topologicalSort2(G) {
for each v ∈ V
visited[v] ← NO;
for each v ∈ V ▷ 정점의 순서는 무관
if (visited[v] = NO) then DFS-TS(v) ;
}
DFS-TS(v) {
visited[v] ← YES;
for each x∈L(v) ▷ L(v): v의 인접 리스트
if (visited[x] = NO) then DFS-TS(x) ;
연결 리스트 R의 맨 앞에 정점 v를 삽입한다;
}
시간복잡도 θ(|V|+|E|)
사이클이 없는 유향 그래프(DAG)
수도코드
DAG-ShortestPath(G, r) {
for each u ∈ V
du ← ∞;
dr ← 0;
G의 정점들을 위상정렬한다;
for each u∈V (위상정렬 순서로)
for each v∈L(u) ▷ L(u) : 정점 u로부터 연결된 정점들의 집합
if (du + wu,v < dv ) then dv ← du + wu,v ;
}
시간복잡도 O(|E| + |V|)
강연결요소 구하기
구현설명
DFS수행해서 종료된 순서를 구한다. 그 다음 종료된 순서가 가장 느린 정점에서 DFS을 다시 수행한다. 집합이 생기는데 이 집합에서 어떠한 정점을 잡더라도 경로를 통해서 한 정점에서 다른 정점으로 갈 수 있는 경로가 있다.
수도코드
stronglyConnectedComponent(G) {
1. 그래프 G에 대해 DFS를 수행하여 각 정점 v의 완료시간 f [v] 를 계산한다.
2. G의 모든 간선들의 방향을 뒤집어 GR을 만든다.
3. DFS(GR)를 수행하되 1행에서 시작점을 택할 때 1.에서 구한 f[v]가 가장 큰 정점으로 잡는다.
4. 앞의 3에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}
시간복잡도 O(|E| + |V|)
증명
강연결요소에 있는 모든 두 정점은 같은 트리에 있어야한다.
- 분리된 트리 안에는 강연결요소의 모든 정점이 포함된다.
- 분리된 트리 내의 임의의 두 정점 사이에는 양방향 경로가 존재한다.
두 조건이 서로 필요충분조건으로 쓰이면서 증명의 근거로 충분하다.