Python에서 그래프를 구현하는 방법에는 여러 가지가 있습니다. 그 중 가장 대표적인 방법은 인접리스트(Adjacency List)와 인접행렬(Adjacency Matrix)이다.
이웃 목록
인접 목록은 그래프를 연결된 목록으로 나타내는 방법입니다. 파이썬에서는 각 노드에 연결된 노드를 리스트로 저장하기 위해 딕셔너리를 사용합니다. 예를 들어 다음과 같은 인접 목록이 있다고 가정합니다.
graph = {
'A': ('B', 'C'),
'B': ('A', 'C', 'D'),
'C': ('A', 'B', 'D', 'E'),
'D': ('B', 'C', 'E', 'F'),
'E': ('C', 'D'),
'F': ('D')
}위의 코드에서 그래프 사전은 모든 노드와 해당 링크의 목록을 저장합니다. 예를 들어 노드 “A”에 연결된 노드는 “B”와 “C”이고 노드 “B”에 연결된 노드는 “A”, “C” 및 “D”입니다.
이웃 행렬
인접 행렬은 그래프를 2차원 배열로 표현하는 방법입니다. Python에서는 2차원 목록으로 구현할 수 있습니다. 인접행렬의 i번째 행과 j번째 열이 1이면 i와 j가 연결되고 0이면 연결되지 않습니다. 예를 들어 위의 다이어그램을 인접 행렬로 구현하면 다음과 같습니다.
graph = (
(0, 1, 1, 0, 0, 0),
(1, 0, 1, 1, 0, 0),
(1, 1, 0, 1, 1, 0),
(0, 1, 1, 0, 1, 1),
(0, 0, 1, 1, 0, 0),
(0, 0, 0, 1, 0, 0)
)그래프 = ((0, 1, 1, 0, 0, 0), (1, 0, 1, 1, 0, 0), (1, 1, 0, 1, 1, 0), (0, 1, 1, 0, 1, 1), (0, 0, 1, 1, 0, 0), (0, 0, 0, 1, 0, 0) )
위의 코드에서 차트 목록은 행과 열 번호가 노드 번호에 해당하는 2차원 배열입니다. 예를 들어 행 0 열 1은 “A”와 “B”가 연결되어 있는지 보여줍니다. 행 0, 열 1은 1이므로 ‘A’와 ‘B’가 연결됩니다.
그리고 사전으로 구현할 수 있습니다. 사전은 각 키에 대한 값을 저장할 수 있는 데이터 유형으로 다이어그램의 노드를 키로, 각 노드의 인접 노드를 값으로 저장할 수 있습니다.
예: 무방향 그래프 구현
다음은 무방향 그래프 구현의 예입니다.
graph = {}
# 그래프에 노드 추가
graph('A') = ('B', 'C')
graph('B') = ('A', 'D')
graph('C') = ('A', 'D')
graph('D') = ('B', 'C', 'E')
graph('E') = ('D')
print(graph)위의 코드는 각 노드를 키로 추가하고 각 노드의 이웃 노드를 값으로 사전 그래프에 추가합니다. 예를 들어, 노드 ‘A’의 이웃은 ‘B’와 ‘C’입니다.
출력 결과는 다음과 같습니다.
{'A': ('B', 'C'), 'B': ('A', 'D'), 'C': ('A', 'D'), 'D': ('B', 'C', 'E'), 'E': ('D')}예: 유방향 그래프 구현
다음은 방향성 그래프 구현의 예입니다.
graph = {}
# 그래프에 노드 추가
graph('A') = ('B', 'C')
graph('B') = ('D')
graph('C') = ('D')
graph('D') = ('E')
graph('E') = ()
print(graph)위의 코드는 각 노드를 키로 추가하고 각 노드의 이웃 노드를 값으로 사전 그래프에 추가합니다. 예를 들어, 노드 ‘A’의 이웃은 ‘B’와 ‘C’입니다. 노드 ‘E’는 이웃 노드가 없으므로 빈 목록(())으로 초기화합니다.
출력 결과는 다음과 같습니다.
{'A': ('B', 'C'), 'B': ('D'), 'C': ('D'), 'D': ('E'), 'E': ()