그래프 (Graph)
객체들이 쌍으로 연관되어 집합을 이루는 자료구조
트리(Tree)도 그래프 구조의 일종
그래프 탐색: 깊이 우선 탐색(DFS), 너비 우선 탐색 (BFS)
[ 활용 예시 ]
- 네트워크 연결
- 경로 찾기 (최단 경로 포함, 다익스트라 (Dijkstra) 알고리즘)
- 순서 확인
- 연결성 확인
- 최단 스패닝 트리, 순환 탐지, 위상 정렬, Puzzle 풀기 (하나의 솔루션 찾기)
구성 요소
-
정점 (Node, Vertex) : 객체, 위치
-
간선 (Edge) : 정점 간의 관계, 연결선 (Link, Branch)
-
인접 정점 (Adjacent vertex) : 1개의 간선으로 직접 연결된 정점
-
정점 차수 (Degree) : 하나의 정점에 인접해있는 간선의 개수
-
진입 차수 (In-Degree) : 방향성이 있는 그래프에서 외부에서 오는 간선의 수(내차수)
-
진출 차수 (Out-Degree) : 방향성이 있는 그래프에서 외부로 향하는 간선의 수(외차수)
-
경로 길이 (Path-Length) : 정점에서 정점 간 경로 구성 시 사용된 간선의 수
-
단순 경로 (Simple Path) : 구성된 경로 중에서 반복되는 정점이 없는 경우
-
사이클 (Cycle) : 경로 중에서 시작 / 종료의 정점이 동일하여 내부적으로 순환이 발생하는 경우
그래프 종류
- 무방향 그래프 (Undirected)
노드(Node) 혹은 객체가 상호 연결만 되어 있는 형태
상호 양방향으로 이동 가능 ( 방향성 존재 X )
- 유방향 그래프 (Directed)
노드(Node) 혹은 객체가 연결되어 있으나 특정 방향으로만 이동할 수 있는 경우
2의 내차수(In-Degree) = 1
2의 외차수(Out-Degree) = 2
- 가중치 그래프 (Weighted)
네트워크(Network)
노드(Node) 혹은 객체의 연결에 가중치가 부여된 형태의 경우를 의미
연결된 내역의 가중치를 비용이라고 본다면, 가장 효율적으로 이동하는 방법을 계산할 수도 있음
- 연결 그래프 (Connected)
무방향 그래프에 있는 모든 정점의 쌍에 대해서 항상 경로가 존재하는 경우
트리(Tree) 구조가 해당, 모든 정점들이 계층에 따라 연결
- 비연결 그래프 (Disconnected)
무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
- 순환 그래프 (Cyclic)
정점 간의 단순 경로에서 시작 정점 / 종료 정점이 동일하여 경로에 순환이 발생할 수 있는 경우
단순 경로 (Simple Path)는 경로 중 반복되는 정점이 없는 경우
순환 그래프를 코드로 구현 시, Cycle Detection(순환 감지) 기능이 필요
- 비순환 그래프 (Acyclic)
- 완전 그래프 (Complete)
그래프에 속한 모든 정점들이 상호 연결된 그래프
N 개의 정점의 수가 있는 경우 간선의 수는 ( (n-1) * n / 2 ) 개
그래프 구현
| 특징 | 인접 리스트 | 인접 행렬 |
|---|---|---|
| 특징 | 특정 정점을 확인하기 위해 리스트를 모두 확인해야 함 | 특정 정점의 연결에 대해 배열로 한 번에 접근 |
| 공간 복잡도 | 각 정점의 List 에 간선의 수만큼 저장 O(E) | V 개의 정점의 수만큼 2치원 배열을 만들기에 O(V^2) |
| 시간 복잡도 | 리스트에 각 정점에 연결된 간선의 개수 만큼 저장 O(E) | 배열이 V*V 형태이므로 특정 정점의 0이 아닌 경우를 모두 검색 O(V) |
인접 행렬 (Adjacency Matrix)
M * N 형태의 행렬 (2차원 배열)을 통해 연결성이 있는 경우에는 0이 아닌 다른 숫자(가중치 등)를 저장
무향 그래프는, 정점 간 대각 성분을 기준으로 대칭을 이룸
전체 탐색의 경우 인접 리스트를 주로 사용
복잡도 :
[ 노드, 간선 = V, E ]
- 노드[ i ]와 [ j ] 간 관계 유무 파악 : O(1)
- 노드 i에 연결된 모든 노드 파악 : O(V)
- 전체 탐색 : O(V^2)
{ 1: [0, 1, 1, 1] ,
2: [1, 0, 1, 0] ,
3: [1, 1, 0, 1] ,
4: [1, 0, 1, 0] }인접 리스트 (Adjacency List)
정점(노드)와 정점 간의 연결을 리스트 형태로 나타내는 것
간선의 개수에 비례하는 메모리만 차지 = 인접 행렬에 비해 메모리 효율성 높음
복잡도 :
[ 노드, 간선 = V, E ]
- 노드[ i ]와 [ j ] 간 관계 유무 파악 : O(V)
- 전체 탐색 : O(E)
{ 1: [2, 3, 4] ,
2: [1, 3] ,
3: [1, 2, 4] ,
4: [1, 3] }간선 리스트
어느 간선 정보를 바탕으로 1차원 배열을 만들어 어떤 정점이 어느 정점으로 연결되는지 나타내는 자료구조
라이브러리 사용이 불가능하여 인접 리스트 사용이 어려울 때 가끔 사용
i번째 정점과 연결된 간선의 수를 저장
간선의 정점 간 연결 정보를 pair 형태(배열 또는 리스트)로 저장
그 개수를 판단하여 각 정점에서 연결된 간선의 수를 누적하여 저장
