그래프는 여러개의 정점(Vertex)들이 간선(Edge)들로 서로 복잡하게 연결되있는 관계를 표현한 자료구조이다.
직접적인 관계가 있는 경우에는 두 정점 사이를 직접적으로 이어주는 간선이 있으며 간접적인 관계라면 몇개의 정점들과 간선들에 걸쳐 이어진다.
리스트, 트리, 그래프
리스트, 트리, 그래프 모두 비슷한 구조를 가지고 있다.
- 리스트 : 하나의 노드에 다른 하나의 노드가 연결되있고 또 다른 노드들이 체인처럼 직렬로 연결된 형태
- 트리 : 리스트와 같이 하나의 진행방향을 가지지만 하나의 노드에 여러 노드가 병렬적으로 연결된 형태
- 그래프 : 각 노드들이 순서와 개수에 상관없이 무작위로 연결된 형태
위와 같은 특징을 가지고 있으며 리스트에서 그래프로 점차적으로 진화된 형태를 띄고 있다.
이에 따라 그래프는 다른 자료구조들과 비슷하지만 더 유동적이고 자율성이 좋으며 많은 곳에 사용된다. ex)소셜네트워크, 네비게이션 등
그래프 자료구조의 용어
- 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소.
- 간선 (edge): 정점 간의 관계를 나타내는 선. (정점을 이어주는 선)
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻함.
- 가중치 그래프 (weighted Graph): 연결의 강도(네비게이션의 거리와 같이 추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프. (간선의 정보)
- 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프.
- 단(방)향 그래프 (directed graph): 두 정점을 잇는 간선이 한쪽으로만 방향성을 가지는 경우. 보통 간선을 화살표로 표시. ex) 네비게이션의 일방통행, Instagram의 following 혹은 follower
- 무(방)향 그래프 (undirected graph): 단방향과 달리 서로 연결된 두 정점이 모두 상대방의 방향을 가질수 있는 경우. ex) Facebook의 친구 추가
- 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄.
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점.
- 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우이며 다른 정점을 거치지 않는다는 것이 특징.
- 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프.
인접행렬(Adjacency Matrix)과 인접리스트(Adjacency List)
리스트 자료구조에서는 각 노드에 연결된 다른 노드들에 대한 정보 즉, next와 previous와 같은 정보들이 담겨있고 트리 자료구조의 경우 left와 right와 같은 자식노드들에 대한 정보가 담겨 있다. 하지만 그래프의 경우 불특정 다수의 정점들과 연결되 있기 때문에 각각의 정점들이 자신과 인접한 모든 정점들의 정보를 가지기가 힘들다. 이런 그래프의 연결 관계도를 나타낼수 있는 가장 흔한 2가지 방법이 인접행렬(Adjacency Matrix)과 인접리스트(Adjacency List)이다.
인접행렬(Adjacency Matrix)
이름과 같이 2차원의 행렬로 표현한다. 행과 열을 이용하여 간선의 정보를 표현하며 보통 행은 자신의 정점을 의미하고 열을 자신을 제외한 다른 정점들을 의미한다. 그리고 안의 표에는 간선들을 의미하며 0 혹은 1과 같이 boolean형식으로 표현한다.
만약 새로운 정점이 생성된다면 행과 열을 각각 1줄씩 추가한다.
인접리스트(Adjacency List)
각각의 정점들은 자신만의 독립적인 리스트(리스트, 배열 등 직렬형태의 어떠한 자료구조든 상관없음)를 가지며 그 리스트안에 자신과 인접한 정점, 즉 자신과 간선으로 연결된 다른 정점을 가리킨다. 위의 예시와 달리 각 정점의 이름이 잘 정렬된 숫자형 타입이 아니라면 해시테이블을 사용할수 있다. ex) { A:["B","C"], B:["A"], C:["A"]}
간단한 인접리스트 구현
Vancouver: [ 'Brisbane' ],
Brisbane: [ 'Vancouver' ]
}
간략히 설명하자면
- Graph클래스에 adjacencyList라는 객체를 생성
- addVertex()메서드를 호출하면 받은 매개인자(추가할 정점의 이름)을 이용하여 adjacencyList객체에 빈 배열을 가진 정점을 추가한다. (이 배열에 해당 정점과 연결된 다른 정점들을 넣게된다.
- removeVertex()메서드를 호출하면 adjacencyList객체 안에서 매개변수(삭제할 정점)의 배열안의 다른 모든 정점들을 반복문을 통해 접근하여 삭제할 정점을 모두 지워준다. 이후 삭제할 정점을 adjacencyList객체 안에서도 제거해준다.
- addEdge()메서드는 연결할 정점 두개를 매개인자로 전달받아 객체내의 두 정점의 배열안에 상대방의 정점을 추가하면 서로간에 간선이 추가되며, Directed 그래프의 경우 하나의 시작정점에만 상대 정점을 추가한다.
- removeEdge()메서드 또한 두개의 정점의 이름을 매개인자로 받으며 해당 정점들의 배열에서 각 상대방 정점들의 이름을 제거해준다.
정점을 추가하거나 제거해줄때에는 해당 정점의 이름만을 매개인자로 보내주었지만 간선을 추가해 줄때는 해당 정점과 연결될 상대 정점의 이름들을 보내 주어야 했다.
해당 메서드들을 구현하면서 중요했던것은 간선을 연결하거나 끊을때 혹은 정점을 제거할때 꼭 해당 정점과 연결된 다른 정점들 또한 수정해 주어야 한다. 특히나 Undirected 그래프의 경우 더더욱 신경 써주어야 한다.
인접행렬과 인접리스트의 Big O
| 인접 행렬 | 인접 리스트 | |
| 정점 추가 | O(V²) | O(1) |
| 간선 추가 | O(1) | O(1) |
| 정점 삭제 | O(V²) | O(V+E) |
| 간선 삭제 | O(1) | O(E) |
| 특정 간선에 접근 | O(1) | O(V+E) |
| 공간 복잡도 | O(V²) | O(V+E) |
V=정점의 개수, E=간선의 수
간선의 삭제와 특정 간선에 접근하는 경우만 제외하면 인접리스트의 효율이 월등히 좋다.
이유는 인접행렬의 경우 각 정점과 간선들의 위치가 고정이기에 해당 인덱스로 직접적으로 접근이 가능하기에 간선의 삭제와 특정 간선에 대한 접근이 간편하다.
하지만 각 정점마다 다른 모든 정점들간의(연결되어 있지 않은 정점들 포함) 관계를 표시하기때문에 다른 기능들의 효율 과 공간 복잡도 효율이 좋지 못하다. 만약 어떠한 그래프의 정점들이 모두 연결되어있다면 인접리스트와 성능차이가 크게 나지 않겠지만 실제로 그런 경우를 기대할수 없을 것 같다.
'Datastructure & Algorithm' 카테고리의 다른 글
| 동적 계획법(Dynamic Programming, DP) (0) | 2023.03.22 |
|---|---|
| 그래프 순회 (DFS, BFS) (0) | 2023.03.20 |
| Binary Heap(이진 힙)과 Priority Queue(우선순위 큐) (0) | 2023.02.14 |
| Tree Traversal (트리 순회), BFS, DFS (0) | 2023.02.08 |
| Binary Search Tree (이진 검색 트리) (0) | 2023.02.08 |