그래프(Graph)란 무엇인가?
그래프는 유한한 개수의 노드(정점)와 이 노드들의 쌍을 연결하는 간선의 집합으로 구성되는 대표적인 비선형 자료구조입니다. 트리나 배열과 달리 데이터가 계층적 또는 순차적으로 배치되지 않고, 임의의 형태로 서로 연결될 수 있다는 점이 특징입니다.
그래프는 실생활의 다양한 문제를 모델링하고 해결하는 데 폭넓게 활용됩니다. 예를 들어 소셜 네트워크에서 사람들 간의 친구 관계, 지도 애플리케이션에서 도시 간 도로 연결, 통신망에서 라우터 간의 연결 상태 등을 표현할 때 그래프가 사용됩니다.
이 섹션에서 다루는 주요 그래프 알고리즘
아래에서는 그래프 이론의 핵심 주제들을 카테고리별로 정리하여 소개합니다.
1. 기본 탐색 알고리즘
- 그래프의 너비 우선 탐색(BFS, Breadth First Search)
- 그래프의 깊이 우선 탐색(DFS, Depth First Search)
2. 사이클 및 연결성 분석
- 무방향 그래프에서 사이클 감지
- 방향 그래프에서 사이클 감지
- 방향 그래프의 연결성 확인
- 강연결 그래프(Strongly Connected Graph) 판별
- 타잔(Tarjan) 알고리즘을 이용한 강연결 요소(SCC) 찾기
- 이중 연결 그래프(Bi-Connected Graph) 검사
- 그래프의 브리지(Bridge, 다리) 찾기
- 주어진 그래프가 트리인지 판별하기
- 스타 그래프(Star Graph) 여부 검사
3. 경로 및 거리 계산
- 유향 비순환 그래프(DAG)에서의 최단 경로
- 유향 비순환 그래프(DAG)에서의 최장 경로
- 정확히 k개의 간선을 거치는 최단 경로
- 벨만-포드(Bellman–Ford) 알고리즘을 이용한 최단 경로 탐색
4. 오일러 경로와 회로
- 오일러 경로(Eulerian Path)와 오일러 회로(Eulerian Circuit)
- 방향 그래프에서의 오일러 회로
- 플뢰리(Fleury) 알고리즘
5. 매칭, 색칠 및 기타 응용
- 그래프가 이분 그래프(Bipartite Graph)인지 확인하는 방법
- 최대 이분 매칭(Maximum Bipartite Matching)
- 그래프 색칠(Graph Coloring)
- 위상 정렬(Topological Sorting)
- 그래프의 추이적 폐쇄(Transitive Closure)
- 포드-풀커슨(Ford-Fulkerson) 알고리즘
- 뱀과 사다리 게임 문제(Snake and Ladder Problem)
위 알고리즘들은 코딩 테스트, 기술 면접, 실무 시스템 설계에서 자주 등장하는 핵심 주제들입니다. 각 알고리즘의 동작 원리와 구현 방법을 순서대로 학습하면 그래프 이론 전반에 대한 이해를 깊이 있게 쌓을 수 있습니다.