💡그래프(Graph)란?
그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조로, 정점(노드)과 간선들의 집합으로 구성된다.
✅그래프 관련 용어
- 정점(vertex) : 노드라고도하며, 데이터가 저장되는 그래프의 기본 원소이다
- 간선(edge) : 링크,arcs라고도 불리며, 노드 간의 관계를 나타낸다.
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결되어 있는 정점 (
A-B,A-C,C-D,A-D) - 차수(degree) : 무방향 그래프에서 하나의 정점에 연결된 간선의 수를 말한다.(정점 A의 차수 : 3)
- 경로(path) : 간선을 따라갈 수 있는 길을 뜻하며, 정점을 나열하여 표시한다.
- 경로의 길이(length) : 경로를 구성하는데 사용된 간선의 수를 뜻한다.
- 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없는 경로를 뜻한다.
- 사이클(cycle) : 시작 정점과 종료 정점이 같은 단순 경로를 뜻한다(
A-C-D-A경로)
💭그래프를 표현하는 방법
- V(G1) = {0,1,2,3}, E(G1) = {(0,1),(0,2),(0,3),(1,2),(2,3)}
- V(G2) = {0,1,2,3}, E(G2) = {(0,1),(0,2)}
- V(G3) = {0,1,2}, E(G3) = {<0,1>,<1,0>,<1,2>}
📋그래프의 종류
1. 무방향성 그래프(Undirected Graph)
- 무방향성을 가진 그래프
- 무방향 그래프는 모든 간선이 양방향
2. 유방향성 그래프(Directed Graph, digraph)
- 방향성을 가진 그래프
- 방향성 그래프는 모든 간선이 단방향
3. 가중치 그래프(Weighted Graph)
- 각 간선마다 가중치 또는 비용이 할당된 그래프
4. 연결 그래프(Connected Graph) / 비연결 그래프(Disconnected Graph)
- 모든 정점이 연결되어 있으면 연결그래프
- 그렇지 않으면 비연결 그래프
- G1은 모든 정점이 연결되어 있으므로 연결 그래프
- G2는 {0,1}, {2,3,4,5)가 연결되어 있지 않아 비연결 그래프
5. 순환 그래프(Cyclic Graph) / 비순환 그래프(Acyclic Graph)
- 순환(Cycle)을 가지고 있으면 순환 그래프
- 그렇지 않으면 비순환 그래프
- n개의 정점이 사이클을 이루고 있을 경우 Cn이라고 표시
6. 희소 그래프(Sparse Graph) / 밀집 그래프(Dense Graph)
- 희소 그래프 : 노드 수보다 간선 수가 적은 그래프
- 밀집 그래프 : 노드 수보다 간선 수가 큰 그래프
7. 단순 그래프(Simple Graph)
- 중복된 간선과 loop가 없는 그래프
- 단순 그래프에서 정점의 개수가 n이라고 했을 때, 최대 n-1개의 간선을 가질 수 있다
8. 완전 그래프(Complete Graph)
- 간선의 수가 최대인 그래프
- 정점의 수가 n개 이면 Kn으로 표시
- 정점의 수 : n , 간선의 수 : n*(n-1)/2
📊그래프의 구현
1. 인접 행렬(Adjacent matrix)
무방향 그래프의 인접 행렬
- 정점들을 배열의 인덱스로 표현하고, 간선은 배열 내의 값으로, 두 정점이 연결되어 있다면 1, 연결되어 있지 않다면 0으로 표현
- 자기 자신으로 연결되는 self loop가 없으므로 배열의 대각선은 모두 0
- A->B가 연결되어 있다면 B->A도 연결되어 있기 떄문에 무방향 그래프를 인접 행렬로 구현하면 대각선을 기준으로 대칭이 된다.
- 인접 행렬의 공간 복잡도는 O(V²)이다. (V : 정점 수(노드의 개수))
유방향 그래프의 인접 행렬
- 유방향 그래프를 인접 행렬로 구현하면 대칭구조가 아니다.
- 유방향 그래프도 self-loop가 없으므로 대각선에는 0이 나오는건 동일
2. 인접 리스트(Adjacent list)
무방향 그래프의 인접 리스트
- 각각의 정점을 head로 시작해서 인접한 노드들을 전부 연결리스트로 연결
- A정점은 B와 D에 연결되어 있으므로 A->B->D로 표현
- 다른 정점도 동일
- 인접 리스트의 공간 복잡도는 O(V + E)이다. (V : 정점 수(노드의 개수), E : 간선의 수)
유방향 그래프의 인접 리스트
- 방향 그래프도 동일
☑️인접 행렬 VS 인접 리스트
🤔그래프를 인접 행렬과 인접 리스트로 구현하는 것중 어떤 것이 더 효율적일까?
정답은 "상황에 따라 다르다." 이다.
그렇다면 어떤 상황에서는 행렬이 유리하고, 어떤 상황에서는 리스트가 유리한지 알아보자.
📌희소 그래프 vs 밀집 그래프
그래프 표현 방식은 그래프가 희소 그래프인지, 밀집 그래프인지에 따라 선택한다.
위 그래프의 종류 설명 시, 정점에 비해 간선의 수가 적은 그래프를 희소 그래프라 했는데, 예를 들어 그래프의 정점이 100개 인데, 간선이 3개만 있는 경우를 희소 그래프라고 한다.
이 때, 이 그래프를 인접행렬로 구현하게 된다면 인접 행렬의 시간복잡도는 O(V²)이므로 100*100의 행렬이 필요하고, 무방향 그래프라고 가정하면 그 큰 행렬 안에 1값은 단 6개만 있는 행렬이 구현될 것이다.(메모리 낭비가 심하다)
그러나 인접 리스트로 구현하면 공간 복잡도 O(V + E)로 인해 106개의 노드만 있으면 된다. 방향 그래프라면 103개면 구현이 완료된다.
따라서, 인접 리스트는 희소 그래프를 표현하는데 적절한 방법이다.
반면, 정점에 비해 간선의 수가 많은 그래프를 밀집 그래프라고 한다. 만약 정점이 100개인데 간선이 200개 있는 그래프가 있다고 생각해보자. 간선이 많아 E ≈ V²가 되면 인접 리스트의 O(V + E)가 결국 O(V²)에 가까워져 두 표현의 비용이 비슷해진다. 또한 알고리즘의 특성상 간선 존재 확인을 매우 자주 수행해야 한다면 인접 행렬은 O(1)로 즉시 확인 할 수 있어 시간면에서 유리하다.
어떤 정점이 다른 정점과 연결되어 있는지 확인하고 싶을 때 배열은 인덱스를 이용하여 O(1)이면 충분하지만, 인접 리스트는 head부터 해당 노드를 찾을 때까지 탐색을 해야하므로 시간이 더 오래걸리게 된다. 즉, 밀집 그래프는 인접 행렬로 구현하는 것이 더 효과적이다.
| 항목 | 인접 행렬 (Adjacency Matrix) | 인접 리스트 (Adjacency List) |
|---|---|---|
| 공간 복잡도 | O(V²) | O(V+E) |
| 정점의 인접 노드 탐색 | O(1) | O(n), n : 연결된 노드 개수 |
| 구현에 유리한 그래프 | 밀집 그래프 | 희소 그래프 |
