[자료구조] 트리(Tree) vs 그래프(Graph) 차이 및 DFS/BFS 탐색 알고리즘 완전 정리

컴퓨터공학과 자료구조/알고리즘 전공 시험이나 코딩 테스트 문제에서 "비선형 자료구조(Non-linear Data Structure)의 대표격인 두 구조"를 다룰 때 빠지지 않는 주제가 있습니다. 바로 트리와 그래프의 구조적 차이와 DFS / BFS 탐색 방식입니다.

"트리와 그래프는 정확히 어떤 차이가 있을까?"

"스택과 큐를 각각 사용하는 DFS와 BFS는 어떤 상황에서 선택해야 할까?"

두 자료구조의 개념 비교부터 핵심 탐색 알고리즘의 동작 방식, 구현 자료구조, 그리고 시험 단골 문제 유형까지 깔끔하게 정리해 드립니다!

1. 트리(Tree) vs 그래프(Graph) 구조적 차이

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조의 총칭이며, 트리는 그래프의 특정한 형태(사이클이 없는 연결 그래프)에 해당합니다. 즉, "모든 트리는 그래프이지만, 모든 그래프가 트리는 아니다"라는 명제가 성립합니다.

루트 노드로부터 계층 구조를 이루는 트리 및 비선형 자료구조 탐색 방식. 출처: Tribune Media Services

🔹 주요 구조적 차이점 비교 (★시험 요약표)

구분	트리 (Tree)	그래프 (Graph)
구조 방식	계층적 구조 (Hierarchical)	망형 구조 (Network)
방향성	방향 그래프 (부모 $\rightarrow$ 자식)	방향(Directed) 또는 무방향(Undirected)
사이클 (Cycle)	사이클 존재 불가 (Acyclic)	사이클 존재 가능 (Cyclic / Acyclic)
루트 노드	단 1개의 루트 노드(Root Node) 존재	루트 노드의 개념이 없음
부모-자식 관계	부모-자식 관계가 명확함	부모-자식 개념 없음 (선으로 연결된 노드 관계)
간선(Edge) 수	$N$개 노드일 때 항상 $N-1$개	간선 수가 다양함 (0개 이상)

2. 그래프/트리 탐색 알고리즘: DFS vs BFS

비선형 자료구조의 모든 노드를 한 번씩 방문하는 과정을 순회(Traversal) 또는 탐색(Search)이라고 합니다. 대표적인 두 가지 방식이 DFS(Depth-First Search)와 BFS(Breadth-First Search)입니다.

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

• 개념: 그래프의 한 갈래를 선택해 최대한 깊게(자식 노드 방향으로) 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 갈림길로 돌아와(Backtracking) 다른 갈래를 탐색하는 방식입니다.
• 사용 자료구조: 스택(Stack) 또는 재귀 호출(Recursion).
• 장점:
  • 현재 탐색 경로상의 노드들만 기억하면 되므로 메모리 공간(공간 복잡도)을 비교적 적게 차지합니다.
  • 목표 노드가 깊은 단계에 있을 때 빠르게 도달할 수 있습니다.
• 단점:
  • 해가 없는 깊은 경로에 빠질 경우 무한 루프에 위험이 있으며, 최단 경로를 보장하지 않습니다.

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

• 개념: 루트(또는 시작 노드)에서 시작하여 인접한 노드(같은 깊이/레벨의 노드)들을 먼저 모두 방문한 뒤, 다음 레벨로 넘어가는 방식입니다.
• 사용 자료구조: 큐(Queue).
• 장점:
  • 가중치가 없는 그래프에서 최단 경로(Minimum Edge Count) 또는 최소 간선 이동 횟수를 보장합니다.
• 단점:
  • 다음 레벨의 노드들을 큐에 모두 저장해야 하므로, 노드 수가 많을수록 메모리(공간 복잡도) 소모가 큽니다.

3. 한눈에 비교하는 DFS vs BFS (★시험 필수)

구분	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방향	세로 방향으로 깊게 탐색	가로 방향으로 넓게 탐색
주요 자료구조	스택(Stack), 재귀함수	큐(Queue)
최단 경로 보장	보장되지 않음	보장됨 (가중치 없는 그래프 기준)
시간 복잡도	인접 리스트: $O(V + E)$ / 인접 행렬: $O(V^2)$	인접 리스트: $O(V + E)$ / 인접 행렬: $O(V^2)$
주요 활용 문제	• 미로 찾기 (경로 유무 탐색) • 사이클 존재 여부 검사 • 백트래킹(N-Queen 등)	• 최단 거리 / 최소 비용 구하기 • 미로 최단 경로 탐색 • 최단 연결망 구축

💡 시험 단골 포인트: Visited 배열의 필요성

트리는 사이클이 없어서 순회 시 재방문 우려가 적지만, 일반 그래프에서는 DFS/BFS 탐색 시 무한 루프를 방지하기 위해 반드시 방문 여부를 기록하는 visited 배열이 필요합니다.

4. 시험 단골 출제 유형 체크

1. Q. $N$개의 노드를 가지는 트리가 갖는 간선(Edge)의 개수는 몇 개인가?
2. 👉 $N-1$개 입니다.
3. Q. 가중치가 동일한 미로 찾기 문제에서 시작점에서 도착점까지의 '최단 경로'를 찾을 때 적합한 알고리즘과 사용 자료구조는?
4. 👉 BFS(너비 우선 탐색) 알고리즘이며, 큐(Queue) 자료구조를 사용합니다.
5. Q. 그래프 탐색 시 DFS는 (A) 자료구조를 활용하고, BFS는 (B) 자료구조를 활용한다. 빈칸은?
6. 👉 (A) 스택(Stack) (또는 재귀), (B) 큐(Queue) 입니다.