방송대 방통대 자료구조 15강 - 그래프 탐색과 최소 비용 신장 트리 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 15강 - 그래프 탐색과 최소 비용 신장 트리

그래프의 정점을 빠짐없이 방문하는 깊이 우선 탐색과 너비 우선 탐색의 원리 및 구현 자료구조를 익힌다. 이어서 신장 트리와 최소 비용 신장 트리의 조건을 이해하고 Prim·Kruskal·Sollin 알고리즘의 간선 선택 방식과 차이를 정리한다.

그래프 탐색의 개념

시작 정점에서 정점을 찾아가는 연산

그래프 G = (V, E)에서 그래프 탐색은 시작 정점에서 출발하여 특정 목표 정점에 도달하거나, 목표가 없다면 도달 가능한 모든 정점을 방문하는 연산이다. 트리와 달리 그래프에는 루트가 정해져 있지 않으므로 탐색을 시작할 정점을 명시해야 한다.

그래프는 사이클을 가질 수 있고 하나의 정점으로 가는 경로가 여러 개일 수 있다. 따라서 이미 방문한 정점을 다시 처리하지 않도록 visited 배열 또는 방문 표시가 반드시 필요하다. 연결 그래프라면 한 시작 정점에서 모든 정점에 도달하지만, 비연결 그래프라면 한 번의 탐색으로는 시작 정점이 속한 연결 요소만 방문한다.

탐색 방법	핵심 전략	주요 자료구조
깊이 우선 탐색	한 경로를 가능한 깊이 진행한 뒤 되돌아감	스택 또는 재귀 호출
너비 우선 탐색	현재 정점과 가까운 정점부터 레벨 순서로 방문	큐

공통 원칙: 시작 정점을 방문 표시하고, 인접하면서 아직 방문하지 않은 정점을 선택한다. 방문 표시가 없으면 사이클 때문에 같은 정점을 반복 방문할 수 있다.

깊이 우선 탐색

갈 수 있는 데까지 내려가기

깊이 우선 탐색(Depth First Search, DFS)은 시작 정점을 방문한 뒤 그 정점에 인접한 미방문 정점 하나를 선택하여 탐색을 이어 간다. 새 정점에서도 같은 작업을 반복해 한 경로를 깊게 진행한다. 더 이상 갈 미방문 인접 정점이 없으면 가장 최근 분기점으로 되돌아가 다른 경로를 탐색한다.

되돌아갈 위치를 관리하는 방식이 후입선출이므로 DFS는 스택을 사용한다. 재귀 함수로 구현하면 함수 호출 스택이 이 역할을 자동으로 수행한다. 명시적 스택을 사용할 수도 있으며, 이때 현재 정점의 미방문 인접 정점들을 스택에 넣고 가장 최근에 넣은 정점을 꺼내 탐색한다.

단계	DFS 동작
1	시작 정점을 방문하고 visited를 표시
2	현재 정점에 인접한 미방문 정점 하나를 선택
3	선택한 정점을 새 현재 정점으로 삼아 깊이 진행
4	막다른 곳이면 스택을 이용해 최근 분기점으로 복귀
5	더 이상 방문할 정점이 없으면 종료

인접 정점이 여러 개일 때 어느 정점을 먼저 선택하는지에 따라 방문 순서는 달라질 수 있다. 인접 리스트의 저장 순서나 인접 행렬의 열 검사 순서가 결과에 영향을 준다. 그러나 어떤 순서를 사용하더라도 방문 표시를 올바르게 한다면 도달 가능한 정점을 한 번씩 방문한다.

너비 우선 탐색

가까운 정점을 먼저 방문하기

너비 우선 탐색(Breadth First Search, BFS)은 시작 정점을 방문한 뒤 그 정점의 미방문 인접 정점을 모두 차례로 방문한다. 다음에는 먼저 발견된 정점의 미방문 인접 정점들을 처리한다. 같은 거리의 정점들을 먼저 방문하므로 탐색이 동심원처럼 바깥쪽으로 넓어진다.

