Graph
그래프는 간단하게 말하면 정점과 간선의 집합이다. 이전에 알아보았던 트리 또한 그래프의 일종이다. 그러나 트리는 사이클의 형성을 허용하지 않는다.
Graph 용어
Vertex & Edge
- Vertex는 정점을 의미한다. 정점에는 값들이 들어간다.
- Edge는 간선을 의미한다. 간선은 정점과 정점을 연결한다.
Undirected Graph & Directed Graph
Undirected Graph
말 그대로 정점과 간선의 연결에서 방향성이 없는 그래프이다.
V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex # u와 vertex v를 연결하는 edgeDirected Graph
말 그대로 정점과 간선의 연결에서 방향성을 가지는 그래프이다.
V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex # u에서 vertex v로 가는 edgeDegree
- Undirected Graph에서의 Degree는 정점과 정점을 연결하는 간선의 개수를 의미한다.
- Directed Graph에서의 Degree는 간선의 방향성이 존재하기 때문에 두개로 나뉘게 된다. 각 정점에서 나가는 간선의 개수를 Outdegree라고 하고 각 정점으로 들어가는 간선의 개수를 Indegree라고 한다.
가중치 그래프 (Weight Graph) & 부분 그래프 (Sub Graph)
가중치 그래프
가중치 그래프란 간선에 가중치를 두어 구성한 그래프이다. 해당 간선을 지나갈 때에 해당 가중치를 따져야 한다. 보통 '최소 비용으로 목적지에 도달하기' 같은 문제에 사용한다.
비가중치 그래프
비가중치 그래프는 말 그대로 간선에 가중치가 없는 그래프이다. 모든 간선의 가주이가 동일한 그래프도 존재한다.
부분 그래프
부분 집합과 유사한 개념으로 그래프에 적용된 것이다. 본래의 그래프의 일부 정점과 일부 간선만으로 이루어진 그래프를 의미한다.
Graph의 표현
인접 행렬 (Adjacent Matrix)
정방 행렬을 사용해서 그래프를 표현하는 방법으로 해당하는 위치의 value값을 통해 정점간의 연결 관계를 O(1)의 시간 복잡도로 파악할 수 있다. 정점의 개수와는 무관하게 O(V(정점)^2)의 공간 복잡도를 가진다. Dense Graph(밀집 그래프: 간선의 개수가 많은 그래프)를 표현할 때에 적합하다. (공간 복잡도가 이미 크기 때문에)
인접 리스트 (Adjacent List)
연결 리스트를 사용해서 그래프를 표현하는 방법으로 각 정점의 인접 리스트를 확인해봐야 하기 때문에 정점 간의 연결 확인에 시간이 오래 걸린다. 공간 복잡도는 O(E+V)이다. Sparse Graph(희소 그래프: 간선의 개수가 적은 그래프)를 표현할 때에 적합하다. (간선의 개수가 공간 복잡도에 반영되기 때문)
Graph의 탐색
그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 특정한 규칙이 있지 않기 때문에 탐색이 복잡하다. 그래프의 모든 정점을 탐색하기 위해서는 다음과 같은 방법을 사용한다.
깊이 우선 탐색 (DFS: Depth First Search)
그래프 상에서 임의의 한 정점으로부터 연결된 한 정점을 우선적으로 탐색하는 기법이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하고 더 이상 연결할 수 있는 정점이 없다면 바로 이전 단계로 돌아가 연결할 수 있는 정점을 탐색한다. 깊이 우선 탐색의 경우 Stack을 사용해서 구현한다. 시간 복잡도는 O(V+E)이다. (V: Vertex(정점), E: Edge(간선))
너비 우선 탐색 (BFS: Breadth First Search)
그래프 상에서 임의의 한 정점으로부터 연결된 모든 정점을 우선적으로 탐색하는 기법이다. Tree에서 같은 level에 있는 정점들을 우선적으로 탐색하는 것과 같다. 정점의 순서를 기록하기 위해 Queue를 사용하여 구현한다. 탐색을 시작하는 정점을 Queue에 enqueue하고 dequeue하며 dequeue하는 정점과 연결되어 있는 정점들을 enqueue한다. 이는 정점을 방문 순서대로 Queue에 저장하는 방법이다. 시간 복잡도는 O(V+E)이다. (V: Vertex(정점), E: Edge(간선))
BFS로부터 도출된 경로는 최단 경로를 보장한다.
최소 신장 트리 (MST: Minimum Spanning Tree)
Spanning Tree
그래프 내의 모든 정점을 포함하는 트리로 그래프의 최소 연결 부분 그래프이다. n개의 정점을 가진 그래프의 최소 간선의 개수는 n-1이 되고 n-1개의 간선을 가진 부분 그래프는 필연적으로 트리의 형태를 가진다. 이 트리가 바로 신장 트리이다. 간단하게 말하면 그래프에서 일부 간선을 선택해 만든 트리라고 할 수 있다.
Spanning Tree 특징
- DFS, BFS를 통해 그래프에서 신장 트리를 찾을 수 있다. (탐색 도중에 사용된 간선만을 모으면 만들 수 있음)
- 하나의 그래프에는 여러개의 신장 트리가 존재할 수 있다.
- 신장 트리는 트리의 특수한 형태로 모든 정점들이 연결되어 있고, 사이클을 포함하지 않는다. (사이클을 포함하면 트리가 아니다.)
- 신장 트리는 그래프의 n개의 정점을 n-1개의 간선으로 연결한다.
Minimum Spanning Tree
Spanning Tree 중에서 사용한 간선의 가중치의 합이 가장 적은 Spanning Tree를 의미한다. 각 간선의 가중치가 동일하지 않을 때 단순히 가중치가 가장 작은 간선을 사용한다고 해서 MST가 되는 것은 아니다. 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
Minumum Spanning Tree 특징
- 간선의 가중치의 합이 최소이다.
- n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용한다.
- 사이클을 포함하지 않는다.
Minimum Spanning Tree 구현
Kruskal Algorithm
Greedy method를 사용해 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘이다. 초기화 작업으로 간선 없이 정점들로만 그래프를 구성한 뒤에 간선을 가중치의 오름차순으로 정렬한다. 그 후 정렬된 간선들 중 사이클을 형성하지 않는 간선을 선택해 차례대로 추가한다. Spanning Tree가 완성되면 모든 정점들이 연결된 상태로 종료가 되고 완성될 수 없는 그래프에 대해서는 모든 간선에 대한 판단이 이루어진 후 종료된다.
cycle의 생성 여부의 판단
그래프의 각 정점에 set-id라는 것을 추가적으로 부여한다. 초기화 과정에서 1부터 n까지의 값으로 가각의 정점들을 초기화한다. 여기서 0은 어떠한 간선과도 연결되지 않았음을 의미한다. 그리고 연결할 때마다 set-id를 하나로 통일시킨다. 값이 동일한 set-id 개수가 많은 set-id 값으로 통일시킨다.
시간 복잡도
간선의 가중치를 기준으로 오름차순 정렬 -> O(E log E)
사이클 생성 여부를 검사하고 set-id를 통일 -> O(E + V log V)
전체 시간 복잡도 -> O(E log E)
Prim Algorithm
초기화 과정에서 한개의 정점으로 이루어진 초기 그래프 A를 구성한다. A의 정점과 외부의 정점 간의 간선을 연결하는 방식으로 그 중 가장 작은 가중치의 간선을 통해 연결되는 정점을 추가한다. 정점에 상관없이 간선의 가중치를 기준으로 연결한다. 이렇게 연결된 정점은 A에 추가되고 이 과정을 반복하여 Spanning Tree를 만든다. 간단하게 말하면 이전 단계에서 만들어진 신장 트리를 확장하는 방식인 셈이다. 트리의 간선이 n-1개가 되면 이 과정을 종료한다.
시간 복잡도
전체 시간 복잡도 -> O(E log V)
