8-1. 그래프의 표현

2차원 리스트 생성

• 리스트 객체를 생성하는 방법

  A = [[0 for col in range(4)] for row in range(3)]
  

• 얕은 복사를 일으켜 생성하는 방법

  • 해당 경우 리스트 객체는 1개만 생성하고, 모든 리스트의 각 요소가 해당 객체를 바라보게 됨

    

  • 이러한 경우 다른 원소의 값도 함께 변경될 수 있기에 주의해야 함

  A = [[0]*4]*3
  

1) 에지 리스트(edge list)

• 에지를 중심으로 그래프를 표현

  • 리스트에 출발 노드/도착 노드를 저장하여 에지를 표현
  • 또는 출발 노드/도착 노드/가중치를 저장하여 가중치가 있는 에지를 표현함

• 구현 자체는 쉽다는 장점이 존재

  • 그러나, 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않음

• 노드 사이의 최단 거리를 구하는 벨만-포드 또는 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용됨

  cf) 노드 중심 알고리즘에는 잘 사용하지 x

에지 리스트로 가중치 없는 그래프 표현하기

• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현함

  → 리스트의 열은 2개면 충분함

• 방향이 있는 그래프는 순서에 맞게 노드를 리스트에 저장하는 방식으로 표현함
• 이후 노드를 리스트에 저장하여 에지를 표현 ⇒ 에지 리스트

에지 리스트로 가중치 있는 그래프 표현하기

• 가중치를 저장할 수 있는 열을 추가(ex. 3번째 열)

2) 인접 행렬(adjacency matrix)

• 2차원 리스트를 자료구조로 이용하여 그래프로 표현하는 방식
• 에지 리스트와 다르게 노드 중심으로 그래프를 표현

인접 행렬로 가중치 없는 그래프 표현하기