그래프 탐색

Last updated - 2024년 10월 29일 Edit Source

코드트리(Codetree)의 Novice High - 자료구조 알고리즘을 정리한 내용입니다.

그림은 해당 내용을 참고하여 그렸습니다.

# 그래프

그래프(Graph) : 노드와 간선의 집합으로 구성된 자료구조
노드(Node) : 정점(Vertex), 각각의 지점
간선(Edge) : 정점과 정점을 잇는 선
간선의 가중치 : 간선에 값이 적혀져 있는 경우
차수(Degree) : 연결된 정점의 수
- 방향그래프의 경우 들어올 수 있는 정점의 수, 나갈 수 있는 정점의 수가 다름
- 위 그림에서 3번 노드를 기준으로 생각
- 무방향 그래프의 3번 노드 차수 : 3
- 진입차수(In-degree) : 0
- 진출차수(Out-degree) : 3
특정 지점에서 출발하여 다시 본래의 지점을 돌아올 수 있는 경우 = 사이클이 존재한다
연결 그래프 : 모든 정점들에 대해서 갈 수 있는 경로가 존재하는 경우
비연결 그래프 : 갈 수 있는 경로가 존재하지 않는 경우
연결요소 : 간선으로 연결되어 있는 정점들을 묵었을 때 나오는 그룹
- 위의 예시에서는 두 그래프 모두 연결 요소가 1
- 만약 비연결 그래프 형태로 하나의 선을 끊었다고 치면 2가 될 것

# 그래프 구현

그래프는 보통 인접 행렬, 인접 리스트 2가지 방식으로 구현
- 일반적으로 인접 행렬이 메모리를 더 많이 차지함
- 특정 정점과 연결된 정점의 수를 확인하는 연산은 인접 리스트가 더 빠름
  - 인접 행렬은 모든 정점의 연결관계 확인하니까 $O(|V|)$
  - 인접 리스트는 리스트의 크기만 보면 되니까
- 특정 두 정점이 연결되었는지 확인하는 연산은 인접 행렬이 더 빠름
  - 인접 행렬은 2차원배열의 1칸을 확인하면 되니까 $O(1)$
  - 인접 리스트는 정점에 해당하는 연결된 정점을 찾기 위해 모든 정점을 순서대로 확인해야해서 $O(|V|)$

인접 행렬

정점의 수 $|V|$, 간선의 수 $|E|$
인접 행렬 : $|V| * |V|$ 크기의 2차원 배열 만들어서 연결관계 표현
시간 복잡도
- 특정 정점 $I$, $J$ 연결되어 있는지 확인 : $O(1)$
- 특정 정점과 연결된 모든 정점 확인 : $O(|V|)$
- 공간 복잡도 : $O(|V| * |V|)$

인접 리스트

3번 노드의 연결 리스트 길이는 2
시간 복잡도
- 특정 정점 $I$, $J$ 연결되어 있는지 확인 : $O(min(degree(I), degree(J)))$
- 특정 정점과 연결된 모든 정점 확인 : $O(degree(X))$
  - X라는 정점에 해당하는 리스트의 크기, 연결된 정점의 수
- 공간 복잡도 : $O(|V| + |E|)$

# DFS

DFS (Depth First Search) : 깊이 우선 탐색

최대한 깊게 탐색한 후, 더 이상 도달할 수 없는 상황이라면 다시 이전으로 돌아감
DFS는 재귀(스택)를 활용해 구현하는 경우가 많음
- 방문할 수 있는 지점이 있다면 그 지점을 방문하는 함수를 재귀적으로 호출하고, 더 이상 방문할 곳이 없다면 함수를 종료
이미 방문했던 지점을 또 방문하면 효율이 떨어지기 때문에 이전에 방문했던 지점은 다시 방문하지 않아야 함
- 이런 처리를 위해, visited라는 배열을 하나 만들어서 그 번호를 갖고 있는 지점을 방문한 적이 있는지 확인하며 진행
시간 복잡도
- $O(∣V∣+∣E∣)$
- 어차피 모든 노드와 엣지를 방문하니까

