그래프(Graph)는 자료구조론에서 가장 중요하면서도 활용 범위가 넓은 구조 중 하나다. 정점(Vertex)과 간선(Edge)을 통해 객체 간의 관계를 표현할 수 있기 때문에 네트워크, 지도, SNS, 추천 시스템, 알고리즘 문제 등 다양한 분야에서 핵심적으로 사용된다. 특히 트리보다 자유로운 구조를 가지기 때문에 현실 세계의 복잡한 관계를 모델링하는 데 매우 적합하다. 이 글에서는 자료구조를 처음 접하는 초보자를 위해 그래프의 기본 개념부터 구조, 표현 방식, 활용 예시까지 2026년 기준 학습 흐름에 맞춰 체계적으로 정리한다.
그래프(Graph)의 기본 개념과 구성 요소
그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조다. 정점은 개체나 데이터를 의미하고, 간선은 두 정점 사이의 관계를 나타낸다. 이때 그래프의 핵심은 값 자체보다도 “연결 관계”에 있다. 예를 들어 사람을 정점으로, 친구 관계를 간선으로 표현하면 SNS 구조를 그래프로 나타낼 수 있다. 마찬가지로 도시를 정점으로, 도로를 간선으로 표현하면 지도와 교통망을 모델링할 수 있다.
그래프에는 여러 가지 유형이 존재한다. 먼저 무방향 그래프는 간선에 방향이 없어 양쪽 이동이 가능한 구조다. 친구 관계나 도로처럼 상호 연결된 경우에 적합하다. 반면 유향 그래프는 간선에 방향이 있어 한쪽 방향으로만 이동할 수 있다. 이는 웹 페이지 링크 구조, 작업 의존 관계, 명령 흐름 등을 표현할 때 사용된다. 여기에 간선마다 비용이나 거리 같은 값을 부여하면 가중치 그래프가 된다. 가중치 그래프는 최단 경로 문제나 네트워크 비용 계산에서 필수적인 개념이다.
초보자들이 그래프를 어려워하는 이유 중 하나는 트리와의 차이 때문이다. 트리는 항상 루트가 존재하고 사이클이 없지만, 그래프는 시작점이 명확하지 않을 수 있고 사이클이 자유롭게 존재할 수 있다. 이러한 차이를 이해하면 그래프의 유연한 구조가 왜 필요한지 자연스럽게 받아들일 수 있다.
그래프 표현 방식과 자료구조적 특징
그래프를 실제 프로그램에서 다루기 위해서는 메모리 상에서 표현하는 방식이 필요하다. 가장 대표적인 방법은 인접 행렬과 인접 리스트다. 인접 행렬은 정점 개수만큼의 2차원 배열을 생성해, 두 정점이 연결되어 있으면 1 또는 가중치를 저장하는 방식이다. 이 방식은 두 정점의 연결 여부를 즉시 확인할 수 있다는 장점이 있지만, 정점 수가 많아질수록 메모리 사용량이 급격히 증가한다.
반면 인접 리스트는 각 정점마다 연결된 정점들의 목록을 저장하는 방식이다. 실제로 연결된 간선 정보만 저장하기 때문에 메모리 효율이 뛰어나며, 대부분의 알고리즘 문제와 실무 환경에서 선호된다. 특히 정점 수는 많지만 간선 수가 상대적으로 적은 그래프에서는 인접 리스트 방식이 매우 효과적이다.
그래프의 또 다른 중요한 특징은 방문 처리의 필요성이다. 그래프에는 사이클이 존재할 수 있기 때문에 탐색 과정에서 이미 방문한 정점을 다시 방문하지 않도록 체크해야 한다. 이 과정을 소홀히 하면 무한 루프에 빠지거나 스택 오버플로우가 발생할 수 있다. 따라서 그래프를 다룰 때는 항상 방문 배열이나 집합을 통해 방문 여부를 관리해야 한다는 점을 명확히 인식해야 한다.
그래프의 활용과 초보자가 알아야 할 핵심 포인트
그래프는 알고리즘 분야에서 매우 다양한 문제를 해결하는 데 사용된다. 가장 대표적인 예가 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)이다. 이 두 탐색 알고리즘은 그래프의 모든 정점을 방문하는 기본적인 방법으로, 최단 거리 탐색, 연결 요소 분석, 경로 존재 여부 판단 등에 활용된다.
실생활 예시를 살펴보면 그래프의 중요성은 더욱 명확해진다. 지도 앱에서 목적지까지의 최단 경로를 찾는 기능은 가중치 그래프와 최단 경로 알고리즘을 기반으로 동작한다. SNS에서 친구 추천이나 관계 분석 역시 그래프 탐색과 연결성 분석을 통해 구현된다. 또한 프로젝트 관리 도구에서는 작업 간의 선후 관계를 유향 그래프로 표현해 일정 충돌을 방지한다.
초보자가 그래프를 공부할 때 가장 중요한 포인트는 “문제를 그래프로 표현하는 사고”를 기르는 것이다. 단순히 BFS, DFS를 외우는 것보다, 주어진 문제 상황에서 정점과 간선이 무엇인지 정의하는 연습이 훨씬 중요하다. 이 과정이 익숙해지면 그래프 문제는 패턴화되어 보이기 시작하고, 복잡해 보이던 문제도 구조적으로 접근할 수 있게 된다.
그래프는 정점과 간선이라는 단순한 구성 요소를 통해 복잡한 관계를 표현할 수 있는 매우 강력한 자료구조다. 기본 개념, 그래프 유형, 표현 방식, 활용 사례를 차근차근 이해하면 알고리즘 문제 해결 능력뿐만 아니라 실무적인 문제 해결 능력까지 함께 향상된다. 초보자일수록 다양한 예제를 그래프로 모델링해보는 연습을 통해 그래프 사고방식을 자연스럽게 익히는 것이 중요하다.