발견된 순서대로 정점을 처리해야 하므로 BFS는 큐를 사용한다. 시작 정점을 큐에 넣고 방문 표시한다. 큐의 front에서 정점을 꺼내 인접 정점을 검사하며, 아직 방문하지 않은 정점은 발견 즉시 방문 표시한 뒤 rear에 넣는다. 큐가 빌 때까지 이 과정을 반복한다.

방문 표시는 큐에서 꺼낼 때가 아니라 큐에 넣는 순간 하는 것이 안전하다. 그래야 여러 정점이 같은 이웃을 발견하더라도 그 정점이 큐에 중복 삽입되지 않는다.

간선 가중치를 고려하지 않는 그래프에서 BFS가 만든 탐색 트리는 시작 정점으로부터 간선 수가 가장 적은 경로를 보여 준다. DFS와 마찬가지로 인접 정점의 검사 순서에 따라 같은 레벨 내부의 방문 순서는 달라질 수 있다.

DFS와 BFS 비교

구분	DFS	BFS
진행 방향	한 경로를 깊게 진행	가까운 정점부터 넓게 진행
자료구조	스택·재귀 호출	큐
막힌 경우	최근 분기점으로 되돌아감	큐의 다음 정점을 처리
대표 활용	경로 탐색, 사이클·연결성 검사, 백트래킹	비가중 최단 경로, 레벨별 탐색
공통점	visited 표시로 중복 방문을 막고 시작점에서 도달 가능한 정점을 탐색

DFS와 BFS의 방문 순서는 그래프 표현과 인접 정점 선택 규칙에 따라 달라질 수 있다. 시험에서 방문 순서를 계산할 때는 정점 번호가 작은 순서, 인접 리스트에 적힌 순서 등 문제에서 제시한 선택 기준을 먼저 확인해야 한다.

빠른 구분: DFS는 “마지막에 발견한 정점을 먼저” 처리하므로 스택, BFS는 “먼저 발견한 정점을 먼저” 처리하므로 큐를 사용한다.

신장 트리와 최소 비용 신장 트리

사이클 없이 모든 정점을 연결하기

트리는 사이클이 없는 단순 연결 그래프이다. 루트를 지정하면 계층 구조로 볼 수 있지만, 일반 그래프의 부분 그래프로서 트리를 말할 때는 특정 루트를 요구하지 않는다. 트리에서는 임의의 두 정점 사이에 단순 경로가 하나만 존재한다.

연결 그래프 G의 신장 트리(spanning tree)는 G의 모든 정점을 포함하고 원래 간선의 일부만 선택해 만든 트리이다. 정점이 n개인 신장 트리는 항상 n-1개의 간선을 갖는다. DFS와 BFS에서 정점을 처음 발견할 때 사용한 간선만 모아도 각각 깊이 우선 신장 트리와 너비 우선 신장 트리를 만들 수 있다.

가중치 그래프에서는 신장 트리에 포함된 간선 비용의 합을 계산할 수 있다. 가능한 신장 트리 가운데 합계가 가장 작은 것을 최소 비용 신장 트리(Minimum Cost Spanning Tree, MST)라고 한다. MST는 모든 정점을 최소 총비용으로 연결하되 사이클을 포함하지 않는다.

개념	조건
트리	연결되어 있고 사이클이 없는 그래프
신장 트리	원 그래프의 모든 정점과 n-1개 간선을 포함하는 부분 트리
최소 비용 신장 트리	신장 트리 중 선택 간선 가중치 합이 최소인 것

Prim 알고리즘

하나의 트리를 바깥으로 확장하기

Prim 알고리즘은 임의의 시작 정점에서 하나의 트리 T를 만들고, 매 단계 T 안의 정점과 T 밖의 정점을 연결하는 간선 중 비용이 가장 작은 것을 선택해 T에 추가한다. 이미 T에 포함된 두 정점을 잇는 간선은 사이클을 만들므로 선택하지 않는다.

단계	Prim의 처리
초기화	임의의 시작 정점을 정점 집합 W에 포함
후보 선택	W와 V-W를 연결하는 간선 중 최소 비용 간선을 찾음
확장	선택 간선과 바깥쪽 정점을 T와 W에 추가
종료	모든 정점이 W에 포함되거나 n-1개 간선이 선택되면 종료

