[알고리즘] - 그래프의 표현 방법 #8

안녕하세요!

그래프 알고리즘을 배우기 전에 반드시 알아야 할 부분이 있습니다!

바로 그래프의 표현 방법입니다.  그래프 관련 문제를 해결하기 위해서는 주어진 그래프를 표현해야 하고,

그 데이터를 바탕으로 그래프 알고리즘을 적용시켜 해결해야 합니다. 

그럼 이제 본격적인 설명에 앞서, 그래프를 표현하는 방법에는 어떤 것들이 있는지 간단한게 알아보고 가도록 하겠습니다.

그래프를 표현하는 방법은 세 가지가 있습니다.

• 인접 행렬(Adjacency matrix) : 두 노드간의 엣지 상태를 행렬 형태로 표현

• 인접 리스트(Adjacency list) : 각 노드 별로 연결되어있는 노드들만 표현

• 간선 리스트(Edge list) : 위의 방법들과 달리 엣지만을 리스트 형태 혹은 배열 형태로 저장하는 방법입니다.

[그래프1 - 방향이 없는 그래프]

[그래프2 - 방향이 있는 그래프]

이제부터 위 그래프를 각 방법으로 표현해 보겠습니다.

인접 행렬(Adjacency matrix)

[그래프1 - 인접 행렬]

[그래프2 - 인접 행렬]

인접 행렬은 노드와 노드 사이의 관계를 행렬 형태로 표현하는 방법입니다.

위 행렬에서 표현된 값이 0이면 노드 자신을 의미, INF면 직접적으로 연결 X, 나머지 값들은 연결된 엣지의 가중치입니다.

그래프 형태에 따라서 간선의 방향이 없으면 대칭행렬 형태로, 방향이 있다면 일반 행렬처럼 표현하면 되는 방식입니다.

이 특성때문에 인접 행렬 방식은 다음과 같은 특징을 같습니다.

1) 두 노드간의 엣지에 직접 접근할 수 있습니다. 예) g[4][2] : 4번노드와 2번노드의 엣지

2) 모든 노드쌍의 관계를 표현해야 하기 때문에 공간복잡도가 O(V^2) 소요됩니다.

따라서 인접 행렬은 밀집 그래프(엣지수가 많은) 형태에서 좋은 성능을 발휘하고 적절한 공간을 소요한다고 여겨지지만,

희소그래프(엣지수가 적은) 형태에서는 공간낭비가 매우 심합니다.(어떤 문제에서는 이 특성때문에 메모리 초과가 발생하기도 합니다)

인접 리스트(Adjacency list)

[그래프1 - 인접 행렬]

[그래프2 - 인접 행렬]

이 방법은 인접 행렬에서 INF와 같은 불필요한 데이터를 제거하고, 실제 존재하는 그래프만을 표현하기 위한 방식입니다.

표현하는 방법은 정점을 기준으로 연결되어 있는 간선을 리스트형태 추가시켜 나가면 됩니다. 

방향이 없는 그래프라면 각 두 노드 리스트에 [상대 노드, 가중치] 형태를 갖는 자료구조를 추가해주면 됩니다.

반면에 방향이 있다면, 출발 노드 리스트에 [목적지 노드, 가중치] 형태를 갖는 자료구조를 추가해주면 됩니다.

이런 리스트적 특징 때문에 인접 리스트에서는 다음 특징을 갖습니다.

1) 두 노드간의 엣지가 존재 여부를 조사하기 위해서는 순차 탐색을 해야하기 때문에 O(V) 시간이 소요됩니다.

2) 인접 행렬과는 달리, 존재하는 엣지만을 표현하기 때문에 O(E) 만큼의 공간이 소요됩니다.

위 특징 때문에 모든 엣지 혹은 적은 엣지를 조사해야하는 그래프 알고리즘에서 유용하게 활용됩니다. 

하지만, 밀집 그래프 형태의 문제에서는 1번 특징으로 인해 시간 초과 문제가 발생할 수 있습니다.

간선 리스트(Edge list)

간선 리스트는 다른 두 방식과는 달리 엣지를 중심으로 표현하는 방법입니다.

즉, 단순하게 [노드1(혹은 출발 노드), 노드2(혹은 도착 노드), 가중치] 형태의 자료구조를 리스트 또는 배열 형태로 저장하는 방식입니다.

따라서 모든 엣지를 살펴보는 알고리즘에서 간편하고 직관적으로 활용할 수 있습니다.

각 방법을 사용해서 주어진 그래프를 표현해 봤습니다.

코드 레벨에서 설명하지는 않았지만, 이는 앞으로 다룰 그래프 관련 알고리즘에서 적어도 한 번씩은 다룹니다.

그때 코드 레벨에서 설명해드리도록 하겠으니 "아! 이런 방식이구나" 정도의 느낌만 알고 가시면 됩니다!