안녕하세요,
오늘은 알고리즘에 사용되는 자료구조를 정리해보려고 합니다.
알고리즘 문제 풀이에 대표적으로 사용되는 자료구조증 하나, 그래프에 대하여 정리해보겠습니다.
그래프(Graph), 혹은 그래프 이론(Graph Theory)라고 불리는 이 자료구조는, DFS, BFS 문제를 푸는 데 기초가 되는 이론이고,
나아가 위상정렬 등의 문제를 푸는 데도 기초가 됩니다.
트리 문제도 그래프 이론에서 출발하죠!
그래서 저도 기초를 다시 다지기 위해서 정리해봅니다. :)
그래프 이론(Graph Theory) 기초 개념 정리
그래프는 현실 세계의 네트워크, 관계, 연결구조를 수학적으로 표현한 자료구조 입니다.
소셜 네트워크, 지도, 컴퓨터 네트워크, 알고리즘 문제 등에서 필수적으로 사용됩니다.
그래프란?
: 그래프란 정점(Vertex, Node)과 간선(Edge)으로 이루어진 구조
정점(Node): 데이터를 표현하는 점 (ex. 사람, 도시, 서버 등)
간선(Edge): 두 정점을 연결하는 선 (ex. 친구 관계, 도로, 네트워크 등)
> 예시 그림 (무 방향 그래프; Undirected Graph)
A --- B
| |
C --- D
- 정점: A, B, C, D
- 간선: (A-B), (A, C), (B, D), (C, D)
이렇게 간단히 정의해볼 수 있습니다.
그래프의 종류
그래프의 종류는 아래와 같이 여러가지 구분 기준에 따라 종류를 나눌 수 있습니다.
a) 방향성에 따른 구분
| 구분 | 설명 | 예시 |
| 무방향 그래프 | 간선에 방향이 없음 | A - B |
| 방향 그래프 | 간선에 방향이 있음 | A -> B |
b) 순환성 여부
| 구분 | 설명 | 예시 |
| 순환 그래프 | 다시 자기 자신으로 돌아올 수 있는 경로가 있음 | A --- B | | C --- D |
| 비순환 그래프(DAG) | 순환이 없음 -> 주로 위상정렬에서 사용됨 | A --- B --- C |
c) 가중치 여부
| 구분 | 설명 | 예시 |
| 가중치 그래프 | 간선에 비용이나 길이 등이 있음 | A -(3)- B : 가중치 3 |
| 비가중치 그래프 | 간선에 값이 없음(단순 연결만 의미) | A --- B |
이런 식으로 그래프를 분류할 수 있습니다.
그래프 표현 방법
그래프는 표현하는 방법이 따로 필요합니다.
노드들이 있고 각 노드를 간선이 이어주는 것, 그리고 더 나아가 가중치까지 기본 자료구조를 이용하여 나타내는 방법을 사용합니다.
1. 인접 행렬(Adjacency Matrix)
* 정점간 연결 여부를 2차원 배열로 표현
* 간선이 있으면 1, 없으면 0, 혹은 가중치가 있으면 해당 가중치 값으로 표현
예시: A-B, B-C, A-C 연결
1) 간선 유무만 표현
A B C
-----------
A | 0 1 1
B | 1 0 1
C | 1 1 0
2) 가중치 표현
* A-B 가중치 2, B-C 가중치 1, A-C 가중치 5 일 때
A B C
-----------
A | 0 2 5
B | 2 0 1
C | 5 1 0
위에서 든 예시를 코드로 나타내면 아래와 같이 나타낼 수 있습니다.
// 2차원 배열
int n = 3;
int[][] graph = new int[n][n];
// 가중치 없는 인접 행렬로 표현
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(i != j) { // A-A, B-B, C-C 연결 간선은 없음
graph[i][j] = 1;
}
}
}
2. 인접 리스트(Adjacency List)
* 각 정점에 연결된 이웃 정점들을 리스트로 저장
* 공간효율 ↑, 연결이 적은 경우 좋음
예시: A-B, B-C, A-C 연결
A: [B, C]
B: [A, C]
C: [A, B]
-> 이중 연결 리스트로 표현
A: index 0, B: index 1, C: index 2
[[B, C], [A, C], [A, B]]
이를 코드로 나타내면 다음과 같이 나타낼 수 있습니다.
// graph 생성(이중 연결 리슽)
List<List<Character>> graph = new ArrayList<>();
// 각 노드 별 연결 정보 세팅
List<Character> c1 = new ArrayList<>();
c1.add('B');
c1.add('C');
List<Character> c2 = new ArrayList<>();
c2.add('A');
c2.add('C');
List<Character> c3 = new ArrayList<>();
c2.add('A');
c2.add('B');
// graph에 각 인덱스 별 연결 정보 저장
graph.add(c1);
graph.add(c2);
graph.add(c3);
주요 용어 정리
그럼 이제 그래프에서 사용하는 주요 용어들을 표로 정리해보겠습니다.
| 용어 | 설명 |
| 정점(Vertex, 노드) | 그래프의 점 |
| 간선(Edge) | 두 정점을 연결하는 선 |
| 인접(Adjacent) | 간선으로 연결된 정점의 관계 정점 A와 B가 간선으로 연결되어 있으면 "인접" |
| 차수(Degree) | 정점에서 연결된 간선의 수 |
| 경로(Path) | 정점을 순서대로 연결한 길 |
| 사이클(Cycle) | 출발점으로 다시 돌아오는 경로 |
| 연결 그래프 | 모든 정점이 연결되어 있는 그래프 |
| 트리(Tree) | 사이클이 없는 연결 그래프 n개의 정점이 있는 트리는 n-1개의 간선을 가진다. |
탐색 알고리즘 및 그래프의 활용
이번에는 그래프 이론을 활용한 탐색 알고리즘을 정리해보겠습니다.
| 알고리즘 | 방식 | 용도 |
| DFS (깊이 우선 탐색) | 재귀 or 스택 | 경로 찾기, 사이클 탐지 |
| BFS (너비 우선 탐색) | 큐 | 최단 거리 탐색 |
| 다익스트라 | 우선순위 큐 | 가중치 있는 최단 경로 |
| 플로이드 워셜 | DP 방식 | 모든 쌍 간 최단거리 |
| 크루스칼 / 프림 | MST (최소 신장 트리) | 최소 비용 연결 구조 찾기 |
이렇게 대표적인 그래프 이론 활용 탐색 알고리즘이 있습니다.
더 나아가면 더욱 어려운 알고리즘들도 있지만, 우선 탐색 알고리즘을 정리하자면 위와 같은 종류들이 있습니다!
그래프는 현실 세계의 연결 관계나 네트워크 구조를 표현하기에 아주 유용하고, 따라서 다양한 실생활 및 문제 해결에 활용됩니다.
아래는 그러한 활용 예시를 정리해보았습니다.
| 분야 | 활용사례 |
| 지도 / 네비게이션 | 도로망, 최단 경로 찾기(다익스트라, A*) |
| 소셜 네트워크 | 친구 추천, 팔로워 구조 분석(연결, 클러스터) |
| 컴퓨터 네트워크 | 패킷 전송 경로, 라우팅 알고리즘 |
| 웹 크롤링 | 링크 구조 -> 웹 페이지들을 정점, 링크를 간선으로 표현 |
| 게임 개발 | 맵 이동, AI 경로 탐색 |
| 데이터 분석 | 유사도 분석, 추천 시스템 (그래프 기반 협업 필터링) |
| 컴파일러 / 빌드 시스템 | 작업 순위 결정 (위상정렬: DAG 기반) |
| 전기 회로 / 화학 분자 구조 | 노드-연결 구조 분석 |
| 퍼즐, 시뮬레이션 | 미로찾기, 물 흐름 시뮬레이션 등 |
그래프 이론은 이와 같이 다양한 상황에서 활용할 수 있습니다.
"현실세계의 개념을 표현하기 용이한 자료구조"이다 보니, 더욱 다양한 분야의 데이터 형태를 나타내기 좋습니다.
그래프 알고리즘의 장점과 단점
✅ 장점
1. 현실 문제 모델링에 적합
- 도로, 사람 관계, 네트워크 등 현실 세계의 문제를 그대로 반영이 가능합니다.
2. 다양한 알고리즘 존재
- 최단경로, 최소 신장 트리, 경로 탐색 등 강력한 알고리즘들이 존재합니다.
3. 연결성, 경로 등 복잡한 관계 표현 가능
- 노드 간 직접적이지 않은 간접 관계, 순환 여부 등도 쉽게 표현이 가능합니다.
4. 동적/복잡한 구조에도 유연함
- 배열이나 트리보다 훨씬 복잡한 관계를 모델링 할 수 있습니다.
❗️ 단점
1. 구현 복잡도
- 인접리스트/행렬 선택, 방향성/가중치에 따라 구현이 복잡할 수 있습니다.
2. 공간복잡도
- 연결 정보 저장 비용이 큽니다.
- 특히 인접 행렬로 나타낼 경우 O(n^2)만큼의 공간을 사용합니다.
3. 연산 성능
- 모든 정점/간선을 탐색해야 할 수 있습니다.
- 따라서 이로 인한 성능 이슈가 발생할 수 있습니다.
- 예) DFS, BFS -> O(V + E)
4. 추상화의 어려움
- 문제를 그래프로 모델링하는 능력이 부족하면 적용하기 어려울 수 있습니다.
이렇게 자료구조 이론 중 그래프 이론(Graph Theory)에 대해서 공부해보았습니다.
오늘 설명한 그래프 이론은 그래프를 활용한 알고리즘(DFS, BFS, 위상정렬 등) 공부를 위해 기초를 다지는 포스팅이었는데요,
난이도가 너무 높지 않은 기초 편이라 저도 금방 공부할 수 있었습니다 :)
코딩 테스트나 자료구조를 공부하시는 분들께 이번 편도 도움이 되셨길 바래요 !
포스팅 읽어주셔서 감사합니다 ! :)
