장 실습: 그래프 하나를 네 가지로 분석하기
그래프 하나를 네 가지로 분석하기 과제를 단계별로 진행하고, 손 계산과 코드 출력을 비교합니다. 시작 상태와 체크포인트, 결과가 다를 때 확인할 곳, 완성 파일과 풀이를 함께 제공합니다.
길이 짧다는 말을 간선 수로 읽는지 비용으로 읽는지에 따라 선택하는 경로가 달라집니다. 깊이 우선 탐색과 너비 우선 탐색까지 배운 방법으로 같은 그래프의 차수, 오일러 경로, 두 종류의 거리를 한 번에 비교합니다.
이 글을 마치면 다음을 할 수 있습니다.
- 무방향 간선 목록에서 차수와 오일러 경로의 종류를 구합니다.
- 같은 시작점에서 최소 간선 수와 최소 비용을 나란히 출력합니다.
시작 상태
그래프의 모델과 표현의 차수, 오일러 경로와 해밀턴 경로의 판정 조건, 최단 경로의 Dijkstra, 앞 글의 너비 우선 탐색을 씁니다. 간선 목록은 아래 과제의 다섯 간선으로 시작합니다.
Python은 교재 첫머리의 준비를 그대로 쓰며 추가 패키지는 설치하지 않습니다. 새 파일 graph_report.py를 만들고 이 실습의 함수와 마지막 호출만 모읍니다. 실행 명령은 python graph_report.py입니다. 완성 파일에는 필요한 함수가 모두 들어 있으므로 앞 글 파일을 import하지 않습니다.
완성 조건
최단 경로의 가중치 그래프(AB = 2, AC = 5, BC = 1, BD = 6, CD = 2)를 앞의 네 글의 방법으로 분석하는 graph_report.py를 완성하세요. 실행하기 전에 네 줄의 출력을 손으로 먼저 적어 둡니다.
- 가중치가 붙은 간선 목록에서 무방향 인접 목록을 만듭니다.
- 정점별 차수, 차수의 합, 간선 수의 두 배를 출력합니다.
- 연결되어 있는지와 홀수 차수인 정점의 수로 오일러 순환, 오일러 경로, 없음을 판정해 출력합니다.
- A에서 각 정점까지 간선 수가 가장 적은 거리와, 비용이 가장 작은 거리를 출력합니다.
힌트: 연결 여부는 너비 우선 탐색 한 번이 모든 정점을 방문하는지로 판정합니다. 간선 목록에서 만든 그래프에는 간선이 없는 정점이 없습니다.
1단계: 무방향 인접 목록과 차수 만들기
각 간선을 두 정점의 이웃 목록에 모두 넣습니다. 정점별 목록 길이와 전체 합을 계산합니다.
체크포인트: 차수는 A:2, B:3, C:3, D:2이고 합과 간선 수의 두 배는 모두 10입니다.
2단계: 연결 여부와 오일러 경로 판정하기
너비 우선 탐색으로 모든 정점에 닿는지 본 뒤 홀수 차수인 정점을 셉니다.
체크포인트: 홀수 차수인 B와 C를 양 끝으로 하는 오일러 경로 B-C가 출력됩니다.
3단계: 간선 수와 비용을 나란히 출력하기
A에서 시작한 bfs_depth와 dijkstra의 결과를 각각 출력합니다.
체크포인트: D까지 간선 수는 2이고 최소 비용은 5입니다. 같은 거리를 두 번 출력한 것이 아닌지 봅니다.
다를 때 먼저 볼 곳
| 증상 | 먼저 볼 곳 |
|---|---|
| 차수 합과 간선 수의 두 배가 다르다 | 무방향 간선을 양쪽 정점 목록에 모두 넣었는지 |
| 오일러 경로가 없다고 나온다 | 연결 여부를 확인한 뒤 홀수 차수 정점을 세었는지 |
| D의 최소 비용이 6보다 작아지지 않는다 | A→B→C→D로 이어지는 완화가 수행되는지 |
완성 파일과 풀이
먼저 위 단계까지 직접 작성해 보세요. 예상한 결과와 비교할 준비가 되면 아래를 펼칩니다.
완성 파일과 풀이 보기
from collections import deque
from heapq import heappop, heappush
edges = [("A", "B", 2), ("A", "C", 5), ("B", "C", 1), ("B", "D", 6), ("C", "D", 2)]
graph = {}
for u, v, weight in edges:
for x in (u, v):
if x not in graph:
graph[x] = []
graph[u].append((v, weight))
graph[v].append((u, weight))
def bfs_depth(graph, start):
depth = {start: 0}
queue = deque([start])
while queue:
v = queue.popleft()
for u, _ in graph[v]:
if u not in depth:
depth[u] = depth[v] + 1
queue.append(u)
return depth
def dijkstra(graph, start):
distance = {v: float("inf") for v in graph}
distance[start] = 0
heap = [(0, start)]
while heap:
cost, v = heappop(heap)
if cost != distance[v]:
continue
for u, weight in graph[v]:
if cost + weight < distance[u]:
distance[u] = cost + weight
heappush(heap, (cost + weight, u))
return distance
def euler_kind(graph):
first = list(graph)[0]
if len(bfs_depth(graph, first)) != len(graph):
return "없음: 연결되어 있지 않음"
odd = [v for v in graph if len(graph[v]) % 2 == 1]
if len(odd) == 0:
return "오일러 순환"
if len(odd) == 2:
return "오일러 경로 " + odd[0] + "-" + odd[1]
return "없음: 홀수 차수인 정점 " + str(len(odd)) + "개"
degree = {v: len(graph[v]) for v in graph}
print(degree, sum(degree.values()), 2 * len(edges))
print(euler_kind(graph))
print(bfs_depth(graph, "A"))
print(dijkstra(graph, "A")){'A': 2, 'B': 3, 'C': 3, 'D': 2} 10 10
오일러 경로 B-C
{'A': 0, 'B': 1, 'C': 1, 'D': 2}
{'A': 0, 'B': 2, 'C': 3, 'D': 5}첫 줄은 첫 글의 중간 점검에서 간선 BD를 더해 센 값과 같습니다. 홀수 차수인 정점이 B와 C 둘이므로 그 둘을 양 끝으로 하는 오일러 경로가 있고, 손으로 그리면 B, A, C, B, D, C가 다섯 간선을 한 번씩 지납니다. 셋째 줄과 넷째 줄을 견주면 D는 간선 2개로 닿지만 가장 싼 길은 간선 3개짜리 A → B → C → D의 5입니다.
확인 방법: 넷째 줄을 최단 경로의 Dijkstra 표 마지막 행과 맞추어 봅니다. 첫 줄의 두 수가 다르면 간선을 양쪽 목록에 모두 넣었는지부터 보세요.
더 해 보기
edges에서 BD를 빼면 네 줄이 어떻게 바뀌는지 먼저 적고 확인해 보세요.- 간선
("E", "F", 1)을 더하면 둘째 줄과 넷째 줄이 어떻게 바뀌는지 확인해 보세요.
방문 순서가 예상과 다르면 정점 이름, 이웃의 순서, 방문 표시를 하는 시점을 차례로 확인해 보세요. 다음 장의 트리와 이진 트리의 구조에서는 사이클이 없는 연결 그래프인 트리를 다루고, DFS와 BFS는 트리의 순회에서 다시 만납니다. 그래프 알고리즘을 더 깊이 공부하려면 MIT 6.006의 강의 노트를 참고하세요.