그래프란?
정점(vertex, node)과 그것을 이어주는 간선(edge)으로 구성된 자료구조다.
트리는 Acyclic 그래프다. 그래프가 네트워크적 관계를 보여주는 모델이라면, 트리는 계층관계를 보여주는 모델이다.
그래프 용어
- Undirected Graph: 정점과 정점을 이어주는 간선의 방향성이 없는 그래프
- Directed Graph: 정점과 정점을 이어주는 간선의 방향성이 있는 그래프
- Degree: 각 정점에 연결된 간선의 개수. Directed Graph는 방향성을 고려하여 정점에서 나가는 간선의 개수인 Outdegree, 정점으로 들어오는 간선의 개수인 Indegree로 구분 하능하다.
- Weight: 간선은 가중치(weight) 정보를 포함할 수 있다. 별도의 가중치를 부여하지 않느다면 모든 간선의 가중치를 동일하게 고려한다.(비가중치 그래프)
- Sub Graph: 기존 그래프 중 일부의 정점과 간선으로 구성한 그래프
- Dense Graph: 정점의 수보다 간선의 수가 큰 그래프
- Sparse Graph: 점점의 수보다 간선의 수가 적은 그래프
오일러 경로?
- 그래프의 모든 간선을 한 번씩만 지나면서 방문하는 경로. 시작점과 도착점이 같을 시 오일러 회로라 한다.
- Undirected Graph에서 Degree가 홀수인 정점이 2개라면 오일러 경로, 0개라면 오일러 회로가 존재한다.
그래프의 구현
V: 정점의 개수, E: 간선의 개수
인접 행렬 (adjacency matrix)
정점간의 연결 여부를 (0|1)로 표현한다.
eg) 1번 정점과 2번 정점은 연결되지 않은 경우
- adjMatrix[1][2] == adjMatrix[2][1] == 0
eg) 1번 정점과 3번 정점은 연결된 경우
- adjMatrix[1][3] == adjMatrix[3][1] == 1
공간복잡도
간선의 개수와는 무관하며, V2를 가진다.
시간복잡도
두 정점의 연결 여부 확인: O(1)
한 정점이 어느 정점과 연결되었는지 확인: O(V)
모든 정점에 대해 어느 정점과 연결되었는지 확인: O(V2)
장단점
- 두 정점이 연결되었는지를 빠르게 확인 가능
- 정점의 개수가 많아질수록 정점에 대한 간선 확인이 느림
- 많은 메모리 차지 (V2)
➡️ 정점의 수보다 간선의 수가 많은 Dense Graph에 어울린다.
인접 리스트 (adjacency list)
각 정점이 어떤 정점과 인접한지를 표현한다. 즉, 정점마다 가진 리스트에 자신과 인접한 다른 정점들을 가진다.
eg) 1번 정점에 3,5,8번 정점이 연결된 경우
adjList[1] = [3, 5, 8]
공간복잡도
O(E+V). 정점의 수만큼 공간이 필요하며, 간선의 수만큼 추가 공간이 요구된다.
시간복잡도
두 정점의 연결 여부 확인: O(E)
한 정점이 어느 정점과 연결되었는지 확인: O(E)
모든 정점에 대해 어느 정점과 연결되었는지 확인: O(E)
장단점
- 두 정점이 연결되었는지를 확인하는 것은 인접 행렬에 비해 느리다.
- 한 정점 또는 모든 정점에 대해 어느 정점과 연결되었는지 확인이 인접 행렬에 비해 빠르다.
- 간선의 수 만큼만 메모리를 차지
➡️ 간선의 수보다 정점의 수가 많은 Sparse Graph에 어울린다.
그래프의 탐색
깊이 우선 탐색 (DFS)
한 정점으로부터 연결되어 있는 다른 한 정점으로 쭉 탐색한다. 탐색 도중 연결할 수 있는 정점이 하나도 없어지면, 전 단계의 정점으로 돌아가서 연결할 수 있는 다른 정점이 있는지 다시 탐색한다. 구현 시 주로 재귀 또는 스택을 이용한다.
너비 우선 탐색 (BFS)
한 정점으로부터 연결된 모든 정점으로 탐색한다. 즉, 한 정점으로부터 거리가 1인 모든 정점들을 탐색하고, 이후 거리가 2인 모든 정점들을 탐색하고, ...의 방식이다. 구현 시 주로 큐를 이용한다. BFS를 이용하면 최단 경로를 구할 수 있다.
Minimum Spanning Tree (최소 신장 트리)
그래프의 모든 정점이 acyclic하게 연결된 형태를 'Spanning Tree'라고 한다. 이러한 Spanning Tree 중 간선들의 가중치의 합이 최소가 되도록 하는 것이 MST(Minimum Spanning Tree, 최소 신장 트리)다. 즉 간선의 개수는 (정점의 개수 - 1) 이 된다. 일반적으로 크루스칼 알고리즘과 프림 알고리즘을 통해 구할 수 있다.
Kruskal Algorithm
간선들을 가중치 기준 오름차순으로 정렬한다. 이 후, cycle을 이루지 않는 한에서 간선을 가중치가 낮은 순으로 선택한다.
알고리즘 세부 사항
Union Find
새로운 간선이 Cycle을 이루는지 아닌지는 Union-Find 알고리즘을 통해 확인 가능하다. Union-Find는 말해, 어떤 원소가 어느 집합에 속했는지를 알 수 있게 해준다. 즉 정점을 원소, sub-graph를 집합이라 하면, 새로운 간선이 포함하는 두 정점이 같은 sub-graph에 있다면 해당 간선은 cycle을 이루기 때문에 MST에 포함될 수 없다. 일반적으로 트리를 통해 구현한다.
- Union Find의 3가지 과정
1. 초기화: 각자 자기자신을 루트노드로 가진다.
2. Union: 합치고 싶은 두 집합(트리)의 집합 번호(루트 노드)가 다르다면 한 트리의 루트 노드를 다른 트리의 루트 노드로 바꾼다. 즉 다른 트리의 서브 트리로 편입한다.
3. Find: 노드에 대하여 그 노드의 부모 노드를 탐색하며 자기 자신을 부모(집합 번호)로 가지는 루트 노드를 찾는다.
- 경로 압축
위의 과정을 보면, Union-Find의 시간 복잡도는 Find의 영향을 받는 것을 알 수 있다. 따라서 어떻게 Find를 효율적으로 수행할 것인지가 중요하다. Find를 수행하며 탐색하는 노드들 중 로트 노드가 아닌 것들을 모두 임시 저장한 뒤, 루트 노드를 찾으면 루트 노드의 child로 저장함으로써 경로를 단축할 수 있다.
그림 참고
시간 복잡도
- 간선 오름차순 정렬 비용: O(E log E)
- cycle 생성 여부 확인 (Union Find): 경로 압축을 한 find의 시간 복잡도는 O(a(N))이 된다. (a(N): 아커만 함수). 아커만 함수는 상수의 시간 복잡도를 가진다고 봐도 무방하다.
➡️ 총 시간 복잡도: O(E log E)
Prim Algorithm
하나의 정점을 무작위로 선택한다. 그 후 해당 정점에서 연결된 간선들 중 가장 가중치가 낮은 간선을 선택하여 연결된 정점을 sub-graph에 포함한다. 이 후 sub-graph에 포함된 정점들과 연결된 다른 정점들 중 연결하는 간선의 가중치가 가장 낮은 정점을 선택하여 sub-graph에 포함한다. 우선순위 큐를 사용한다면 빠르게 sub-graph와 최소 간선을 통해 연결된 정점을 알 수 있다.
시간 복잡도
sub-graph 내의 모든 정점에 대해 최소 간선으로 연결된 다른 정점을 찾는 비용: O(V log V)
sub-graph와 간선으로 이어진 다른 정점들을 우선순위 큐에 삽입하고, 힙 내부에서 들어온 정점들을 정렬하는 비용: O(E log V)
일반적으로 V가 E보다 작다.
➡️ 총 시간 복잡도: O(E log V)
최소 힙을 사용하지 않고 일반적인 배열을 사용할 경우, O(V2)이 된다.
Kruskal vs Prim
그래프 내의 간선이 많은 경우 프림(O(E log V)), 간선이 적을 경우 크루스칼 알고리즘(O(E log E))이 유리하다.
