[Java] 그래프(Graph)란? (비선형 자료구조)

 

그래프(Graph)란 무엇일까? - 비선형 자료구조의 이해

지금까지 우리는 리스트나 배열처럼 데이터가 일렬로 늘어선 선형 구조에 대해 주로 다루었습니다. 이는 데이터와 데이터가 링크로 연결되어 한 줄로 표현될 수 있는 구조입니다. 하지만 만약 데이터 간의 연결이 복잡하게 얽혀 있어 한 줄로 표현할 수 없다면 어떻게 될까요? 이러한 구조를 비선형 구조라고 부르며, 대표적인 예가 바로 그래프입니다.

그래프의 기본 구성 요소

그래프는 복잡하게 얽힌 데이터 관계를 표현하는 비선형 자료구조입니다. 그래프는 두 가지 핵심 요소로 구성됩니다.

• 노드 (Node): 그래프에서 개별 데이터를 의미합니다. 정점(Vertex)이라고도 부릅니다.
• 에지 (Edge): 노드와 노드를 연결하는 링크(선)입니다. 간선이라고도 부릅니다.

에지는 단순히 연결을 나타낼 수도 있지만, 추가적인 정보를 가질 수도 있습니다. 예를 들어, 한쪽으로만 이동할 수 있는 방향성을 갖거나, 이동에 드는 비용이나 거리를 나타내는 가중치(Weight)를 가질 수도 있습니다.

이러한 그래프 구조는 지하철 노선도처럼 여러 노선이 교차하고 순환하는 복잡한 관계를 데이터로 표현하는 데 매우 유용합니다. 하나의 노선만 본다면 리스트로 표현할 수 있겠지만, 전체 노선도를 한 번에 표현하려면 비선형 구조인 그래프가 필수적입니다.

---

그래프 탐색하기: BFS와 DFS

데이터를 그래프 구조로 표현했다면, 다음 과제는 이 구조 안에서 원하는 데이터를 찾는 것입니다. 선형 구조처럼 처음부터 끝까지 순서대로 확인할 수 없기 때문에, 그래프에는 특별한 탐색 알고리즘이 필요합니다.

그래프 탐색의 기본 원리는 간단합니다.

1. 하나의 노드를 확인합니다.
2. 해당 노드와 연결된, 다음에 확인할 노드들을 예약합니다.
3. 예약된 목록에서 다음 노드를 꺼내 확인하고, 이 과정을 반복합니다.

이때 '예약 목록'을 어떤 자료구조로 관리하느냐에 따라 탐색 방식이 두 가지로 나뉩니다.

 

너비 우선 탐색 (Breadth-First Search, BFS)

BFS는 예약 목록으로 큐(Queue)를 사용하는 방식입니다. 큐는 먼저 들어온 데이터가 먼저 나가는(FIFO) 구조이므로, 탐색은 시작 노드에 가까운 노드들부터 넓게 펴져 나가며 진행됩니다.

예를 들어, 아래 그래프에서 'A'부터 'E'를 찾는다고 가정해 보겠습니다.

1. 'A'를 확인하고, 연결된 'B'와 'D'를 큐에 예약합니다. (Queue: [B, D])
2. 큐에서 'B'를 꺼내 확인하고, 'B'와 연결된 'C'와 'E'를 큐에 예약합니다. (Queue: [D, C, E])
3. 큐에서 'D'를 꺼내 확인합니다. 'D'에 연결된 'C'와 'E'는 이미 예약 목록에 있으므로 중복 추가하지 않습니다. (Queue: [C, E])
4. 큐에서 'C'를 꺼내 확인합니다.
5. 마지막으로 큐에서 'E'를 꺼내 확인하여, 목표 데이터를 찾습니다.

이때 탐색 순서는 A → B → D → C → E가 됩니다. 이처럼 너비를 먼저 탐색한다고 해서 너비 우선 탐색이라고 부릅니다.

 

깊이 우선 탐색 (Depth-First Search, DFS)

DFS는 예약 목록으로 스택(Stack)을 사용하는 방식입니다. 스택은 가장 나중에 들어온 데이터가 먼저 나가는(LIFO) 구조이므로, 탐색은 하나의 경로를 따라 최대한 깊게 들어갔다가 막히면 되돌아 나오는 방식으로 진행됩니다.

동일한 그래프에서 'A'부터 'E'를 찾는다고 가정해 보겠습니다.

1. 'A'를 확인하고, 연결된 'B'와 'D'를 스택에 예약합니다. (Stack: [B, D])
2. 스택에서 가장 위에 있는 'D'를 꺼내 확인하고, 'D'와 연결된 'C'와 'E'를 스택에 예약합니다. (Stack: [B, C, E])
3. 스택에서 가장 위에 있는 'E'를 꺼내 확인하여, 목표 데이터를 바로 찾습니다.

이때 탐색 순서는 A → D → E가 됩니다. 한 경로를 깊게 파고드는 형태이므로 깊이 우선 탐색이라고 부릅니다.

특징	너비 우선 탐색 (BFS)	깊이 우선 탐색 (DFS)
예약 자료구조	큐 (Queue)	스택 (Stack)
탐색 형태	시작 노드 주변부터 넓게 탐색	하나의 경로를 최대한 깊게 탐색
경로 특징	최단 경로를 찾는 데 유리	모든 경로를 탐색해야 할 때 유리

---

결론

BFS와 DFS는 예약 목록을 관리하는 자료구조만 다를 뿐, 그래프의 모든 노드를 방문한다는 점에서는 동일한 목적을 가진 알고리즘입니다. 어떤 방식이 더 우월하다고 말할 수는 없으며, 그래프의 형태나 찾고자 하는 데이터의 위치에 따라 효율성이 달라집니다. 만약 찾는 데이터가 시작 지점과 가깝다면 BFS가, 멀리 떨어져 있다면 DFS가 더 빠를 수 있습니다.

이제 그래프의 기본 개념과 두 가지 대표적인 탐색 방법에 대해 알아보았으니, 다음 단계는 이를 자바 코드로 직접 구현해보며 비선형 자료구조를 더욱 깊이 이해하는 것입니다.