💁♀️ 그래프 (Graph)
그래프는 여러 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다. 정확히는 정점(Vertex)간의 관계를 표현한 조직도이다. 직접적인 관계가 있다면 두 정점 사이를 이어주는 간선(edge)이 있고, 간접적인 관계가 있다면 몇 개의 점과 선에 걸쳐서 이어진다.
그래프 개념
- 정점(Vertice): 노드(node)라고도 하는 데이터가 저장되는 그래프의 기본 원소.
- 간선(Edge): 정점 간의 관계를 나타내는 선
- 인접 정점(Adjacent Vertex): (하나의 정점에서) 간선에 의해 직접 연결되어 있는 정점.
- 단순 경로(Simple-path): 경로 중 반복되는 정점이 없는 것. 같은 간선을 지나가지 않는 경로.
- 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수. (위 이미지의 경우 4의 차수는 3.)
- 진출 차수(Out-degree): 한 정점에서 진출(나가는 간선)하는 간선의 수.
- 진입 차수(In-degree): 한 정점에서 진입(들어노는 간선)하는 간선의 수.
- 사이클(Cycle): 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다. (ex. 서울>대전>부산>서울)
- 자기 루프(Self Loop): 정점에서 진출하는 간선이 바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 표현한다.
✨ 그래프 구현
그래프를 구현하는 방식에는 인접 행렬(Adjacency Matrix)와 인접 리스트(Adjacency List) 방식이 있다.
인접 행렬 (Adjacency Matrix)
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 2차원 배열 형태의 행렬이다. 이어져있다면 1(true), 그렇지 않다면 0(false)로 표시한다.인접 행렬은 정점 간 관계 유무를 파악하는데 주로 사용하며, 이때의 시간 복잡도는 O(1)이다. 가장 빠른 경로를 찾고자 할 때도 많이 사용된다. 다만 데이터가 커짐에 따라 2차원 배열도 계속 커지기 때문에 많은 공간을 낭비하고, 모든 정점에 대한 간선 정보를 대입해야 해서 O(n^2)의 시간 복잡도가 소요된다.
인접 리스트 (Adjacency List)
인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 인접 리스트는 인접 행렬에 비해 공간 낭비가 적어서 메모리를 효율적으로 사용할 수 있다. 또한 연결 정보를 탐색할 때도 O(n)의 시간이면 충분하다. 다만 특정 점들이 연결되어 있는지 확인하려면 시간이 오래 걸리고, 구현이 비교적 어렵다는 단점이 있다.
👉 그래프 종류
- 무방향 그래프: 두 정점을 연결하는 간선에 방향이 없는 그래프.
- 방향 그래프: 두 정점을 연결하는 간선에 방향이 있는 그래프. (방향으로만 이동 가능)
- 가중치 그래프: 두 정점을 이동할 때 가중치만큼의 비용이 드는 그래프.
- 완전 그래프: 모든 정점이 간선으로 연결되어 있는 그래프.
🌀 그래프 탐색
그래프는 배열처럼 정렬이 되어 있지 않기 때문에 원하는 자료를 찾으려면 특정한 방법으로 탐색해야 한다. 두 가지 대표적인 탐색법인 BFS와 DFS에 대해 알아보자.
DFS (Depth-First Search)
DFS(깊이 우선 탐색)는 하나의 정점에서 시작해 해당 경로를 끝까지 탐색한 후, 다음 경로로 넘어가 탐색한다. 하나의 경로를 끝까지 보기 때문에 운이 좋다면 원하는 자료를 몇 번 만 에 찾을 수 있다. 재귀호출 혹은 스택을 사용해 구현한다.
BFS (Breadth-First Search)
BFS(너비 우선 탐색)는 시작 정점을 방문한 후, 인접한 모든 정점을 방문한 하고, 시작 정점에서 인접한 모든 정점을 우선방문하는 방법이다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 일반적으로 큐를 사용해서 현재 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현한다.
참고자료