Prim은 과정 내내 하나의 연결된 트리를 유지한다. 선택할 수 있는 최소 비용 간선이 여러 개면 어느 것을 고르느냐에 따라 만들어지는 MST의 모양은 달라질 수 있지만 총비용은 같을 수 있다.

Kruskal 알고리즘

전체 간선을 비용 순서로 검사하기

Kruskal 알고리즘은 그래프의 모든 간선을 비용이 작은 순서로 정렬한 뒤 하나씩 검사한다. 현재 선택된 간선 집합에 추가해도 사이클이 생기지 않으면 선택하고, 사이클이 생기면 버린다. n-1개의 간선이 선택될 때까지 반복한다.

초기에는 각 정점이 서로 분리된 작은 트리, 즉 숲을 이룬다. 간선을 선택할 때 서로 다른 두 트리를 연결하면 두 집합이 하나로 합쳐진다. 같은 트리에 이미 속한 두 정점을 잇는 간선은 사이클을 만들므로 제외한다. 실제 구현에서는 서로소 집합인 Union-Find를 사용해 두 정점이 같은 집합인지 효율적으로 검사한다.

Prim	Kruskal
현재 트리와 바깥 정점을 잇는 최소 간선을 선택	전체 남은 간선 중 최소 비용 간선을 선택
과정 내내 하나의 트리를 유지	중간에 여러 분리된 트리, 즉 숲이 존재
정점 집합의 확장 관점	간선 정렬과 사이클 검사 관점

Kruskal에서는 비용이 작아도 사이클을 만드는 간선은 선택하지 않는다. “가장 싼 간선부터 모두 고른다”가 아니라 “사이클을 만들지 않는 가장 싼 간선부터 고른다”가 정확한 설명이다.

Sollin 알고리즘

각 트리의 최저 비용 간선을 동시에 선택하기

Sollin 알고리즘은 Borůvka 알고리즘이라고도 한다. 처음에는 간선이 하나도 없어 각 정점이 독립된 트리인 숲에서 시작한다. 한 단계마다 숲의 각 트리에 대해 그 트리와 다른 트리를 연결하는 최소 비용 간선을 선택하여 여러 트리를 동시에 합친다.

선택된 간선을 반영해 연결 요소가 줄어들면, 새로 만들어진 각 트리에서 다시 외부로 나가는 최소 비용 간선을 선택한다. 이 단계를 하나의 신장 트리가 될 때까지 반복한다. Prim이 한 트리를 한 간선씩 확장하고 Kruskal이 전체 간선을 순서대로 검사하는 것과 달리, Sollin은 여러 연결 요소가 각자 최소 간선을 선택해 병렬적으로 합쳐지는 방식이다.

알고리즘	매 단계의 선택 단위	중간 구조
Prim	현재 하나의 트리에서 나가는 최소 간선	하나의 성장 중인 트리
Kruskal	전체에서 다음 최소 비용의 비순환 간선	여러 트리로 이루어진 숲
Sollin	각 연결 요소에서 외부로 나가는 최소 간선	여러 트리가 단계별로 동시 결합

핵심 개념 정리

그래프 탐색은 시작 정점에서 도달 가능한 정점을 중복 없이 방문한다. DFS는 스택 또는 재귀 호출로 한 경로를 깊게 탐색하고, BFS는 큐로 가까운 정점부터 탐색한다.

신장 트리는 원 그래프의 모든 정점을 포함하고 사이클이 없으며 n개 정점에 n-1개 간선을 갖는다. 가중치 합이 가장 작은 신장 트리가 최소 비용 신장 트리이다.

Prim은 하나의 트리를 확장하고, Kruskal은 간선을 비용 순으로 검사하면서 사이클을 피하며, Sollin은 각 연결 요소의 최소 외향 간선을 동시에 선택해 숲을 합친다.

최종 암기: DFS = 스택·재귀 · BFS = 큐 · 신장 트리 간선 수 = n-1 · MST = 총비용 최소 · Prim = 하나의 트리 확장 · Kruskal = 간선 정렬+사이클 검사 · Sollin = 각 트리의 최소 외향 간선.

예상문제 20개

