알고리즘 - 그래프의 표현

그래프의 표현

안접 행렬을 이용한 표현

• 인접 행렬(adjacency matrix): 2차원 배열을 이용해 간선들의 집합을 표현
• 무방향 그래프에서는 인접 행렬이 항상 대칭 행렬 따라서 배열의 상위 삼각이나 하위 삼각만 저장하여 메모리 절약 가능
• 방향 그래프라면 인접 행렬은 대칭이 아니고, 간선의 수와 동일한 수의 행렬 성분들이 1을 갖게 된다

인접 리스트를 이용한 표현

• 인접 리스트: 각 정점이 인접한 정점 리스트를 갖도록 하여 간선들을 표현

인접 행렬과 인접 리스트 중에서 어떤 것을 사용할까?

• 정점이 $n$개인 그래프를 표현하기 위한 메모리의 양은 인접 행렬의 경우 $n^2$이므로 인접 리스트 보다는 약간 불리함
• 그래프에 간선 $(u,v)$가 있는지를 검사하려면 행렬은 해당 성분을 바로 검사하면 되지만, 인접 리스트에서는 정점 $u$의 인접 리스트에서 $v$가 있는지 하나씩 검사해 보아야 하므로 인접리스트가 불리

따라서

• 메모리 사용량이 중요하거나 정점에 비해 간선이 별로 없는 희소 그래프 에서는 “인접리스트”
• 정점끼리의 인접 여부를 빨리 알아내야 하거나, 완전 그래프나 이와 유사한 조밀 그래프(dense graph)라면 “인접행렬”