그래프(Graph)
개념
그래프란, 노드들과 그 노드들을 연결한 간선을 나타낸 자료구조이다.
각각의 노드들은 정점(Vertex)이라고 표현한다.
그럼 트리와는 뭐가 다른가요?
| 그래프 | 트리 |
| 노드와 노드를 연결하는 간선들의 집합 | Cycle이 없는 Connected Graph |
| Cycle 존재 가능 | Cycle 존재 불가능 |
| 두 정점 사이의 여러개의 경로 존재 가능 | 두 정점 사이 반드시 1개의 경로 존재 |
| 간선의 수는 그래프의 종류에 따라 다름 | 간선의 수 = 정점의 수 -1 |
그래프 ⊃ 트리
표현방식
그래프 자료구조의 표현 방식에는 두 가지가 있다.
1. 인접 행렬
2. 인접 리스트
• 인접행렬 (Adjency Matrix)
정의 : 그래프의 연결 관계를 이차원 배열로 나타낸 방식,,
ex) adMa[i][j] -> i 정점에서 j 정점으로 가는 간선이 존재하면 adMa[i][j] = 1
이때 만약 간선에 가중치가 존재한다면 행렬 내부의 값을 가중치로 바꿔주기만 하면 된다.
• 인접리스트 (Adjency List)
정의 : 그래프의 연결 관계를 연결 리스트로 나타낸 방식,,
따라서 정점의 개수만큼 인접리스트가 존재하고, 각각의 인접 리스트에는 인접한 정점의 정보가 저장된다.
이번엔 또 두 개가 뭐가 다른가요...?
두 개의 표현방식에는 각각의 장단점이 있다.
• 인접행열 (Adjency Matrix)
장점
노드 i와 j의 인접(Adjency, 둘 사이에 간선이 존재하는 지) 여부를 O(1) 시간에 확인 가능.
밀집한(dense, 간선의 개수가 최대에 가까운) 그래프에서 효율적.
구현하기에 비교적 쉬움.
단점
간선의 개수에 상관없이 반드시 |Vertex|×|Vertex| 메모리 사용.
인접한 정점을 알려면 O(V)의 시간을 사용. ( 정점 개수와 간선 개수의 차이가 많이 날수록 비효율적)
• 인접리스트 (Adjency List)
장점
존재하는 간선에 따라 메모리 사용이 유동적 (드문(sparse) 그래프에서 효율적)
한 개 노드에 연결되어 있는 정점을 찾기에 간편.
단점
노드 i와 j의 인접 여부를 확인하려면 i에 연결되어있는 모든 정점을 확인해야 하므로 느림(최악의 경우 O(V) 사용)
구현이 비교적 어려움
정리하면,
인접 행렬 : 메모리를 많이 사용하지만, 탐색이 빠르고 간선이 많을수록 효율적
인접 리스트 : 메모리는 간선의 개수만큼만 사용하지만, 탐색이 느림, 구현 어려움