딕셔너리로 그래프 표현하기
Python에서는 딕셔너리(Dictionary)를 활용해 그래프(Graph)를 손쉽게 구현할 수 있습니다. 딕셔너리에서 각 키(key)는 그래프의 정점(vertex)을 나타내고, 값(value)에는 해당 정점과 연결된 정점들의 목록을 저장합니다. 이렇게 구성된 전체 구조는 곧 그래프 G(V, E)의 인접 리스트(Adjacency List)와 같은 형태가 됩니다.
기본 딕셔너리 객체를 사용해도 되지만, 여기서는 collections 모듈의 defaultdict를 사용합니다. defaultdict는 존재하지 않는 키에 접근할 때 기본값을 자동으로 생성해 주는 등 유용한 부가 기능을 제공하며, 하나의 추가 쓰기 가능 인스턴스 변수를 가지고 있습니다.
입력 파일 준비하기
이 예제에서는 정점의 개수, 간선의 개수, 정점 이름 목록, 그리고 간선 정보가 담긴 텍스트 파일을 사용합니다. 무방향 그래프(undirected graph)이므로 각 간선은 (u,v)와 (v,u)처럼 양방향으로 두 번 기록됩니다.
예제에서 사용되는 그래프는 다음과 같습니다.
위 그래프를 표현하는 입력 파일은 아래와 같습니다.
Graph_Input.txt
6 8 A|B|C|D|E|F A,B B,A A,C C,A B,D D,B B,E E,B C,E E,C D,E E,D D,F F,D E,F F,E
파일 처리 순서는 다음과 같습니다. 먼저 정점 이름들을 읽어 각 정점마다 빈 리스트를 생성하고, 이후 간선 정보를 한 줄씩 읽으면서 연결 관계를 리스트에 채워 넣습니다.
그래프 생성 코드
from collections import defaultdict
def create_graph(filename):
# 키(정점)와 대응하는 리스트(연결 정점)로 구성된 딕셔너리 생성
graph = defaultdict(list)
with open(filename, 'r') as graph_file:
vertex = int(graph_file.readline()) # 정점 개수
edges = int(graph_file.readline()) # 간선 개수
vert_names = graph_file.readline()
vert_names = vert_names.rstrip('\n') # 줄바꿈 문자 제거
nodes = vert_names.split('|') # 정점 이름 분리
for node in nodes: # 정점별 빈 리스트 생성
graph[node] = []
# 파일에서 간선을 읽어 리스트 채우기
for line in graph_file:
line = line.rstrip('\n') # 줄바꿈 문자 제거
edge = line.split(',')
graph[edge[0]].append(edge[1]) # edge[0]: 출발, edge[1]: 도착
return graph
my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys(): # 그래프 출력
print(node + ': ' + str(my_graph[node]))
실행 결과
A: ['B', 'C'] B: ['A', 'D', 'E'] C: ['A', 'E'] D: ['B', 'E', 'F'] E: ['B', 'C', 'D', 'F'] F: ['D', 'E']
이제 생성된 그래프 G(V, E)에 대해 몇 가지 기본 연산을 살펴보겠습니다. 먼저 출발 정점에서 도착 정점까지의 경로(path)를 구하는 방법입니다. 아래 코드를 실행하려면 앞서 소개한 방법으로 그래프를 먼저 생성해야 합니다.
특정 경로 찾기
# 출발점에서 도착점까지의 경로를 찾는 함수
def get_path(graph, src, dest, path=[]):
path = path + [src]
if src == dest: # 도착점을 찾으면 종료
return path
for vertex in graph[src]:
if vertex not in path:
new_path = get_path(graph, vertex, dest, path)
if new_path:
return new_path
return None
my_graph = create_graph('Graph_Input.txt')
path = get_path(my_graph, 'A', 'C')
print('노드 A에서 C까지의 경로: ' + str(path))
실행 결과
노드 A에서 C까지의 경로: ['A', 'B', 'D', 'E', 'C']
모든 경로 찾기
다음은 출발 정점에서 도착 정점까지 가능한 모든 경로를 구하는 방법입니다. 마찬가지로 실행 전에 그래프를 먼저 생성해야 합니다.
# 출발점에서 도착점까지의 모든 경로를 찾는 함수
def get_all_path(graph, src, dest, path=[]):
path = path + [src]
if src == dest: # 도착점을 찾으면 종료
return [path]
paths = []
for vertex in graph[src]:
if vertex not in path:
new_paths = get_all_path(graph, vertex, dest, path)
for new_path in new_paths:
paths.append(new_path)
return paths
my_graph = create_graph('Graph_Input.txt')
paths = get_all_path(my_graph, 'A', 'C')
print('노드 A에서 C까지의 모든 경로:')
for path in paths:
print(path)
실행 결과
노드 A에서 C까지의 모든 경로: ['A', 'B', 'D', 'E', 'C'] ['A', 'B', 'D', 'E', 'C'] ['A', 'B', 'D', 'F', 'E', 'C'] ['A', 'B', 'D', 'F', 'E', 'C'] ['A', 'B', 'D', 'F', 'E', 'C'] ['A', 'B', 'E', 'C'] ['A', 'C']
최단 경로 찾기
마지막으로 출발 정점에서 도착 정점까지의 최단 경로(shortest path)를 구하는 방법입니다. 이 코드 역시 실행 전에 앞서 설명한 방법으로 그래프를 생성해야 합니다.
# 출발점에서 도착점까지의 최단 경로를 찾는 함수
def get_shortest_path(graph, src, dest, path=[]):
path = path + [src]
if src == dest: # 도착점을 찾으면 종료
return path
shortest = None
for vertex in graph[src]:
if vertex not in path:
new_path = get_shortest_path(graph, vertex, dest, path)
if new_path:
if not shortest or len(new_path) < len(shortest):
shortest = new_path
return shortest
my_graph = create_graph('Graph_Input.txt')
path = get_shortest_path(my_graph, 'A', 'C')
print('노드 A에서 C까지의 최단 경로: ' + str(path))
실행 결과
노드 A에서 C까지의 최단 경로: ['A', 'C']