Graph
- Data structure
- 2021년 6월 3일
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 Tree도 그래프의 일종인데 그래프 중에서도 사이클이 허용되지 않는 그래프이다.
1. 개념
- 정점(vertex) / 노드(node) : 위치
- 간선(edge) / 링크(link) : 위치간의 관계
- 인접 정점 : 간선에 의해 직접 연결된 노드
- 차수 : 하나의 노드에 인접한 노드의 수
- 경로 길이 : 경로를 구성하는 데 사용된 간선의 수
- 단순 경로 : 경로 중에서 반복되는 간선이 없을 경우
- 사이클 : 단순경로의 시작 정점과 종료 정점이 동일한 경로
- 오일러 경로 : 모든 간선을 한 번만 통과하면서 처음 정점으로 돌아오는 경로
- 오일러 정리 : 간선이 짝수일 때만 오일러 경로가 존재
- 부분 그래프 : 원래의 그래프의 일부 정점 및 간선으로 이루어진 그래프
2. 그래프 종류
- 영 그래프 (null graph) : 비어있는 그래프
- 완전 그래프 (complete graph) : 모든 노드가 서로 연결되어 있는 그래프
- 연결 그래프 (connected graph ) : 무방향 그래프에 있는 모든 노드쌍에 대해 항상 경로가 존재한 경우
- 정규 그래프 (regular graph) : 모든 정점이 동일한 개수의 정점을 갖는 것 ( 모든 정점의 차수가 같은 그래프)
- 이분 그래프 (bipartite graph) : 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로 칠할 수 있는 그래프 ( 모든 정점이 두 그룹으로 나눠지고 같은 그룹끼리는 인접하지 않은 그래프 )
- 완전 이분 그래프 (complete bipartite graph) : 이분 그래프 중에서도 서로 다른 그룹이라면 서로 다른 그룹끼리 모두 연결되어 있는 그래프
- 가중치 그래프 : 간선에 가중치가 주어진 그래프 ( 가중치는 양,음 모두 가질 수 있다. )
- 밀집 그래프 : 간선이 많이 존재하는 그래프
- 희소 그래프 : 간선이 적은 그래프
3. 표현 방법
1) 인접 행렬 (Adjacency Matrix) ( 2차원 배열 )
정점 사이의 관계를 나타내는 행렬
해당하는 위치의 값을 통해 vertex간의 연결 관계를 O(1)로 파악할 수 있어 두 정점의 인접 여부를 체크할 때 빠르다.
배열은 노드를 n개를 갖는다고 한다면 n^2만큼 메모리가 필요하기에 희소 그래프는 메모리 낭비가 될 수 있고 정점 개수가 동적으로 변하는 경우에는 효과적이지 않다.
간선의 개수가 많은 밀집 그래프 (Dense graph) 가 적합하다.
2) 인접 리스트 (Adjacency List) ( 연결 리스트 )
노드의 개수가 n개이고 노드의 개수가 e개인 무방향 그래프를 그리는데 있어 n개의 연결 리스트, n개의 헤드 포인터, 2e개의 노드가 필요하다.
정점의 개수가 동적으로 변하는 경우 효과적이다.
간선의 개수가 적은 희소 그래프 (Sparse graph) 가 적합하다.
3) 근접 행렬 (= 발생 행렬,부속 행렬) (Incidence Matrix) (2차원 배열)
정점과 간선의 관계를 나타내는 행렬로 그래프의 정점을 행으로, 간선을 열로, 두 정점간 연결상태를 2차원 배열로 표시하는 것이다.
정점보다 간선이 상대적으로 많은 그래프에서 저장공간과 메모리 절약을 위해 사용된다.
4. 시간 복잡도 ( Big-O)
| 자료구조 | 시간 복잡도 | |||||
|---|---|---|---|---|---|---|
| 저장 (storage) | 간선 추가 (Add Vertex) | 엣지 추가 (Add Edge) | 간선 삭제 (Remove Vertex) | 엣지 삭제 (Remove Edge) | Query | |
| 인접 리스트 (Adjacency list) | O(|V|+|E|) | O(1) | O(1) | O(|V|+|E|) | O(|E|) | O(|V|) |
| 인접 행렬 (Adjacency matrix) | O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) |
| 근접 리스트 (Incidence list) | O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) |
| 근접 행렬 (Incidence matrix)) | O(|V|+|E|) | O(|V|+|E|) | O(|V|+|E|) | O(|V|+|E|) | O(|V|+|E|) | O(|E|) |
5. 탐색
1) 깊이 우선 탐색( DFS )
시작 노드에서 출발하여 먼저 다음 노드로 향하면서 탐색한 곳은 표시를 해두고 더이상 갈 수 있는 노드가 없다면 이전 노드에서 다른 노드로 향하여 모든 노드를 탐색하는 방식. Stack 을 사용하여 구현.
Psuedo Code
노드를 방문했다고 표시
해당 노드 출력
for 연결되어 있는 모든 노드 확인
if 방문 하지 않고 연결되어 있는 노드
재귀 함수
2) 너비 우선 탐색( BFS )
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로, 큐를 이용하여 노드를 삽입하고 방문한 노드는 큐에서 빼내는 방식으로 구현한다.
Psuedo Code
노드를 방문했다고 표시
queue에 노드번호 삽입
while 큐가 비어있을때까지
queue pop
pop값 출력
for 노드에 연결되어있는 모든 노드 탐색
if 방문하지 않은 노드라면
큐에 삽입
노드 방문표시
6. 신장 트리 (Spanning Tree)
- 그래프 내의 모든 정점을 포함하는 트리
- 모든 정점들이 연결되어 있어야 하고 사이클은 포함되지 않는 형태
- n개의 노드를 정확이 n-1개의 간선으로 연결된다.
- 하나의 그래프에는 많은 신장 트리 존재 가능
1) Psuedo Code
노드 방문 표시
for 인접한 노드 탐색
if 방문하지 않은 노드
간선 표시
재귀함수
7. 최소 비용 신장 트리 (MST)
- 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리
- 모든 정점들이 연결되어 있어야 하고 사이클은 포함되지 않는 형태
- n개의 노드를 정확이 n-1개의 간선으로 연결된다.
한마디로 무방향의 가중치가 있는 연결 그래프이다.
1) 알고리즘 종류
Krustkal MST
탐욕적인 방법( Greedy Method )
- 간선 선택 기반 알고리즘
- 희소그래프에 적합 ( V > E )
- 간선 선택 단계에서 사이클을 포함하지 않고 최소 비용 간선을 선택
- 트리집합을 병합하면서 하나의 트리로 확장
과정
- 그래프의 가중치를 이용하여 오름차순 정렬
- 정렬된 리스트에서 사이클 포함하지 않은 간선 선택
- 선택한 간선을 MST 집합에 추가
edge 정렬이 속도를 결정짓기 때문에 egde 수가 적은 희소 그래프 유리하다.
Prim MST
탐욕적인 방법( Greedy Method )
- 정점 선택 기반
- 밀집 그래프에 적합 ( V < E)
- 시작 정점부터 출발하여 신장 트리 집합을 단계적으로 확장
과정
- 시작 정점 MST에 추가
- 앞 단계의 MST에 인접한 정점들 중 최소 간선 정점 선택
- MST가 n-1개 간선을 가질때 까지 반복
8. 그래프 알고리즘 복잡도
| 알고리즘 | 시간 복잡도 | |
|---|---|---|
| 평균 (Average) | 최악 (Worst) | |
| Kruskal 알고리즘 | Θ( |E| log|E| ) | O( |V|^2) |
| 프림 알고리즘 (Prim’s algorithm)) | Θ( |E| log|V| ) | O( |V|^2 ) |
| 다익스트라 알고리즘 (Dijkstra’s algorithm) | Θ( |E| log|V| ) | O( |V|^2 ) |
| 벨먼-포드 알고리즘 (Bellman-Ford algorithm) | Θ( |E| * |V| ) | Θ( |V|^3 ) |
| 플로이드-워셜 알고리즘 (Floyd-Warshall algorithm) | Θ( |V|^3 ) | O( |V|^3 ) |
| A* 알고리즘 (A* search algorithm) | Θ( |E| ) | O( b^d ) |
| 위상 정렬 (Topological sort) | Θ( |V| + |E| ) | O( |V| + |E| ) |