# BFS

BFS (Breadth First Search) : 너비 우선 탐색

시작점을 기준으로 가장 가까운 정점부터 방문
BFS는 큐를 활용해 구현함
- 하나의 노드에 방문하면, 해당하는 노드와 인접한 노드 중 방문한 적 없는 노드를 전부 큐에 넣음
- 큐는 FIFO 이니까, 이후에 처음 넣었던 노드의 이웃 노드를 순차적으로 방문
시간 복잡도
- $O(∣V∣+∣E∣)$
- 어차피 모든 노드와 엣지를 방문하니까

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function bfs(position)
	set Q = Queue
	Q.push(position)
	visit(position)
	while Q is not empty
		set node = Q.pop
		for children of node
			if visitied[child] == false
				visit(child)
				Q.push(child)

DFS와 BFS의 성능 차이
어차피 모든 노드와 엣지를 방문하니까 시간 복잡도는 동일
그러나, 실제로는 DFS가 미묘하게 느림
재귀함수의 오버헤드 때문 ! 그래도 별 차이는 없습니다 ~!

# 최단거리

BFS를 이용한 최단거리 구하기

BFS의 동작 과정을 생각해보자
A를 방문했고, A의 이웃한 정점을 큐에다가 넣으면, 큐에 있는 모든 것들은 A와 거리가 1임
1의 이웃들이 큐에 들어가면, 거리가 1이니까 A와의 거리는 2가 됨
가중치만 전부 동일하다면, 방향 그래프에서도 동일하게 적용됨

간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리 구하는 것이 복잡해짐
실제로 1에서 2로 가는 최단거리는 4이다
- BFS를 그냥 이용하면, 가장 인접한 노드부터 순차적으로 보니까 최단거리를 100이라고 판단함
- 이를 해결하는 다양한 알고리즘이 존재 → ex) 다익스트라, 플로이드-워셜

# Dijkstra

다익스트라 알고리즘

특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘
특정 지점까지 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리
ex) 5개의 정점이 있고, 1번 정점에서 출발한다고 치면 1번에서 2번~5번으로 가는 최단거리 구함
시간 복잡도
- 그래프 내의 정점의 수 $|V|$
- 그래프 내의 간선의 수 $|E|$
- $O(|E| log |V|)$
- 다익스트라 알고리즘을 진행하면 각 간선을 한 번씩 보게 되는데, 이때 dist값이 변하면 우선순위 큐에서의 순서가 계속 바뀌게 될 수도 있으므로 간선의 수 × 우선순위 큐 이용 이 된 것
- 우선순위큐 안쓰고 for문 쓰면 $O(V^2)$
음수 가중치가 있을 때의 최단거리는 다익스트라로 구할 수 ❌
- 다익스트라 자체가 최솟값을 고르면서 가는건데, 음수 때문에 꼬임
- 음수 가중치가 있는 그래프의 최단거리를 구하려면 플로이드 와샬이나 벨만포드(2차원 DP)로 가능

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function dijkstra(graph, source)              // 그래프, 시작점 정보
    set Q = Queue()                           // 우선순위 큐 생성

    for each vertex in graph                  // 그래프에 있는 모든 노드들
        set dist[v] = INF                     // 초기값을 아주 큰 값으로 설정
        Q.push(v)                             // 우선순위큐에 모든 노드 넣기

    set dist[source] = 0                      // 시작점 dist 값을 0으로
    while Q is not empty                      // 우선순위큐 빌 때 까지
        set u = vertex in Q with min dist     // 우선순위 큐에서 dist값이 가장 작은 노드를 선택
        Q.remove(u)                           // 우선순위 큐에서 해당 노드를 제거

        for each neighbor v of u              // u번 노드와 연결된 노드들을 전부 살펴보면서
            set alt = dist[u] + length(u, v)  // 현재 dist값에 간선 가중치를 더한 값을 계산하여
            if alt < dist[v]                  // 기존 dist값보다 더 alt값이 작다면
                set dist[v] = alt             // dist값을 갱신

