[알고리즘이론] 그래프 파이썬으로 구현하기

파이썬에서 그래프를 구현하는 방법은 여러 가지가 있습니다. 이 중에서 대표적인 방법은 인접 리스트와 인접 행렬입니다.

인접 리스트

인접 리스트(Adjacency List)는 그래프를 연결 리스트로 표현하는 방식입니다. 파이썬에서는 딕셔너리를 이용하여 각 노드에 연결된 노드들을 리스트로 저장합니다. 예를 들어, 다음과 같은 인접리스트가 있다고 합시다.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D']
}

위 코드에서 graph 딕셔너리는 각 노드와 그에 대한 연결 리스트를 저장합니다. 예를 들어, 'A' 노드와 연결된 노드들은 'B'와 'C'이며, 'B' 노드와 연결된 노드들은 'A', 'C', 'D'입니다.

 

인접 행렬

인접 행렬(Adjacency Matrix)은 그래프를 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]
]

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] ]

위 코드에서 graph 리스트는 2차원 배열로, 행과 열의 번호가 각각 노드의 번호와 대응됩니다. 예를 들어, 0행 1열은 'A'와 'B'가 연결되어 있는지를 나타냅니다. 0행 1열이 1이므로 'A'와 'B'가 연결된 것입니다.

그리고 딕셔너리(Dictionary)를 사용하여 구현할 수 있습니다. 딕셔너리는 각각의 키(Key)에 대해 값을 저장할 수 있는 자료형으로, 그래프의 노드를 키(Key)로, 각 노드의 인접 노드를 값(Value)으로 저장할 수 있습니다.

 

예제: 무방향 그래프 구현

다음은 무방향 그래프를 구현하는 예제입니다.

graph = {}

# 그래프에 노드 추가
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'D']
graph['D'] = ['B', 'C', 'E']
graph['E'] = ['D']

print(graph)

위 코드에서는 딕셔너리 graph에 각 노드를 키(Key)로, 각 노드의 인접 노드를 값(Value)으로 추가합니다. 예를 들어, '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)

위 코드에서는 딕셔너리 graph에 각 노드를 키(Key)로, 각 노드의 인접 노드를 값(Value)으로 추가합니다. 예를 들어, 'A' 노드의 인접 노드는 'B'와 'C'입니다. 'E' 노드는 인접 노드가 없으므로 빈 리스트([])로 초기화합니다.

출력 결과는 다음과 같습니다.

{'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': []