1. 그래프 탐색에서 visited 표시가 필요한 가장 중요한 이유는?

① 간선 가중치를 자동 계산하기 위해 ② 그래프를 트리로 변환하기 위해 ③ 사이클 등으로 같은 정점을 반복 방문하지 않기 위해 ④ 정점 이름을 정렬하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
그래프에는 사이클과 여러 경로가 존재할 수 있으므로 방문 여부를 기록해야 중복 처리를 막는다.

2. 깊이 우선 탐색의 기본 진행 방식은?

① 한 경로를 가능한 깊이 진행한 뒤 되돌아간다. ② 모든 간선을 비용 순으로 정렬한다. ③ 시작 정점과 같은 레벨만 방문한다. ④ 항상 가중치가 작은 정점으로 이동한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
DFS는 미방문 이웃을 따라 깊게 내려가고 막히면 최근 분기점으로 복귀한다.

3. DFS에서 최근 분기점으로 되돌아가기 위해 사용하는 자료구조는?

① 큐 ② 힙 ③ 해시 테이블 ④ 스택

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
가장 최근에 선택한 지점으로 먼저 돌아가므로 후입선출 스택이 알맞다. 재귀 호출도 호출 스택을 사용한다.

4. 너비 우선 탐색에서 사용하는 핵심 자료구조는?

① 스택 ② 큐 ③ 이진 탐색 트리 ④ 우선순위 없는 배열만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
BFS는 먼저 발견한 정점을 먼저 처리하는 선입선출 순서이므로 큐를 사용한다.

5. BFS에서 새 인접 정점의 visited를 표시하기에 적절한 시점은?

① 모든 탐색이 끝난 뒤 ② 큐에서 두 번 꺼낸 뒤 ③ 정점을 발견하여 큐에 넣는 순간 ④ 방문 표시는 필요 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
큐에 넣을 때 즉시 표시하면 다른 정점이 같은 이웃을 중복 삽입하는 것을 막을 수 있다.

6. 가중치가 없는 그래프에서 시작 정점으로부터 간선 수가 가장 적은 경로를 구하는 데 적합한 것은?

① 후위 순회 ② 힙 정렬 ③ 이진 검색 ④ BFS

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
BFS는 시작점에서 같은 거리의 정점을 레벨별로 방문하므로 비가중 최단 경로를 찾는다.

7. DFS와 BFS의 방문 순서에 공통으로 영향을 주는 것은?

① 인접 정점을 검사하거나 저장한 순서 ② 정점의 메모리 크기만 ③ 신장 트리의 총비용만 ④ 간선 수와 무관하게 항상 동일하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
선택 가능한 이웃이 여럿이면 인접 리스트 또는 행렬을 검사하는 순서에 따라 세부 방문 순서가 달라진다.

8. 정점이 n개인 신장 트리가 갖는 간선 수는?

① n개 ② n-1개 ③ n+1개 ④ 2n개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
모든 정점을 연결하면서 사이클이 없는 트리는 정점 수보다 하나 적은 간선을 가진다.

9. 연결 그래프 G의 신장 트리에 대한 설명으로 옳은 것은?

① G의 정점 일부만 포함한다. ② 반드시 사이클을 하나 포함한다. ③ G에 없던 간선을 새로 만든다. ④ G의 모든 정점과 일부 간선을 포함하는 트리이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
신장 트리는 원 그래프의 모든 정점을 연결하되 사이클을 제거한 부분 그래프이다.

10. 최소 비용 신장 트리의 목적은?

① 간선 수를 n개로 만드는 것 ② 모든 사이클을 유지하는 것 ③ 모든 정점을 연결하는 신장 트리의 총 가중치를 최소화하는 것 ④ 가장 큰 비용 간선만 선택하는 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
MST는 모든 정점을 사이클 없이 연결하는 여러 신장 트리 중 간선 비용 합이 가장 작은 것이다.

11. Prim 알고리즘이 매 단계 선택하는 간선은?

① 전체에서 가장 비싼 간선 ② 현재 트리와 바깥 정점을 잇는 최소 비용 간선 ③ 현재 트리 내부의 최소 비용 간선 ④ 사이클을 만드는 최소 간선

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
Prim은 이미 포함된 정점 집합과 아직 포함되지 않은 정점을 연결하는 가장 싼 간선으로 트리를 확장한다.

