13강. 그래프의 표현

[ 목차 ]

1. 그래프 표현

2. 인접 리스트와 인접행렬의 비교

3. 가중 그래프

 

1. 그래프 표현

1) 인접리스트 표현 Adjacency-list representation

  1] 정점 하나당 리스트 하나인 크기가 V인 배열

  2] 정점 하나에 인접한 모든 정점을 리스트에 저장

  3] 비방향성 그래프에서는 방향성 그래프로 변환해서 저장하며, 공간을 많이 쓴다는 단점을 보유

2) 인접행렬 표현 Adjacency-matrix representation

  1] 크기가 V x V인 행렬

  2] 두 정점 i와 j를 잇는 간선이 있다면 행렬의 (i,j)는 1 아니면 0

  3] 무방향성은 양방향으로 간선이 존재하므로 하위 삼각 행렬이 상위 삼각 행렬과 대칭

 

2. 인접 리스트와 인접행렬의 비교

1) G가 성기면 인접리스트가 낫고 촘촘하면 인접행렬이 좋음

2) 간선을 찾는데 걸리는 시간

3) 모든 간선을 찾거나 방문하는데 걸리는 시간

 

3. 가중 그래프

1) 간선이 숫자로 표현되는 값을 가지는 그래프

2) 인접 리스트에서는 정점 외에 간섬의 값을 추가 저장

3) 인접행렬에서는 1 대신 간선의 값을 저장