내용에 대한 출처는 ‘이것이 취업을 위한 컴퓨터 과학이다’에 책에서 CHAPTER 04 자료구조에서 - 6 그래프에 대한 내용입니다.
그래프란
그래프(Graph)는 정점(Vertex)이라 불리는 데이터를 간선(Edge) 혹은 링크(Link)로 연결한 형태의 자료구조이다.
이전에 배웠던 트리(Tree)도 사실 그래프의 일종으로, 사이클이 없는 특별한 형태의 그래프라고 볼 수 있음.
트리는 노드 간 상하 관계(부모-자식 관계)를 가지며 사이클이 없지만,
그래프는 보다 일반적인 연결 관계를 표현할 수 있어 사이클을 가질 수 있으며, 정점들 간에 명확한 상하 구조도 없다.
예를 들어 SNS에서 친구 관계처럼 상하 관계 없이 서로 연결되는 구조는 트리가 아닌 그래프가 적합함.
특정 정점에서 출발해서 다시 처음 출발했던 정점으로 되돌아오는 경로가 존재한다면, 우리는 이 그래프에 사이클이 존재한다고 표현한다.
즉, 그래프는 기본적으로 데이터 간의 복잡한 연결 관계를 표현할 수 있는 자료구조이다.
그래프의 기본 유형
연결 그래프 (Connected Graph)
그래프 상의 임의의 두 정점 사이에 항상 경로가 존재하는 그래프
→ 아무 두 정점을 골라도 간선을 통해 서로 도달 가능하면 연결 그래프이다.
비연결 그래프 (Disconnected Graph)
어떤 정점 쌍 사이에 경로가 존재하지 않는 경우가 있는 그래프
→ 예: 하나의 그래프 안에 '섬'처럼 분리된 부분이 있을 수 있다.
방향 그래프 (Directed Graph)
간선이 방향을 가지는 그래프
→ A에서 B로 가는 간선이 있어도, B에서 A로는 갈 수 없을 수 있음.
무방향 그래프 (Undirected Graph)
간선에 방향이 없는 그래프
→ A와 B가 연결되어 있다면, B와 A도 자동으로 연결된 상태
가중치 그래프 (Weighted Graph)
간선에 가중치(비용)가 부여된 그래프
→ 예: 지도에서 역과 역 사이의 거리를 가중치로 둘 수 있음.
그래프의 표현 방식
인접 행렬 (Adjacency Matrix)
- 정점이 N개일 때, N × N 크기의 2차원 배열(행렬)로 표현한다.
- 행(i), 열(j)은 각각 정점 i에서 정점 j로의 간선 존재 여부를 나타냄
일반적으로
- 연결되어 있다면 1
- 연결되어 있지 않다면 0
- 예: graph[1][2] = 1이면, 1번 정점에서 2번 정점으로 간선 존재
인접 행렬은 구현이 단순하지만, 공간 복잡도가 O(N²)로 정점 수가 많을 때 비효율적이다.
인접 리스트 (Adjacency List)
- 각 정점마다 연결된 정점들의 리스트를 저장
- 무방향 그래프의 경우, 연결된 정점을 양방향으로 리스트에 추가
- 가중치 그래프는 각 연결된 정점과 함께 가중치 정보도 저장 → 예 : (2, 5)는 정점 2로 가는 간선의 가중치가 5라는 의미
인접 리스트는 공간을 더 효율적으로 사용하며, 간선 수가 적은 희소 그래프에 적합함.
그래프 탐색 알고리즘
깊이 우선 탐색 (DFS: Depth-First Search)
- 가능한 한 깊이 들어가며 탐색하는 방식
- 더 이상 갈 수 없을 때 되돌아와서(backtrack) 다른 경로 탐색
구현 시에 보통은
- 방문 여부를 체크하는 배열
- 되돌아올 정점을 기억하기 위한 스택 사용
재귀 함수나 스택을 통해 구현되며, 미로 탐색 같은 문제에 적합
너비 우선 탐색 (BFS: Breadth-First Search)
- 한 정점에서 인접한 모든 정점을 우선 방문한 후,
- 그다음 레벨의 정점을 넓게 확장하며 탐색하는 방식
구현 시 보통
- 방문 여부 배열
- 탐색 대기열을 위한 큐(Queue) 사용
BFS는 최단 경로를 찾는 문제에서 자주 사용됨. (ex. 최단 횟수로 탈출하기 등)
최단 경로 알고리즘
최단 경로 알고리즘은 출발 정점에서 목적지 정점까지의 가중치 합이 가장 작은 경로를 찾는 알고리즘이다.
실생활 예시 : 카카오맵, 네이버 지도에서 목적지까지의 최단 거리 찾기
대표적인 알고리즘은
- 다익스트라(Dijkstra) : 음의 가중치가 없는 경우
- 벨만-포드(Bellman-Ford) : 음의 가중치 허용
- 플로이드-워셜(Floyd-Warshall) : 모든 정점 쌍 간 최단 경로
