패스트캠퍼스 온라인 강의

Part1.Ch02-06. 그래프

1. 그래프란?

  • 사물을 정점과 간선으로 나타내기 위한 도구

ㄱ. 인접행렬 : 2차원 배열을 사용

ㄴ. 인접 리스트 : 연결 리스트를 이용

  • 인접 리스트 > 인접 행렬

2. 인접 행렬 ( 메모리 : O(V^2), 연결 여부 : O(1) )

  • 그래프를 2차원 배열로 표현한다.

image

0에서 0으로 가기위한 비용은 0, 0에서 1로 가기위해서는 3, 0에서 2로 가기에는 7, 1에서 0으로 가기에는 3, 1에서 1로 가기위해서는 0, 1에서 2로 가기위해서는 선이 없기에 무한…

즉, 2차원 배열에는 각각 노드가 다른 노드로 가기위한 비용을 의미한다.

공간은 노드의 개수 * 노드의 개수만큼 필요해진다.

  • 방향성이 없는 무방향 그래프, 모든 간선에 가중치가 없는 무가중치 그래프일 때에는 간선의 유무에 따라 0과 1로 표현한다.

  • 방향 그래프이자 가중치가 있는 가중치 그래프일때에는 방향에 따른 가중치만을 계산한다.

3. 인접 리스트 ( 메모리 : O(V+E), 연결 여부 : O(V) )

  • 그래프를 리스트로 표현한다.

image

0에서 1로 가는건 3, 0에서 2로 가는건 7

1에서 0으로 가는건 3

2에서 0으로 가는건 7

자기 자신을 가리키거나 간선이 없는 경우는 아예 따지지 않는다. (상대적으로 메모리 효율적이다.

  • 무방향 무가중치 그래프
  • 방향 가중치 그래프

4. 인접행렬 VS 인접 리스트

  • 최단 경로 알고리즘 : 인접행렬 < 인접리스트

WHY? 간선 개수가 적다.