그래프

그래프란?

• 노드와 에지로 구성된 집합
• 노드는 데이터를 표현하는 단위, 에지는 노드를 연결

유니온 파인드

유니온 파인드란?

• 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성

유니온 파인드의 핵심 이론

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B를 말함
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산. 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표 노드를 반환

유니온 파인드의 원리

1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것(처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화)

2. 각 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행(항상 대표노드끼리 연결해줌)

3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산(단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킴)

1. 대상 노드 배열에 index값과 value값이 동일한지 확인
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동
3. 이동 위치의 index값과 value값이 같을 때까지 1 ~ 2를 반복(반복이므로 이 부분은 재귀 함수로 구현)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 루트 노드값으로 변경

위상 정렬

위상 정렬이란?

• 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

기능 : 노드 간의 순서를 결정
특징 : 사이클이 없어야 함
시간 복잡도(노드 수 : V, 에지 수 : E) : O(V + E)

위상 정렬의 핵심 이론

1. 진입 차수의 이해(진입 차수는 자기 자신을 가리키는 에지의 개수)

2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺌

다익스트라

다익스트라 알고리즘이란?

• 그래프에서 최단 거리를 구하는 알고리즘

기능 : 출발 노드와 모든 노드간의 최단 거리 탐색
특징 : 에지는 모두 양수
시간 복잡도(노드 수 : V, 에지 수 : E) : O(ElogV)

다익스트라 알고리즘의 핵심 이론

1. 인접 리스트로 그래프 구현

• 다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만, 시간 복잡도 측면에서 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋음

2. 최단 거리 배열 초기화

• 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화(이때 무한은 적당히 큰 값을 사용하면 됨)

3. 값이 가장 작은 노드 고르기

• 최단 거리 배열에서 현재 값이 가장 작은 노드를 고름

4. 최단 거리 배열 업데이트하기

• 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트(1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트)

최단 거리 업데이트 방법 : Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

5. 과정 3 ~ 4를 반복해 최단 거리 배열 완성

• 모든 노드가 처리될 때까지 반복(과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 배열 완성)

벨만-포드

벨만-포드란?

• 그래프에서최단 거리를 구하는 알고리즘

  기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
  특징 : 음수 가중치 에지가 있어도 수행할 수 있음, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
  시간 복잡도(노드 수 : V, 에지 수 : E) : O(VE)

벨만-포드의 핵심 원리

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화

• 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현(최단 경로 리스트를 출발 노드는 0, 나머지 노드는 무한대로 초기화)

에지 클래스는 일반적으로 노드 변수 2개와 가중치 변수로 구성돼 있음

2. 모든 에지를 확인해 정답 리스트 업데이트

• 최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1임(노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N - 1이기 때문)
• 모든 에지 E = (s, e, w)에서 조건을 만족하면 업데이트를 실행
• 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리

업데이트 조건 방법 : D[s] != ∞이며 D[e] > D[s] + w일 때, D[e] = D[s] + w로 리스트의 값을 업데이트
※ 음수 사이클이 없을 때 최대 에지 개수가 나오려면 사향 트리 형태에서 양 도착 노드를 선택해야 함
※ 에지의 출발 노드를 s, 종료 노드를 e, 에지 가중치를 w로 가정

3. 음수 사이클 유무 확인

• 음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인
• 만약 업데이트 되는 노드가 있다면 음수 사이클이 있다는 뜻(2단계에서 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻)

플로이드-워셜

플로이드-워셜이란?

• 그래프에서 최단 거리를 구하는 알고리즘

기능 : 모든 노드 간에 최단 경로 탐색
특징 : 음수 가중치 에지가 있어도 수행할 수 있음(단, 음수 사이클은 불가). 동적 계획법의 원리를 이용해 알고리즘에 접근
시간 복잡도(노드 수 : V) : O(V³)

플로이드-워셜의 핵심 원리

• A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로

  도출한 플로이드-워셜 점화식 : D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

1. 리스트를 선언하고 초기화

• D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의(S와 E의 값이 같은 칸은 0, 다른 칸은 ∞로 초기화)
• S == E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문

2. 최단 거리 리스트에 그래프 데이터 저장

• 출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 리스트에 입력(인접 행렬로 표현)

3. 점화식으로 리스트 업데이트

• 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트

• 플로이드-워셜 알고리즘 로직

for 경유지 K에 관해 (1 ~ N) # N : 노드 개수
	for 출발 노드 S에 관해 (1 ~ N)
    	for 도착 노드 E에 관해 (1 ~ N)
        	D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

최소 신장 트리

최소 신장 트리란?

• 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리

특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개

최소 신장 트리의 핵심 원리

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화

• 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장
• 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성됨
• 사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화

2. 그래프 데이터를 가중치 기준으로 정렬(오름차순)

3. 가중치가 낮은 에지부터 연결 시도

• 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결

4. 과정 3 반복

• 전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복

5. 총 에지 비용 출력

• 에지의 개수가 N - 1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력

정리

• 언제 해당 알고리즘을 사용해야하는지 정리

  1. 유니온 파인드 : 연결된 집합을 관리할 때, 사이클 검출 시(최소 신장 트리 문제, 사이클 검출)
  2. 위상 정렬 : 작업 선행 관계가 있을 때(프로젝트 작업 순서 결정, 수강 과목 순서)
  3. 다익스트라 : 가중치가 양수인 그래프에서 단일 시작점 최단 경로(실시간 경로 탐색, 네트워크 라우팅)
  4. 벨만-포드 : 음수 가중치가 있는 그래프에서 단일 시작점 최단 경로(음수 가중치가 있는 네트워크에서 최단 경로 탐색
  5. 플로이드-워셜 : 모든 쌍 최단 경로를 구할 때(도시 간 모든 쌍의 최단 경로 계산)
  6. 최소 신장 트리 : 최소 비용으로 모든 노드를 연결할 때(네트워크, 전력망, 통신망 최적화)