그래프(Graph) 란?
그래프(graph) 란 객체 사이의 연결 관계를 표현할 수 있는 자료구조 입니다. 그래프는 오일러가 처음으로 사용했다고 알려져 있는데요, 아래 문제는 오일러의 "Konigsberg bridge problem" 이라고 불리는 문제입니다.
"Konigsberg bridge problem" 란 임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가? 를 묻는 문제입니다. 이 문제의 정답은 "없다" 입니다. 오일러가 '어떤 한 지역에서 시작하여 모든 다리를 한 번씩만 지나서 처음 출발점으로 되돌아오려면 각 지역에 연결된 다리의 개수가 모두 짝수"이어야 한다는 것을 증명했죠. 그 때 오일러는 위 문제를 아래 그림처럼 간단히 바꿔서 증명했습니다.
이 문제에서의 핵심은 'A, B, C, D의 위치가 어떠한 관계로 연결되었는가?' 의 아이디어로 오일러는 특정 지역은 정점(Node, Vertex), 다리는 간선(Edge) 로 표현 하여 그래프 문제로 변환해서 풀었습니다.
위처럼 그래프란 객체를 나타내는 정점(Vertex) 와 간선(Edge) 로 구성된 집합을 말합니다. 자료구조적인 그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조를 말합니다.
그래프의 종류
방향 그래프 vs 무방향 그래프
간선에 방향이 있는 그래프를 방향 그래프(Directed Graph) 라고 하며 간선에 방향이 없는 그래프를 무방향 그래프(Undirected Graph) 라고 합니다. 차후 배울 트리는 대표적인 무방향 그래프입니다.
완전 그래프
완전 그래프(Complete Graph) 는 각 정점에서 다른 모든 정점이 연결된, 최대한 많은 간선 수를 가진 그래프를 뜻합니다.
정점이 n 개인 무방향 그래프에서의 최대 간선 수는 n(n-1) / 2 개가 되고, 정점이 n개인 방향 그래프에서의 최대 간선 수는 n(n-1) 개가 됩니다.
부분 그래프
부분 그래프(Subgraph) 는 원래 그래프에서 일부 정점이나 간선을 제외하고 만든 그래프입니다. 그래프를 정점과 간선의 집합으로 정의하면 부분 집합이 곧 부분 그래프가 됩니다.
가중치 그래프
가중치 그래프(Weighted Graph) 는 간선에 가중치가 부여되어 있는 그래프를 뜻합니다. 쉽게 생각하여 각 도시간의 거리를 간선의 가중치로 생각할 수도 있습니다. 가중치 그래프는 다른 이름으로 네트워크(Network) 라고도 합니다.
연결그래프 vs 비연결그래프
연결 그래프(Connected Graph) 는 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프를 말하고, 비연결 그래프는 연결되지 않은 정점이 있는 그래프를 뜻합니다.
그래프 관련 용어
- 인접(adjacent) : 두 정점을 연결하는 간선이 있을 때 서로 인접하다고 합니다.
- 부속(incident) : 인접한 두 정점사이의 간선은 두 정점에 부속되어 있다고 합니다.
- 차수(degree) : 차수는 정점에 부속되어 있는 간선 수를 뜻합니다. 무방향그래프에서는 정점에 연결된 간선의 수를 뜻하지만, 방향 그래프에서는 진입차수(in-degree)와 진출차수(out-degree) 가 다를 수 있습니다.
- 경로(path) : 그래프에서 간선을 따라갈 수 있는 길을 정점으로 나열한 것 (ex : A->B->C->D)
- 경로 길이(path length) : 경로를 구성하는 간선의 수
- 단순 경로(simple path) : 모두 다른 정점으로 구성된 경로
- 사이클(cycle) : 한 정점에서 시작해 해당 정점으로 끝나는 경로(ex : A - B - C - D - A)
- DAG(Directed Acyclic Graph) : 방향 그래프이면서 사이클이 존재하지 않는 그래프. 어떤 정점에서 출발해도 자기 자신으로 돌아오는 경로가 없는 그래프
그래프 구현
그래프의 구현은 2가지 방법이 있습니다.
1. 인접 행렬 (Adjacent matrix)
2. 인접 리스트 (Adjacent list)
무방향 그래프를 인접행렬로 구현하면 위 그림과 같습니다. 정점들을 배열의 인덱스로 표현하고 간선은 배열 내의 값으로 두 정점이 연결되어 있다면 1로, 두 정점이 연결되어 있지 않다면 0으로 표현합니다. 또한 자기 자신으로 연결되는 self-loop 가 없으므로 배열의 대각선은 모두 0이고 A->B 가 연결되어 있다면 당연히 B->A 도 연결되어 있기 때문에 무방향 그래프를 인접배열로 구현하면 배열은 대각선을 기준으로 대칭 (symmetric) 입니다.
방향 그래프를 인접 행렬로 구현한다면 대칭 구조가 아니게 됩니다. A -> B 는 1이지만, B -> A 는 0인 경우가 생기는 것이죠. 대각선에는 self-loop 가 없으므로 0이 나오는 특징은 무방향 그래프와 동일합니다.
즉 인접 행렬로 그래프를 나타내는 방법은 정점의 개수가 V개 라면 V*V 행렬을 선언한 이후, 인덱스에 맞는 정점들간의 연결에 간선에 맞는 값들, 간선이 있으면 1, 없으면 0 을 써주면 되겠죠?
무방향 그래프를 인접리스트로 구현하면 위 그림과 같습니다. 각각의 정점을 head로 시작해 인접한 노드들을 전부 연결리스트로 연결해주면 됩니다. A 정점만 보면 B와 D에 연결되어 있다는 것을 A -> B -> D 로 표현한 겁니다.
B 정점만 보면 이는 3개의 정점 모두에 연결되어 있으니 노드의 개수가 4개가 되는 것이고, 나머지 정점도 동일한 방식으로 나타냅니다.
방향 그래프도 동일한 방식으로 각 정점을 head 로 시작해 들어가는 노드를 모두 연결리스트로 연결해주면 됩니다.
인접 행렬 vs 인접 리스트
그래프를 인접행렬로 구현하는 것과 인접리스트로 구현하는 것 중 어떤 것이 더 효율적일까요?
정답은 "상황에 따라 다르다" 입니다. 그러면 어떤 상황에서는 행렬이 유리하고 어떤 상황에서는 리스트가 유리한지 알아보겠습니다.
밀집 그래프 vs 희소 그래프
정점에 비해 간선의 수가 적은 그래프를 희소 그래프(sparse graph) 라고 합니다. 예를 들어 정점이 100개인데, 간선이 3개만 있는 경우입니다. 이 때 이 그래프를 인접행렬로 구현하게 되면 100*100 행렬이 필요하고, 실제로 무방향 그래프라고 가정하면 그 행렬 안에 1 값은 단 6개만 있고 나머지 값은 모두 0으로 차게 될 겁니다.
그러나 연결리스트로 구현하면 106 개의 노드만 있으면 됩니다. 만약 방향 그래프라면 행렬 안에 1값은 3개가 있을 것이고 연결리스트는 103개의 노드로 구성됩니다. 이를 정확히 따지는 것이 공간복잡도(Space Complexity) 라는 개념인데 인접행렬의 공간복잡도는 O(V^2) 이고 인접리스트의 공간 복잡도는 O(V+E) 입니다.
따라서 인접리스트는 희소 그래프를 표현하는데 적절한 방법입니다.
반면 정점에 비해 간선의 수가 많은 그래프를 밀집 그래프(dense graph) 라고 합니다. 정점은 100개인데 간선은 200개 있는 그래프가 있다고 생각해보겠습니다. 이 때는 인접행렬로 그래프를 구현하는 것이 더 효과적입니다. 그 이유는 행렬의 접근성 때문입니다.
어떤 정점이 다른 정점과 연결되었는지 확인하고 싶을 때 배열은 인덱스를 이용하여 O(1) 이면 충분하지만, 인접리스트는 head 부터 시작해서 해당 노드를 찾을 때까지 탐색을 해야하므로 시간이 더 오래걸리게 됩니다.
여기까지 그래프의 정의와 종류, 그리고 대표적인 구현방식 2개인 인접 행렬과 인접 리스트 구현 방식에 대해 알아보고 어떤 방식이 언제 더 효율적인지까지 알아보았습니다. 감사합니다.
참고 및 이미지 출처 :
https://code-lab1.tistory.com/13
C언어로 쉽게 풀어쓴 자료구조 - 생능출판사
'C 자료구조' 카테고리의 다른 글
| [C 자료구조] 트리(Tree) 의 종류 (0) | 2023.05.25 |
|---|---|
| [C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트 (2) | 2023.05.25 |
| [C 자료구조] 큐(Queue) - 연결리스트 구현 (0) | 2023.05.24 |
| [C 자료구조] 큐(Queue) - 선형큐 / 원형큐 배열 구현 (0) | 2023.05.23 |
| [C 자료구조] 연결리스트(Linked List) (0) | 2023.05.22 |