그래프

그래프(graph)는 정점(vertex)들과 정점 사이를 잇는 간선(edge)으로 이뤄진 자료구조(data structure)다. 지도의 도시와 도로, SNS의 사람과 친구 관계, 작업과 선후 관계처럼 "무엇과 무엇이 이어져 있다"는 데이터를 담는다.

그래프의 종류

• 무방향 그래프(undirected graph): 간선에 방향이 없어 A–B가 이어지면 양쪽으로 오갈 수 있다.
• 방향 그래프(directed graph): 간선에 방향이 있어 A→B로만 갈 수 있다. 팔로우 관계가 그렇다.
• 가중치 그래프(weighted graph): 간선마다 거리·시간·비용 같은 숫자(가중치)가 붙는다.

한 정점에 붙은 간선 수를 차수(degree)라 한다. 출발한 정점으로 다시 돌아오는 경로를 사이클(cycle)이라 한다. 트리(tree)는 사이클이 없고 모든 정점이 이어진 그래프의 특수한 경우다.

저장 방법: 인접 행렬과 인접 리스트

정점이 V개, 간선이 E개인 그래프를 저장하는 방법은 두 가지다. 아래 무방향 그래프로 비교한다.

다이어그램 로딩…

인접 행렬(adjacency matrix)은 V × V 크기의 2차원 배열(array)로, i번과 j번 정점이 이어져 있으면 [i][j] 칸에 1(또는 가중치)을 적는다. 인접 리스트(adjacency list)는 정점마다 이웃 정점 목록을 들고 있어 실제 간선만 저장한다.

인접 행렬	A	B	C	D	E
A	0	1	1	0	0
B	1	0	0	1	0
C	1	0	0	1	0
D	0	1	1	0	1
E	0	0	0	1	0

인접 리스트는 A: B, C / B: A, D / C: A, D / D: B, C, E / E: D 다. 행렬은 25칸을 다 쓰지만 리스트는 실제 간선 5개를 양쪽에 한 번씩, 10칸만 쓴다.

아래 표의 O(…)는 빅오 표기법(Big-O notation)이다. 간선이 V²에 가까울 만큼 많으면 밀집 그래프(dense graph), 훨씬 적으면 희소 그래프(sparse graph)라 한다.

기준	인접 행렬	인접 리스트
공간	O(V²)	O(V + E)
두 정점이 이어졌나	O(1)	O(그 정점의 차수)
한 정점의 이웃 모두 보기	O(V)	O(그 정점의 차수)
알맞은 그래프	간선이 많은 밀집 그래프	간선이 적은 희소 그래프

도로망·친구 관계 같은 실제 그래프는 대부분 희소 그래프라서 인접 리스트를 많이 쓴다.

BFS: 가까운 곳부터

BFS(Breadth-First Search, 너비 우선 탐색)는 시작 정점에서 가까운 정점부터 한 겹씩 넓혀 가며 방문한다. 방금 발견한 정점을 큐(queue)의 뒤에 넣고 앞에서 꺼내 방문하므로, 먼저 발견된 가까운 정점이 먼저 처리된다. 같은 정점을 두 번 넣지 않도록 방문 표시를 해 두는데, 이것이 없으면 사이클을 따라 같은 곳을 끝없이 돈다. BFS는 간선 수가 적은 순서로 정점에 닿으므로, 가중치가 없는 그래프에서는 BFS로 처음 닿은 거리가 곧 최단 거리(거치는 간선 수)다. 인접 리스트라면 모든 정점과 간선을 한 번씩 보므로 O(V + E)다.

int[] dist = new int[V]; Arrays.fill(dist, -1);   // -1 = 아직 방문 안 함
Deque<Integer> q = new ArrayDeque<>();
dist[s] = 0; q.offer(s);
while (!q.isEmpty()) {
    int u = q.poll();
    for (int v : adj.get(u))
        if (dist[v] == -1) { dist[v] = dist[u] + 1; q.offer(v); }
}

DFS: 끝까지 들어갔다 되돌아오기

DFS(Depth-First Search, 깊이 우선 탐색)는 한 방향으로 갈 수 있는 데까지 깊이 들어갔다가, 막히면 직전 갈림길로 되돌아와 다른 길을 간다. "가장 최근 갈림길로 돌아가기"는 나중에 넣은 것을 먼저 꺼내는 LIFO(Last In First Out, 후입선출)이므로 스택(stack)을 쓰거나, 함수 호출이 스택 역할을 하는 재귀(recursion)로 짧게 쓴다. 방문 표시가 필요한 것은 BFS와 같고, 복잡도도 인접 리스트 기준 O(V + E)다.

DFS는 처음 닿은 경로가 먼 길일 수 있어 최단 거리를 보장하지 않는다. 대신 경로가 있는지, 그래프가 몇 덩어리로 나뉘는지, 사이클이 있는지 확인하는 데 잘 맞고, 그래프 2에서 다룰 위상 정렬(topological sort)에도 쓰인다. 재귀로 짜면 깊이만큼 호출 스택(call stack)이 쌓여, 그래프가 깊으면 스택 오버플로(stack overflow)로 프로그램이 죽을 수 있다.

앞의 예를 A에서 출발해 돌면(이웃은 알파벳 순) 방문 순서가 이렇게 갈린다.

탐색	방문 순서	모양
BFS	A → B → C → D → E	A에서 한 칸(B·C), 두 칸(D), 세 칸(E) 순서로 넓어진다
DFS	A → B → D → C → E	B에서 D까지 깊이 들어간 뒤, D의 다른 이웃 C와 E로 간다

이어지는 내용은 그래프 2에서 다룬다.

면접 포인트

• "인접 행렬 vs 인접 리스트" → 공간 O(V²) vs O(V+E), 간선 확인 O(1) vs O(차수). 희소 그래프면 리스트.
• "BFS와 DFS의 차이는?" → 큐·가까운 곳부터·무가중치 최단 거리 vs 스택(재귀)·끝까지 들어갔다 복귀. 둘 다 O(V+E), 방문 표시 필수.
• "방문 표시를 빼면?" → 사이클이 있는 그래프에서 같은 곳을 끝없이 돈다.