[알고리즘] python 그래프 (인접 행렬/인접 리스트)

💡 탐색 ?

- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.

 

💡 그래프 탐색 ?

- 그래프 탐색 알고리즘이란 그래프의 모든 노드를 방문하는 알고리즘을 의미.

- 트리 탐색은 그래프 탐색의 특수한 일종이며 방문한 노드는 다시 방문하지 않음.

 

• 인접 행렬 : 2차원 배열을 활용하여 그래프를 표현하는 방식
  • 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성
  • 불필요한 메모리가 소요되며 인접 리스트 보다 빠르다.

# 인접 행렬 

# 무한 비용선언
INF = 999999999

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)
👉🏽 [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

• 인접 리스트 : 연결 리스트를 활용하여 그래프를 표현하는 방식
  • 메모리를 효율적으로 사용하지만 인접행렬 방식보다 느리다.

#### ⚡️ 인접 리스트(Adjacency List)

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

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

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

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

print(graph)
👉🏽 [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]