12. Prim 알고리즘의 중간 과정에서 유지되는 구조는?

① 하나의 연결된 성장 중인 트리 ② 반드시 세 개의 분리된 트리 ③ 모든 간선을 포함한 그래프 ④ 루트가 없는 사이클

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
Prim은 시작 정점에서 출발한 하나의 트리에 새 정점과 간선을 계속 붙인다.

13. Kruskal 알고리즘의 첫 번째 핵심 작업은?

① 정점을 깊이 우선 순서로 정렬한다. ② 루트 정점을 고정한다. ③ 간선을 비용이 작은 순서로 정렬한다. ④ 모든 간선을 한꺼번에 선택한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
Kruskal은 가장 싼 간선부터 검사하기 위해 전체 간선을 가중치 오름차순으로 다룬다.

14. Kruskal 알고리즘에서 비용이 작아도 간선을 버리는 경우는?

① 간선이 두 정점을 연결하는 경우 ② 비용이 양수인 경우 ③ 두 정점이 서로 다른 집합인 경우 ④ 선택하면 사이클이 생기는 경우

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
MST는 트리여야 하므로 같은 연결 요소의 두 정점을 다시 잇는 간선은 제외한다.

15. Kruskal의 중간 결과가 여러 개의 분리된 트리일 수 있는 이유는?

① 항상 한 시작 정점에서만 확장하기 때문이다. ② 전체 최소 간선을 순서대로 골라 서로 다른 연결 요소들을 점차 합치기 때문이다. ③ 간선을 전혀 선택하지 않기 때문이다. ④ 사이클만 선택하기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
Kruskal은 하나의 시작 트리를 키우지 않으므로 처음에는 여러 작은 트리로 이루어진 숲이 만들어질 수 있다.

16. Kruskal에서 두 정점이 같은 연결 요소인지 빠르게 검사하는 자료구조는?

① Union-Find 서로소 집합 ② 단순 큐만 ③ 원형 연결 리스트만 ④ 해시 충돌 체인

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
Find로 같은 집합인지 검사하고 Union으로 선택 간선이 잇는 두 집합을 합칠 수 있다.

17. Sollin 알고리즘의 초기 상태는?

① 모든 간선이 이미 선택된 그래프 ② 하나의 완성된 신장 트리 ③ 하나의 사이클 ④ 각 정점이 독립된 트리인 간선 없는 숲

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
Sollin은 각 정점을 하나의 연결 요소로 보고 외부로 나가는 최소 간선을 선택하며 시작한다.

18. Sollin 알고리즘이 한 단계에서 선택하는 것은?

① 전체에서 가장 비싼 간선 하나 ② 각 연결 요소에서 다른 요소로 나가는 최소 비용 간선 ③ 사이클을 만드는 모든 간선 ④ 루트에 인접한 간선만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
각 트리가 자신의 최저 비용 외향 간선을 선택하여 여러 연결 요소가 한 단계에서 함께 합쳐진다.

19. Prim과 Kruskal의 차이를 바르게 설명한 것은?

① Prim은 하나의 트리를 확장하고 Kruskal은 전체 간선을 비용 순으로 검사한다. ② Prim은 큐 탐색이고 Kruskal은 스택 탐색이다. ③ Prim은 사이클을 반드시 만들고 Kruskal은 모든 사이클을 유지한다. ④ 두 알고리즘은 간선 비용을 사용하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
Prim은 정점 집합을 키우고 Kruskal은 비용순 간선을 사이클 여부에 따라 선택한다.

20. Prim·Kruskal·Sollin 알고리즘의 공통 목표는?

① 그래프에 가능한 모든 사이클을 추가하는 것 ② 시작 정점에서 최장 경로를 찾는 것 ③ 가중치 그래프의 최소 비용 신장 트리를 구성하는 것 ④ 모든 간선의 방향을 반대로 바꾸는 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
세 알고리즘은 선택 방식은 다르지만 모든 정점을 최소 총비용으로 연결하는 트리를 구한다.