문제 : 5번을 시작점으로 하여, 다른 모든 정점에 도달하기 위한 최단거리 구하기

1. 거리 배열을 전부 아주 큰 값인 INF로 설정, 출발지만 0으로

2. 거리 배열 내의 값들 중 최솟값 고르기

최솟값 고르는 과정 여러번 반복
효과적으로 최솟값을 계속 찾기 위해 우선순위 큐(최소힙) 이용
1번 정점 ~ 5번 정점 전부 우선순위 큐에 넣어서 최솟값 찾기

3. 최솟값을 골랐으면, 시작점 ~ 뽑힌 노드까지의 거리는 정해졌으니 우선순위 큐에서 빼기

4. 우선순위 큐에서 뺀 노드로부터 연결된 노드들 확인, 값 비교 이후 갱신

뽑힌 노드가 5번이니 dist[5] + 간선에 적혀있는 값 과 해당 노드에 적혀있는 dist 값 중에 더 작은 값으로 갱신
dist[5] + 4 < dist[2] → 4로 갱신
dist[5] + 2 < dist[4] → 2로 갱신

5. 그 다음 우선순위 큐에 담겨있는 노드 중 최솟값 고르고 반복

dist[4] + 1 < dist[2] → 3로 갱신
dist[4] + 2 < dist[3] → 4로 갱신

# Floyd-Warshall

플로이드-와샬 알고리즘

모든 쌍에 대해 최단거리를 구하는 알고리즘
다익스트라와는 다르게, 모든 지점의 거리를 구하는 것
- 다익스트라로 모든 지점을 확인하려면 각각의 지점에 대해 다익스트라를 1번씩 돌려야 함
- 시간 복잡도가 for문 쓰면 $O(V^2)$, 우선순위큐 쓰면 $O(E log V)$ 였는데, V번 해야하니까 $O(V^3)$ 혹은 $O(VE log V)$가 되어버림
- 만약, 그래프에 간선이 굉장히 많다면 $E = V^2$이 되므로, $O(V^3)$가 더 효율적일 수 있음
A → B 경로보다, A → X → B가 더 짧으면 그것으로 갱신해주는 방식
시간 복잡도
- 삼중 반복문 돌리므로 $O(V^3)$
- 상당히 비효율적이라서, 정점의 수가 많지 않거나 모든 쌍의 최단거리를 꼭 구해야 할 때만 쓰고, 안그런 경우라면 다익스트라로 필요 지점만 보는게 효율적
for문 i, j, k가 아니라 k, i, j 인거 유의

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function floyd(graph)
    set dist = |V| * |V| array initialized to INF  // dist INF로 초기화
    for each edge(u, v)                            // 모든 간선에 대해
        dist[u][v] = length(u, v)                  // 간선 가중치 배열에 작성
    for k = 1 ... |V|                              // 확실하게 거쳐갈 정점을 1번부터 V번까지 순서대로 정의
        for i = 1 ... |V|                          // 고정된 k에 대해 모든 쌍 (i, j)를 살펴보기
            for j = 1 ... |V|
                if dist[i][j] > dist[i][k] + dist[k][j]     // i에서 j로 가는 거리가 k를 경유해 가는 것이 더 좋다면
                    dist[i][j] = dist[i][k] + dist[k][j]    // dist[i][j]값을 갱신
    return dist

1. $V^2$ 크기의 배열(dist) 내에 모든 값 INF로 채우기

2. 간선에 적혀져 있는 숫자들을 배열(dist)에 적기

3. 노드1 ~ 노드N 까지 순서대로 경유했을 때를 가정

모든 쌍(i, j)에 대해 노드 1을 경유하는 것이 더 좋은 경우 그 값을 갱신
dist[i][j] > dist[i][1] + dist[1][j] 를 만족하는 경우
- dist[i][j]에 dist[i][1] + dist[1][j] 값을 넣기

4. 노드2, 노드3, . . . , 노드N까지 똑같이 진행

# MST

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

