[그래프] 그래프의 표현방법

그래프의 두 가지 표현방법

그래프의 표현 방법은 대부분 2가지 중 하나를 사용하는데, 하나는 인접 행렬, 다른 하나는 인접 리스트입니다.
인접 행렬은 말 그대로 행렬(2차원 배열)로 표현하고, 인접 리스트는 연결 리스트(Linked List) 혹은 동적 배열(ex. C++ vector 컨테이너)를 사용해 구현합니다.

무향 그래프

1번 정점은 2, 5 와,
2번 정점은 1, 3, 5 와,
3번 정점은 2, 4 와,
4는 3, 5, 6 과,
5는 1, 2, 4 와,
6은 4와 연결되어 있습니다.

이것을 인접 행렬로 나타내면

1 2 3 4 5 6

0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0

와 같이 나옵니다.

1과 2가 연결되어 있기 때문에 (1, 2)와 (2, 1)이 1이 됩니다.
마찬가지로 4와 6이 연결되어 있기 때문에 (4, 6)과 (6, 4)가 1이 됩니다.
만약 그래프가 가중치 그래프라면 1 대신에 가중치를 써주면 됩니다.

무향 그래프는 u에서 v로 가는 간선과 v에서 u로 가는 간선이 동일하기 때문에 삼각 행렬로 표현이 가능합니다.

인접 리스트로 나타내면 아래와 같이 할 수 있습니다.

1 2 3 4 5 6

1 - [2, 5] 2 - [1, 3, 5] 3 - [2, 4] 4 - [3, 5, 6] 5 - [1, 2, 4] 6 - [4]

유향 그래프

이 그래프를 통해 방향 그래프의 표현 방법을 알아봅시다.

1은 2로 갈 수 있고,
2는 4로 갈 수 있고,
3은 1로 갈 수 있고,
4는 3, 5, 6로 갈 수 있고,
5와 6은 갈 수 있는 곳이 없습니다.

세로 방향이 출발지, 가로 방향이 도착지라 가정하고 인접 행렬을 만들면,

1 2 3 4 5 6

0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0

처럼 표현합니다. 만약 가중치가 있는 그래프라면, 1 대신에 가중치를 써주면 됩니다.

유향 그래프는 u->v로 가는 간선과 v->u로 가는 간선이 다르기 때문에 삼각 행렬로 나타낼 수 없습니다.

인접 리스트로 나타내면,

1 2 3 4 5 6

1 - [2] 2 - [4] 3 - [1] 4 - [3, 5, 6] 5 - [] 6 - []

처럼 됩니다.

두 가지 방법의 비교

인접리스트와 인접행렬을 비교해봅시다.

인접 행렬을 이용하면 정점 간의 인접 여부를 빠르게 알 수 있지만( O(1) )
행렬로 저장할 때 메모리의 양이 N^2 에 이르는 단점이 있습니다.

인접 리스트를 이용하면 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색을 해야하지만( O(n) )
정점과 간선 사이의 삽입이 빠르고 메모리를 적게 소모한다는 장점이 있습니다.

그래프의 정점의 개수가 많지 않거나 인접 여부를 빨리 알아야 한다면 인접 행렬을 사용하고, 메모리 효율성을 우선시 하고 정점/간선의 입력이 자주 일어난다면 인접 리스트를 활용하면 됩니다.