💬 구성요소

• 노드 Node (=정점 Vertex)
  e.g. 도시

• 간선 Edge
  e.g 도로

• 그래프를 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문

• 두 노드는 인접(Adjacent) : 두 노드가 간선으로 연결되어있다.

💬 인접행렬 Adjacency Matrix

2차원 배열로 그래프의 연결 관계를 표현하는 방식

• 연결이 되어있지 않은 노드끼리는 무한 infinity 비용으로 작성

INF = 99999999 # 무한 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
	[0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

💬 인접 리스트 Adjacency List

• 리스트로 그래프의 연결 관계를 표현하는 방식
• 연결리스트로 구현(파이썬은 기본 자료형이 append()와 메소드 제공)

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

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

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

🤔두 방식의 차이

• 메모리측면
  인접행렬 : 모든 관계 저장하므로 메모리 낭비
  인접리스트 : 연결된 관계만 저장하므로 메모리 효율적
  
• 속도
  인접행렬 : 빠름 (인덱스로 바로 접근)
  인접리스트 : 느림 (연결된 데이터 하나씩 확인)