가중치의 합을 최소로 하는 Spanning Tree
최소한의 간선을 사용하여 그래프 내 모든 정점을 이어준다면, 그것을 Spanning Tree라고 한다
- N개의 정점에 N-1개의 간선이 존재하는 트리
- 노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프를 트리라고 하니까
- 가중치가 있을때 최소한의 비용을 사용한 Spanning Tree가 Minimum Spanning Tree
MST를 구할 때, 모양이 다를 수는 있어도 크루스칼이든 프림이든 MST를 구하기만 하면, 항상 MST의 가중치의 합은 동일함
프림은 MST에 포함되지 않은 정점에 대해서만 동작하므로 사이클 만들어질 걱정 ❌
크루스칼은 최소비용 간선 확인하면서 가니까 사이클 만들어질 걱정 🟢 → 그래서 union-find 진행

# Union-Find

Union Find : 합집합 찾기

여러 개의 원소가 있고 여러 개의 집합이 있을 때, 특정 원소가 어떤 집합에 속해있는지 확인하고, 특정 집합을 합쳐야 할 때 유용
여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서, 이 노드들이 서로 같은 그래프에 속하는지 판별할 때 유용 → 사이클 존재여부 !!

1
2
3
4
5
6
7
8
function union(x, y)
  set X = find(x), Y = find(y)
  uf[X] = Y

function find(x)
  if uf[x] == x        // x가 루트 노드라면
    return x           // x 값을 반환
  return find(uf[x])   // x가 루트 노드가 아니라면, x의 부모인 uf[x]에서 더 탐색을 진행

모든 노드가 연결되어 있지 않은 상태에서 시작
uf 배열의 초기값은 자기 자신
처음에는 모든 노드가 전부 다른 그룹에 있음
- uf[x]는 부모 노드를 가리킨다고 보면 됨
- 현재 초기화한게 x == uf[x] 이니가 모두가 본인이 루트노드라고 초기화한 것

union(X, Y)
X 부모에다가 Y 부모 넣는다고 생각하면 됨

1번 예시 - union(1, 3)

union() 연산 사용 → 두 노드가 같은 그룹임을 표시할 수 있음
ex) 1번 노드와 3번 노드 연결 → uf[1]에 3을 적으면 됨
union(1, 3) = find(1), find(3)
find(1) = 1
find(3) = 3
uf[1] = 3

2번 예시 - union(5, 6)

union(5, 6) → 5번 노드와 6번 노드 연결, uf[5]에 6을 적으면 됨
union을 이용해 두 노드를 합치게 되면 uf 배열의 값은 그룹으로서의 의미 뿐만이 아니라, 실제 노드가 현재 가리키고 있는 부모 노드의 번호가 됨
union(5, 6) = find(5), find(6)
find(5) = 5
find(6) = 6
uf[5] = 6

3번 예시 - union(5, 1)

find() 과정 수행 → 두 노드 모두 부모 노드를 따라 올라 갈 수 있는데 까지 계속 올라가기
- x와 uf[x] 가 같아지기 전까지 올라가는 것
  - x == uf[x] 라는 말은 x가 루트 노드 라는 것
- find(5) = 6 → find(6) = 6
- find(1) = 3 → find(3) = 3
- 골라진 루트 노드가 X, Y 라면, uf[X]에 Y를 넣으면 됨
- uf[6] = 3

4번 예시 - union(4, 1)

왼쪽에다가 오른쪽 넣기
union(4, 1) = find(4), find(1)
find(4) = 4
find(1) = 3
uf[4] == 3

Union Find 시간 개선

모든 집합들이 합쳐져 있다고 가정하면, 부모를 찾다보면 결국 $O(N)$이 소요될 것
find를 호출할때 조상을 찾아내면, 현재 값의 부모값을 조상으로 바꿔버리는 방식으로 최적화
find()가 호출될 때마다 탐색했던 모든 노드가 전부 root로 붙게 되어 깊이가 전부 1로 바뀌게 되므로, 이후 동일한 노드를 탐색하게 될 경우 시간이 거의 소요되지 않음
- 이러한 방법을 경로 압축(Path Compression) 이라고 함
- 시간 복잡도 : $O(log N)$

