그래프 탐색 알고리즘 : 인접 행렬과 인접 리스트 (Python)

인접 행렬

---

인접 행렬 jpg

 

- 개념 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

- 모든 관계를 저장하므로 노드의 개수가 많을 수록 메모리가 낭비된다.

- 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다.

- 구현

INF = 999999999 # 9 자리수

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
	'''
    [노드0과 노드0 간선 비용, 노드0과 노드1 간선 비용, 노드0과 노드2 간선 비용]
    [노드1과 노드0 간선 비용, 노드1과 노드1 간선 비용, 노드1과 노드2 간선 비용]
    [노드2와 노드0 간선 비용, 노드2와 노드1 간선 비용, 노드2와 노드2 간선 비용]
    '''
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

 

 

 

인접 리스트

---

인접 리스트 jpg

 

- 개념 : 연결 리스트 자료 구조 이용(파이썬은 2차원 리스트 이용)

- 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

- 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 

- 구현

# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph [[] for _ in range(3)]

# 노드0에 연결된 노드 정보 저장
graph[0].append((1, 7)) # (노드1, 노드0과 노드1의 간선 비용)
graph[0].append((2, 5)) # (노드2, 노드0과 노드2의 간선 비용)

# 노드1에 연결된 노드 정보 저장
graph[1].append((0, 7))

# 노드2에 연결된 노드 정보 저장
graph[2].append((0, 5))

print(graph)