그래프의 활용 범위는 다양한 것 같다. 네트워크 분석, 경로 찾기, 최적화 문제 등 다양한 문제를 해결하는 데 사용된다. 모든 내용을 다루지는 못하더라도 꼭 필요한 내용을 중심으로 공부하자
Graph 자료구조란?
그래프(graph)는 정점(Vertex, 또는 Node라고도 함)과 이들을 연결하는 간선(Edge)으로 구성된 자료구조를 말한다. 즉, 연결되어 있는 객체간의 관계를 표현하는 자료구조이다. 방향성이 있는 방향 그래프와 방향성이 없는 무방향 그래프로 나뉘며, 간선에 가중치가 있을 수도 있다. 이러한 그래프 자료구조는 컴퓨터 네트워크, 교통 시스템, 소셜 미디어와 같은 다양한 현실 세계의 문제를 모델링하는 데 사용된다.
그래프와 관련된 용어
- 정점(vertex): 위치라는 개념. (node 라고도 부름)
- 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
- 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
- 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
- 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
- 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
- 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
- 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
- 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
- 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
트리와는 어떤 차이가 있을까?
트리는 그래프 범주 안에 속하며 그 중에서도 특수한 케이스에 해당하는 자료구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다. 이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다. 부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.
그래프의 종류
1. 무방향 그래프
- 간선에 방향이 없는 그래프이다.
- 노드와 간선으로 이루어져 있으며, 노드 사이의 관계는 양방향이다.
2. 방향 그래프
- 간선에 방향이 있는 그래프이다.
- 노드와 간선으로 이루어져 있으며, 노드 사이의 관계는 일방향이다.
3. 가중치 그래프
- 간선에 가중치가 있는 그래프이다.
- 가중치는 간선의 비용, 거리, 시간 등을 나타낸다.
4. 이분 그래프
- 무방향 그래프에서, 노드를 두 그룹으로 나누었을 때, 같은 그룹 내의 노드는 서로 인접하지 않고 다른 그룹의 노드와만 인접하는 그래프이다.
5. 비순환 그래프
- 사이클이 없는 그래프이다.
- 방향 그래프에서, 유향 비순환 그래프(Directed Acyclic Graph, DAG)라고도 한다.
6. 완전 그래프
- 모든 노드가 서로 연결된 그래프이다.
- 노드 수가 n일 때, 간선 수는 n(n-1)/2이다.
- 완전 그래프는 항상 연결 그래프를 포함한다.
7. 부분 그래프
- 주어진 그래프의 일부 노드와 간선으로 이루어진 그래프이다.
8. 연결 그래프
- 무방향 그래프에서, 모든 노드 사이에 경로가 존재하는 그래프이다.
9. 비연결 그래프
- 무방향 그래프에서, 연결 그래프가 아닌 그래프이다.
10. 강결합 그래프
- 방향 그래프에서, 모든 노드 사이에 양방향 경로가 존재하는 그래프이다.
그래프의 구현방법
그래프를 구현하는 방법으로는 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 방법이 있다. 인접 리스트는 각 정점에 대해 연결된 모든 정점의 리스트를 저장하는 방식으로, 특정 정점과 인접한 정점들을 바로 알 수 있다는 장점이 있다. 인접한 노드를 리스트에 저장하고 양방향으로 저장된 것을 볼 수 있다.
반면 인접 행렬은 2차원 배열을 사용하여 노드 간의 연결 관계를 행렬 형태로 나타내는 방식이다. 노드 간의 연결 여부를 빠르게 확인할 수 있다는 장점이 있지만, 모든 각 정점에 관한 관계를 기록하기 때문에 메모리 소비가 더 크다는 단점이 있다. 따라서 인접 행렬은 그래프 간선이 많은 그래프에 주로 사용하고, 인접 리스트는 상대적으로 간선이 적은 그래프에서 주로 사용한다.
그래프 알고리즘의 종류
1) 그래프 탐색 알고리즘
그래프 탐색 알고리즘(Graph Search Algorithms)은 그래프에서 특정 정점을 찾는 알고리즘을 말한다. 이렇게 그래프 내 특정 정점을 찾기 위해서는 그래프의 각 정점을 순회하면서 방문해야 하므로, 그래프 순회 알고리즘(Graph Traversal Algorithms)으로 부르기도 한다. 기본적인 그래프 탐색 알고리즘 종류로는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다.
2) 최단 경로 알고리즘
최단 경로 알고리즘은 가중치가 있는 그래프에서 두 정점 간의 최소 가중치 합을 가지는 경로를 찾는 알고리즘을 말한다. 대표적인 최단 경로 알고리즘으로는 다익스트라 알고리즘(Dijkstra Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 플로이드 알고리즘(Floyd Algorithm)등이 있으며, 네트워크 설계, 교통 시스템 최적화, 지리적 경로 탐색 등 다양한 분야에서 경로 최적화 문제를 해결하는 데 활용한다.
3) 그 밖의 그래프 알고리즘
그래프 알고리즘에는 그래프 탐색과 최단 경로 찾기 외에도 다양한 알고리즘이 있다. 그 중 하나인 위상 정렬(Topological Sorting) 알고리즘은 방향성이 있는 그래프에서 각 정점을 선후 관계에 따라 나열하는 알고리즘이다. 이는 주로 의존성이 있는 여러 작업을 순서대로 정렬하는 데 사용되며, 프로젝트 스케쥴링이나 컴파일러의 작업 순서 결정 등에 활용되고 있다.
이 밖에도 그래프의 모든 정점을 최소한의 간선으로 연결하는 부분 그래프를 찾는 최소 신장 트리(Minimum Spanning Tree) 알고리즘도 있다. 최소 신장 트리 알고리즘은 네트워크 설계, 클러스터링, 물리적 인프라 계획 등에서 중요한 역할을 한다. 대표적인 최소 신장 트리 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있다.
참고
https://bigsong.tistory.com/33
https://hazel-developer.tistory.com/268
https://yozm.wishket.com/magazine/detail/2411/
'자료구조' 카테고리의 다른 글
| [자료구조 Heap / Java] (0) | 2024.05.10 |
|---|