기존의 find()

1
2
3
4
function find(x)
  if uf[x] == x        // x가 루트 노드라면
    return x           // x 값을 반환
  return find(uf[x])   // x가 루트 노드가 아니라면, x의 부모인 uf[x]에서 더 탐색을 진행

개선된 find()

1
2
3
4
5
6
function find(x)
  if uf[x] == x                 // x가 루트 노드라면
    return x                    // x 값을 반환
  set root_node = find(uf[x])   // x가 루트 노드가 아니라면, x의 부모인 uf[x]에서 더 탐색을 진행
  uf[x] = root_node             // 노드 x의 부모를 루트 노드로 설정
  return root_node              // 찾아낸 루트 노드를 반환

# Kruskal

Kruskal : 크루스칼 알고리즘

크루스칼은 MST를 찾는 알고리즘
- 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용
(1) 최소 비용인 간선부터 시작
(2) 특정 간선 선택 시, 두 노드에 union 연산 수행
- 합쳤으니까, 같은 집합이 됨
(3) 사이클이 발생한다면, 같은 집합으로 합치지 않고 넘어가기
즉, 간선의 가중치가 작은 것부터 순서대로 보면서 해당 간선 양 끝에 있는 두 노드 x, y에 대해 find(x), find(y)값을 비교하여 일치하지 않는 경우에만 간선을 선택해주고 union(x, y)를 진행
시간 복잡도
- 그래프 내의 간선의 수가 $E$ 라고 하자
- 최소비용 간선부터 처리하니까 정렬해야겠지. $O(E log E)$
- 각 간선에 대한 union-find 비용 $O(log N)$
  - E번 해야하니까 $O(E log N)$
- $O(E log E) + O(E log N)$이니까
- 최종 $O(E log E)$

팁 !
이미 MST에 포함된 노드끼리의 연결은 사이클 형성 🟢
MST에 새로운 노드가 추가되는 형태여야 사이클 형성 ❌

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function kruskal()
    mst = []                       // mst 담을 배열
    sort edge[] by length          // 간선을 가중치 기준으로 오름차순 정렬
    uf = uf_init(|V|)              // uf 배열을 노드의 수 |V|만큼 초기화

    for E in edge[]                // 각각의 간선에 대해 
        u, v = E                   // 간선을 이루고 있는 두 노드 u, v를 보며
        if find(u) != find(v)      // u, v의 루트 노드가 다른 경우에만
            mst.push(E)            // mst에 해당 간선을 넣어주고
            union(u, v)            // u, v를 같은 루트 노드를 갖도록 만들어줌
    
    return mst

(1) 최소 비용인 간선부터 시작, 비용 5정도 까지만 진행함

(2) 비용 6인 간선 진행하려하니, 사이클 발생

노드 5, 노드 8의 루트 노드가 동일한지 판단해야함
find(5) == find(8) 이니까 간선 추가 ❌

(3) 비용 7인 간선의 노드들을 보면 find(5) != find(7) 이니까 간선 추가

(4) 결과물

# Prim

Prim : 프림 알고리즘

