기술사 학습노트 | imt-log

기술사 학습노트› 알고리즘› 그래프 자료구조

Algorithm · 한장정리

[기술사토픽] 그래프(Graph) 자료구조 완벽 정리 - 한장정리

그래프 개요, 종류(방향·무방향·가중), 인접행렬·인접리스트 표현방식을 체계적으로 정리한 기술사 핵심 학습노트

그래프Graph정점간선방향그래프무방향그래프인접행렬인접리스트정보관리기술사알고리즘

Ⅰ.그래프 개요

그래프(Graph)는 정점(Vertex, V)과 간선(Edge, E)으로 구성된 비선형 자료구조로, G = (V, E)로 표기한다. 트리는 그래프의 특수한 형태(사이클 없는 연결 그래프)이며, 네트워크·경로·관계 모델링에 핵심적으로 활용된다.

용어	설명
정점(Vertex)	그래프의 노드, 데이터 객체를 표현
간선(Edge)	정점 간의 연결 관계
차수(Degree)	한 정점에 연결된 간선의 수
경로(Path)	정점들의 순서 있는 나열 (간선으로 연결)
사이클(Cycle)	시작과 끝이 같은 경로
연결 그래프	모든 정점 쌍 사이에 경로가 존재

Ⅱ.그래프 종류

종류	특징	간선 표현	적용 예시
무방향 그래프	간선에 방향 없음, 양방향 이동 가능	(u, v) = (v, u)	도로망, 친구 관계
방향 그래프(Digraph)	간선에 방향 있음, 단방향 이동	<u, v> ≠ <v, u>	웹 링크, 작업 의존성
가중 그래프	간선에 가중치(비용) 부여	(u, v, w)	최단 경로, MST
완전 그래프	모든 정점 쌍이 간선으로 연결	간선 수: n(n-1)/2	최대 연결 네트워크
이분 그래프	정점을 두 집합으로 분리, 동일 집합 내 간선 없음	두 집합 간 간선만 존재	매칭 문제, 이분 탐색
DAG	방향 그래프 + 사이클 없음	방향 간선, 비순환	위상 정렬, 작업 스케줄링

시험 포인트

무방향 완전 그래프의 간선 수: n(n-1)/2. 방향 완전 그래프: n(n-1). 트리는 정점이 n개일 때 간선이 n-1개인 비순환 연결 그래프이다.

Ⅲ.그래프 표현 방식

그래프를 컴퓨터에서 표현하는 두 가지 주요 방법이 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)이다.

구분	인접 행렬	인접 리스트
구조	n×n 2차원 배열 (A[i][j]=1 이면 간선 존재)	각 정점마다 연결 리스트
공간 복잡도	O(V²) — 희소 그래프에 비효율	O(V+E) — 희소 그래프에 효율적
간선 존재 확인	O(1)	O(degree(v))
인접 정점 순회	O(V)	O(degree(v))
적합한 그래프	밀집 그래프 (E ≈ V²)	희소 그래프 (E ≪ V²)
가중 그래프	A[i][j] = 가중치 값	리스트 노드에 가중치 포함

선택 기준: 정점 수(V)가 적고 간선이 많으면 인접 행렬, 정점 수가 많고 간선이 적은 희소 그래프(Sparse Graph)에는 인접 리스트가 공간·시간 측면에서 유리하다.

Ⅳ.결론

Conclusion

그래프는 네트워크, 경로, 관계를 모델링하는 범용 자료구조로, DFS·BFS 탐색, 최단 경로(다익스트라·벨만포드), 최소 신장 트리(크루스칼·프림), 위상 정렬 등 핵심 알고리즘의 기반이 된다. 그래프 표현 방식은 밀집도에 따라 인접 행렬(밀집)·인접 리스트(희소)를 선택하며, 문제의 특성에 따라 방향·무방향·가중 그래프를 구분하여 적용해야 한다.

블로그: 기술사 학습노트 · imt-log.tistory.com

← 알고리즘 목록