그래프 이론
트리와 그래프의 차이점
그래프는 트리와 다르게 루트노드가 없고 부모-자식 관계가 없다.
인접 리스트 or 인접 행렬로 구현된다.
들어가기 앞서, 다익스트라 알고리즘은 인접 리스트로, 플로이드-워셜 알고리즘은 인접 행렬로 구현된다.
다익스트라 알고리즘
현재까지 알려진 것 중, 가장 짧은 거리에 있는 노드를 선택하기가 핵심. → 그리디 알고리즘에 속함.
왜 인접 리스트로 구현되는 것이 유리한가?
모든 노드 쌍에 대하여 공간 만들지 않아도 되기 때문에 메모리가 효율적이라는 점.
연결된 노드를 찾기 위해 모든 노드를 탐색할 필요가 없다는 점
다익스트라 알고리즘은 시작 노드 지정 작업이 필요하다.
방문 여부를 체크하는 배열 또한 필요하다. → 아직 방문하지 않은 노드 중 최소 거리를 가진 노드를 찾고, 해당 노드와 연결된 노드들 거리를 업데이트 한다.
음의 가중치가 없을 때만 사용 가능한 다익스트라의 시간복잡도는 O(v^2)이지만
우선순위 큐를 사용하면 시간복잡도를 O((V+E)logV)로 줄일 수 있다
처음 방문하는 노드의 (최단거리, 노드번호) 우선순위 큐에 입력해준다.
우선 순위 큐에 있는 노드의 거리가 현재 배열에 입력 되어 있는 거리보다 클 경우 스킵해준다.
우선순위 큐 정렬 기준: 거리가 적은 순
의사 코드
function Dijkstra(graph, start):
distance = list(size=V, init=INF)
distance[start] = 0
priority_queue.add({0, start})
while priority_queue is not empty:
dist, node = priority_queue.pop_min()
foreach neighbor v of node:
alt = distance[node] + weight(node->v)
if alt < distance[v]:
distance[v] = alt
priority_queue.add({alt, v})
return distance
최단 경로가 어떤 노드로 구성되었는지 알기 위해서
현재 위치한 노드의 어느 노드로부터 왔는지 저장하는 prev 배열 필요
function Dijkstra(graph, start):
distance = list(size=V, init=INF)
distance[start] = 0
prev = list(size=V, init=0)
priority_queue.add({0, start})
while priority_queue is not empty:
dist, node = priority_queue.pop_min()
foreach neighbor v of node:
alt = distance[node] + length(node → v)
if alt < distance[v]:
distance[v] = alt
priority_queue.add({alt, v})
prev[v] = node
return distance, prev
노드 개수가 적은 경우에는 플로이드 워셜 알고리즘을 쓰는 것이 유리하다.
플로이드-워셜 알고리즘
플로이드 워셜 알고리즘은 모든 노드 간의 최단 거리를 구해야하므로 2차원 인접 행렬을 사용한다.
라운드마다 새로운 중간 노드를 설정하고(1~N) 각 경로에서 더 짧은 길이를 선택하여 거리를 계속해서 줄여나가는 과정을 반복한다.
의사코드
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3 dist[u][v] ← w(u,v) // 변 (u,v)의 가중치
4 for each vertex v
5 dist[v][v] ← 0
6 for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[i][j] > dist[i][k] + dist[k][j]
10 dist[i][j] ← dist[i][k] + dist[k][j]
11 end if
Disjoint Set
union + find 연산으로 서로소 집합 자료구조를 조작할 수 있다.
따라서 서로소 집합 자료구조는 union-find 자료구조라고도 불린다.
union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find: 특정 원소가 속한 집합이 어떤 집합인지
1. union 연산을 확인해서 서로 연결된 A와 B를 찾고, 그의 루트 노드 A`와 B`를 설정한 후 A`를 B`의 부모 노드로 설정한다.
2. 모든 유니온 연산 처리시까지 반복한다.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a<b:
parent[b] = a
else
parent[a] = b
서로소 집합은 어디에서 사용하는가?: 무방향 그래프의 사이클 판단할 때 사용됨.
루트 노드가 같다면 사이클 발생한 것으로 판단한다.
Spanning Tree
하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
크루스칼 알고리즘: 최소 비용 신장 트리 알고리즘
핵심: 모든 간선의 비용이 적은 순서대로 확인하면서, 사이클을 형성하지 않는 간선만을 선택하여 최소 신장 트리를 만드는 것
1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인한다. → find_parent 함수 사용
2-1. 사이클 발생 X → 최소 신장 트리에 포함
2-2. 사이클 발생 O → 최소 신장 트리에 포함하지 않음
3. 모든 간선에 대하여 사이클 발생 여부를 확인한다. 즉, 각 단계에서 사이클 검사가 포함된다.
*크루스칼 알고리즘이 그리디 알고리즘으로 분류되는 이유: 모든 간선에 대해 정렬한 뒤에 거리가 짧은 순으로 집합에 포함시키기 때문 → 그때마다 최선의 선택을 한다.
Topology Sort: 위상정렬
방향이 있는 비순환 그래프에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용한다. → 한 노드에서 다른 노드로 가는 경로가 있다면, 경로의 출발 노드가 도착 노드보다 먼저 나열되어야 한다는 것을 의미
그래프의 각 간선 에 대해 가 보다 먼저 오도록 노드를 정렬
위상정렬은 진입 차수를 기준으로 동작하는데, 이때 진입 차수는 특정 노드로 들어오는 간선의 개수를 뜻한다.
1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 아래의 과정을 반복
2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
2-2. 새로가 진입차수가 0이 된 노드를 큐에 넣음
Kahn의 알고리즘
public static List<Integer> topologicalSort(int vertices, List<List<Integer>> adj) {
// 진입 차수를 저장할 배열
int[] inDegree = new int[vertices];
// 그래프의 인접 리스트를 통해 각 정점의 진입 차수 계산
for (int i = 0; i < vertices; i++) {
for (int node : adj.get(i)) {
inDegree[node]++;
}
}
// 진입 차수가 0인 모든 정점을 큐에 삽입
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < vertices; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
// 위상 정렬 결과를 저장할 리스트
List<Integer> topOrder = new ArrayList<>();
while (!queue.isEmpty()) {
int current = queue.poll();
topOrder.add(current);
// 현재 정점과 연결된 모든 정점의 진입 차수 감소
for (int node : adj.get(current)) {
inDegree[node]--;
// 새로 진입 차수가 0이 된 정점을 큐에 삽입
if (inDegree[node] == 0) {
queue.add(node);
}
}
}
if (topOrder.size() != vertices) {
throw new RuntimeException("There exists a cycle in the graph");
}
return topOrder;
}
'Algorithms > study log' 카테고리의 다른 글
[Graph+BFS] 백준 7576 토마토 (0) | 2024.04.14 |
---|---|
[투포인터] 백준 20922 겹치는 건 싫어 (1) | 2024.04.09 |
[백트래킹] 눈덩이 굴리기, 근손실, 1,2,3 더하기 2 (1) | 2024.04.07 |
[Greedy] 백준 2141 우체국 (0) | 2024.03.19 |
[Greedy] 연속되는 조건이 있는 문제 (1) | 2024.03.17 |