Prim은 MST를 찾는 알고리즘
전체에서 최소비용 간선을 선택하던 Kruskal과는 반대로, 한 지점에서 시작하여 점점 확장하는 방식
Prim 알고리즘은 Dijkstra 알고리즘과 2줄 빼고 전부 동일
- 현재 노드를 u라고 하자
- Dijkstra : dist[v], dist[u] + length(u, v) 비교 후 작은 것으로 갱신
- Prim : dist[v], length(u, v) 비교 후 작은 것으로 갱신
- Dijkstra의 dist[x] → 시작점부터 x까지의 거리
- Prim의 dist[x] → 현재까지 만들어진 MST와 x를 연결하기 위해 필요한 최소비용
시간 복잡도
- 그래프 내의 정점의 수를 $|V|$, 간선의 수를 $|E|$ 라고 하자
- 프림 알고리즘을 진행하면 각 간선을 한 번씩 보게 되는데, 이때 dist값이 변하면 우선순위큐에서의 순서가 계속 바뀌게 될 수도 있으므로 간선의 수 × 우선순위 큐 이용 시간복잡도
- 다익스트라와 마찬가지로 $O(|E|log|V|)$
- 우선순위큐 안쓰고 for문 쓰면 $O(V^2)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function prim(graph)                   // 그래프와 시작점 정보가 주어짐
    set Q = PriorityQueue()            // 우선순위 큐 생성

    for each vertex in graph           // 그래프에 있는 모든 노드들에 대해
        set dist[v] = INF              // 초기값을 전부 아주 큰 값으로 설정 
        Q.push(v)                      // 우선순위큐에 각 노드를 넣기
    set source = |V|                   // 시작점을 임의로 마지막 노드로 설정
    set dist[source] = 0               // 시작점 대해서만 dist 값을 0으로
    while Q is not empty               // 우선순위 큐가 비어있지 않을 때까지 반복
        set u = vertex in Q with min dist     // 우선순위 큐에서 dist값이 가장 작은 노드를 선택
        Q.remove(u)                           // 우선순위 큐에서 해당 노드를 제거

        for each neighbor v of u              // u번 노드와 연결된 노드들을 전부 살펴보면서
            set alt = length(u, v)            // 간선 가중치를 살펴보기
            if alt < dist[v]                  // 기존 dist값보다 alt값이 작다면
                set dist[v] = alt             // dist값을 갱신

(1) 아무 정점이나 잡아도 되는데, 편의상 1번 잡음

(2) 1에 연결된 간선 중 최소 비용인거 선택, MST에 간선 추가

(3) 붙어있는 간선 중 최소 비용인거 선택

(4) 최소 비용인 13은 사이클 만드니까 선택 ❌

이미 MST에 포함된 노드끼리의 연결이고, MST에 새로운 노드가 추가되는 것이 아니니까

문제 : 5번을 시작점으로 하여, MST 구하기

1. 프림 또한 최솟값을 고르는 과정을 여러번 반복하므로, 우선순위 큐 사용

처음 거리가 최솟값인 노드를 선택하면 5번 노드 → 우선순위 큐에서 빼겠다는 말
프림 알고리즘에서 최솟값이 골라졌다는 의미는 해당 노드를 MST에 추가하겠다는 것

2. 5번 노드와 연결된 다른 노드들을 보며 간선에 적혀있는 값과 해당 노드에 적혀있는 dist값과 비교하여 더 작은 값으로 갱신

현재 MST를 이루고 있는 노드가 5번 노드이므로 5번 노드에 추가적으로 연결할 수 있는 정점들에 대해 각 정점을 간선을 통해 추가했을 때 추가적으로 나가게 되는 비용을 갱신해주는 것

3. dist(v)와 length(u, v) 비교 후 갱신

dist[2] = INF, length(5, 2) = 4 → 4로 갱신
dist[4] = INF, length(5, 4) = 2 → 2로 갱신

4. 우선순위 큐에 담긴 노드 중 dist 최솟값 고르기

dist[4] = 2 이므로 4번 노드 선택
이는 현재 MST에 4번 노드를 추가하는게 가장 좋은 상황이었다는 뜻
4번 노드가 뽑힘과 동시에 MST에 4-5를 연결하는 간선이 추가

5. 4번 노드에 대해서도 연결된 간선 들 최솟값으로 갱신해주는 작업 진행

dist[1] = INF, length(4, 1) = 3 → 3로 갱신
dist[2] = 4, length(4, 2) = 1 → 1로 갱신
dist[3] = INF, length(4, 3) = 2 → 2로 갱신
MST가 현재 노드 4, 5로 구성되어져 있는데 이들과 연결되기 위해 1번 노드는 비용 3이 필요하고, 2번 노드는 비용 1이 필요하고, 3번 노드는 비용 2가 필요하다는 뜻

6. 우선순위 큐에 담긴 노드 중 dist 최솟값 고르기

