다양한 그래프 알고리즘

송현준·2022년 12월 19일

알고리즘 자료구조 책정리

알고리즘, 자료구조

목록 보기

10/12

그래프란

노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미

트리 자료구조

부모에서 자식으로 내려오는 계층적인 모델
다익스트라 최단 경로 알고리즘에서는 우선순위 큐를 사용

우선순위 큐

우선순위 큐를 규현하기 위해 최소 힙이나 최대 힙을 이용할 수 있다.
최소힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조

그래프와 트리 자료구조 비교

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

그래프의 구현 방법

인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
인접 리스트(Adjacency List) : 리스트를 사용하는 방식

두 방식은 메모리와 속도 측면에서 구별되는 특징을 가진다.

특징

인접 행렬
- 간선 정보를 저장하기 위해서 $O(V^2)$ 만큼의 메모리 공간이 필요
- 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O(1)$ 의 시간으로 즉시 알 수 있다는 장점이 있다.
- 플로이드 워셜 알고리즘이 인접 행렬을 이용하는 방식
- 노드의 개수가 적은 경우에 플로이드 워셜 알고리즘을 이용
인접 리스트
- 간선의 개수만큼인 $O(E)$ 만큼의 메모리 공간이 필요
- 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O(V)$ 만큼의 시간이 소요
- 우선순위 큐를 이용하는 다익스트라 최단 경로 알고리즘이 인접 리스트를 이용한 방식
- 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용한 다익스트라 알고리즘을 이용

서로소 집합

수학에서 서로소 집합이란 고옹 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다.

서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다.

union
연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find
연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

서로소 집합 자료구조

서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현

트리를 이용해 서로소 집합 계산 알고리즘

union 연산을 확인하여, 서로 연결된 두 노드 A, b를 확인한다.
$I.$ A와 B의 루트 노드 A', B'를 각각 찾는다.
$II.$ A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)
모든 union 연산을 처리할 때까지 1번의 과정을 반복한다.

여기서 '가리킨다'는 표현은 부모 노드로 설정한다는 의미
예를 들어 B'가 A'를 부모노드로 설정하는 것을 그래프로 시각화 할때, B'와 A'를 간선으로 연결하는 형태로 그래프를 그릴 수 있다.

연결성

서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다.

서로소 집합 계산 알고리즘의 동작 방식

전체 집합
$\lbrace 1, 2, 3, 4, 5, 6 \rbrace$
4개의 유니온 연산
- union 1, 4
- union 2, 3
- union 2, 4
- union 5, 6
- 이러한 연산은 각각 '1과 4는 같은 집합', '2와 3은 같은 집합', '2와 4는 같은 집합', '5와 6은 같은 집합'이라믄 의미를 가지고 있다.

이러한 union 연산들은 그래프 형태로 표현될 수 있다. 각 원소는 그래프에서의 노드로 표현되고, '같은 집합에 속한다'는 정보를 담은 union 연산들은 간선으로 표현된다. 즉 6개의 노드가 있고 4개의 간선이 존재하는 그래프로 바꾸어서 생각할 수 있다.

유의할 점

서로소 집합을 그림으로 표현할 때는 번호가 큰 노드가 번호가 작은 노드를 간선으로 가리키도록 트리 구조를 이용해 그림을 그리게 된다. 즉 트리 구조상 번호가 작은 노드가 부모가 되고, 번호가 큰 노드가 자식이 된다.
union 연산을 효과적으로 수행하기 위해 부모 테이블을 항상 가지고 있어야 한다.
루트 노드를 즉시 계산 할 수 없고, 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.
다음 예시는 노드 3의 루트를 찾기 위해서는 먼저 부모 노드인 2로 이동한 다음 노드 2의 부모를 또 확인해서 노드 1로 접근해야 한다.

step0

초기 단계에서는 가장 먼저 노드의 개수(V) 크기의 부모 테이블을 초기화 한다.
이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.
현재 원소의 개수가 6이므로, 초기 단계에서는 총 6개의 트리가 존재하는 것과 같다.
여기에서 유의할 점은 부모 테이블은 말 그대로 부모에 대한 정보만을 담고 있다. 다시말해 특정한 노드의 부모에 대해서만 정장하고 있다.
실제로 루트를 확인하고자 할 때는 재귀적으로 부모를 거슬러 올라가서 최종적인 루트 노드를 찾아야 한다.
처리할 연산들 : union(1, 4) union(2, 3) union(2, 4) union(5, 6)

step1

첫 번째 union 연산을 확인하면, 1과 4를 합친다.
이때는 노드 1과 노드 4의 루트 노드를 각각 찾는다.
현재 루트 노드는 각각 1과 4이기 때문에 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
처리할 연산들 : ~~union(1, 4)~~ union(2, 3) union(2, 4) union(5, 6)

step2

노드 2와 노드 3의 루트 노드를 각각 찾는다.
현재 루트 노드는 각각 2와 3이기 때문에 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.
처리할 연산들 : ~~union(1, 4)~~ ~~union(2, 3)~~ union(2, 4) union(5, 6)

step3

노드 2와 노드 4의 루트 노드를 각각 찾는다.
현재 루트 노드는 각각 2와 1이기 때문에 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.
처리할 연산들 : ~~union(1, 4)~~ ~~union(2, 3)~~ ~~union(2, 4)~~ union(5, 6)

step4

노드 5와 노드 6의 루트 노드를 각각 찾는다.
현재 루트 노드는 각각 5와 6이기 때문에 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정한다.
처리할 연산들 : ~~union(1, 4)~~ ~~union(2, 3)~~ ~~union(2, 4)~~ ~~union(5, 6)~~

서로소 집합 알고리즘 소스코드

기본적인 서로소 집합 알고리즘
경로 압축 기법을 이용한 서로소 집합 알고리즘

서로소 집합 알고리즘의 시간 복잡도

노드의 개수가 V개이고, 최대 V - 1개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축 방법을 적용한 시간 복잡도
$O(V + M(1 + log_{2-M/V}V))$