dist[2] = 1 이므로 2번 노드 선택
이는 현재 MST에 2번 노드를 추가하는게 가장 좋은 상황이었다는 뜻
2번 노드가 뽑힘과 동시에 MST에 2-4를 연결하는 간선이 추가

7. 2번 노드에 대해서도 연결된 간선 들 최솟값으로 갱신해주는 작업 진행

dist[1] = 3, length(2, 1) = 2 → 2로 갱신

8. 우선순위 큐에 담긴 노드 중 dist 최솟값 고르기

dist[1] = 2, dist[3] = 2인데 그냥 인덱스 작은거 고름
이는 현재 MST에 1번 노드 or 3번 노드를 추가하는게 가장 좋은 상황이었다는 뜻
1번 노드가 뽑힘과 동시에 MST에 1-2를 연결하는 간선이 추가

9. 3번 노드에 대해서도 연결된 간선 들 최솟값으로 갱신해주는 작업 진행

dist[3] = 2, length(1, 3) = 6 → 갱신 ❌
4번 노드랑은 이미 진행했음

10. 우선순위 큐에 담긴 노드 중 dist 최솟값 고르기

dist[3] = 2이므로 3번 노드 선택
이는 현재 MST에 3번 노드를 추가하는게 가장 좋은 상황이었다는 뜻
3번 노드가 뽑힘과 동시에 MST에 3-4를 연결하는 간선이 추가

# Topological Sort

Topological Sort (위상 정렬)

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
위 그래프에서 가능한 순서는 1, 3, 4, 6, 2, 5, 7 or 1, 4, 3, 6, 2, 5, 7 등등
이렇게 가능한 순서들 중 하나를 뽑아주는 방법이 위상정렬
- dfs를 이용한 방법
- in-degree를 이용한 방법

# Method 01 - DFS

DFS로 탐색 진행하다가 더이상 진행 못할 때 역순으로 가면서 스택에 넣으면 됨
1번 정점부터 n번 정점까지 순서대로 보면서 아직 방문한 적이 없는 정점에 대해서는 전부 해당 정점을 시작점으로 하여 dfs를 추가적으로 진행해줘야만 한다는 것
시간 복잡도
- 각 정점과 각 간선을 한 번씩 보게 되기에 $O(V+E)$

예시 1번

예시 2번

1번부터 시작한다 했다면, 탐색 종료 이후 다음으로 작은거 다시 하면됨

# Method 02 - In-degree

In-degree : 정점마다 해당 정점으로 들어오는 간선의 수
위상정렬이라는 것은 앞에 처리해야 할 순서가 끝나고 난 뒤에 현재 일을 처리하면 되는 것
- → in-degree가 0인 지점이 항상 시작점
위상정렬 적용 불가능
- 무방향 그래프 : 순서가 정의되지 않아서 적용하기 어려움
- 사이클 이루는 경우 : 순서를 정의할 수 없어서 적용하기 어려움
시간 복잡도
- 각 정점과 각 간선을 한 번씩 보게 되기에 $O(V+E)$
응용
- Q. 위상정렬 순서 중 사전순으로 가장 앞선 순서로 구해보면? (앞 순서에 더 작은 숫자가 나와야 유리하다는 말)
- A. In-degree sort를 큐 대신 우선순위 큐로 진행 !
  - 큐에서 방문할 지점을 뽑을 때, 가장 인덱스가 작은 지점이 나오므로 원하는 결과 나옴

1. in-degree가 0인 지점을 전부 큐에 넣고 시작

2. 큐에서 가장 앞에 있는 값을 뽑아, 해당 정점에 연결된 모든 간선을 보고, 간선이 가리키는 곳에 있는 정점의 in-degree 1 감소

간선을 지우지는 않았지만, 사실상 1과 2를 잇는 간선은 사라진것과 동일함

3의 in-degree가 0이 되었으니 3을 큐에 넣은 것

4도 마찬가지로 진행 !

3. 큐가 빌 때까지 반복하면 됨

Comment