[Graph] 그래프의 표현 - 인접 행렬과 인접 리스트 (Adjacency Matrix, Adjacency List)

 

 

그래프(Graph) 탐색 문제를 풀기 위해서 가장 먼저 고려해야하는 것은 그 그래프를 어떻게 자료구조로 표현할지에 대한 것이다.

DFS든 BFS든, 최단경로를 찾아내기 위한 다익스트라(Dijkstra)를 이용하든 일단 그래프를 프로그램으로 적절히 옮겨와야 무엇이든 해볼 수 있다.

 

 

정점 (Node 또는 Vertex) 과 간선 (Edge)으로 구성된 그래프를 자료구조로 표현하는 방법에는 인접행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List), 두가지가 있다.

각각 이름에서 알 수 있듯이 행렬(배열)을 이용해 표현하는 방법과 리스트를 이용하는 방법이다.

 

 

여기에서 말하는 '인접'은 두 노드 간 간선이 연결되어있음을 뜻한다.

그래프에서 두 노드가 간선으로 연결되어있다면 인접했다고 표현한다.

즉, 인접이라는 말 자체가 간선을 이야기하는 것이고 따라서 간선 행렬, 간선 리스트 라는 의미로 받아들여도 된다.

 

 

두 표현 방법의 장, 단점이 전혀 다르고 인접 여부를 판단하거나 탐색하는 데 필요한 시간 차이가 크기 때문에 문제에 따라서는 반드시 특정 방법을 이용해야 하는 경우가 있다.

 

 

---

 

 

인접 행렬 (Adjacency Matrix)

 

가장 간단하게 그래프의 간선 정보를 표현할 수 있는 방법이다.

그래프 내에 존재하는 모든 노드를 가로축과 세로축에 위치시키고 각 노드가 간선으로 연결되어있는지 표시한 Table을 이용한다.

 

 

방향과 가중치가 없는 그래프의 인접 행렬 표현

 

그림처럼 각 노드 사이에 간선이 있다면 1로, 없다면 0으로 표시하여 그래프의 연결 관계를 표로 나타낼 수 있다.

프로그램으로 옮길 때 각 노드의 번호를 2차원 배열의 가로 index와 세로 index로 이용할 수 있으므로 아래와 같이 간선 정보를 넣어줄 수 있다.

 

adj[1][2] = 1;
adj[1][3] = 0;
adj[1][4] = 1;
adj[1][5] = 0;
....

 

 

만약 간선에 방향이 있는 그래프라면 아래처럼 가로축을 시작 노드로 Table을 그릴 수 있다.

방향이 없는 그래프와 달리 가로축을 기준으로 볼 때와 세로축을 기준으로 볼 때 채워진 값이 달라진다.

 

 

방향이 있는 그래프의 인접 행렬 표현

 

 

가중치가 있는 그래프를 표현할 때에는 단순히 배열 내 각 노드가 만나는 자리에 1이 아닌 해당 가중치 값을 넣어줌으로써 쉽게 표현 가능하다.

 

 

가중치가 있는 그래프의 인접 행렬 표현

 

 

아래는 일반적인 코딩 테스트 문제에서 흔히 볼수 있는 간선 정보와 이를 인접행렬로 표현하는 코드다.

간선의 시작점과 끝점 노드를 입력받아 인접행렬에 넣어주고 있다.

여기에서는 가중치와 방향이 없는 그래프를 예로 보여준다.

방향이 없기 때문에 a → b 와 b → a 를 모두 표시해준다.

 

9 // 간선의 수 1 2 1 4 2 5 3 4 3 5 4 6 4 7 5 6 5 7

int adj[7][7];
int N, a, b;

cin >> N;
for (int i = 0; i < N; i++) {
	cin >> a >> b;
    	adj[a][b] = 1;
        adj[b][a] = 1;
}

 

 

장점

 

인접 행렬의 장점은 바로 구현과 활용이 쉽다는 점이다.

직관적인 표현 방법이면서 배열의 index가 시작 노드와 도착 노드를 그대로 나타내기 때문에 구현하고 사용하는데 헷갈릴 일이 없다.

 

 

또한 특정 두 노드가 간선으로 연결되어있는지 확인하기 위해 [시작노드][도착노드] 와 같이 index를 이용해 해당 위치의 값만 확인하면 되기 때문에 시간복잡도 O(1)로 확인이 가능하다.

 

 

이러한 장점을 활용하면 가중치가 있는 그래프의 최단 거리를 찾기 위해 배열을 update 할 때에도 간단히 활용할 수 있다.

① → ② 로 가는데에 가중치 1이, ② → ⑤ 로 가는데에 5가 걸리고 이것이 최단거리라고 가정하면, ① → ⑤ 로 향하는 가중치 6을 adj[1][5] 에 넣어줌으로써 최단거리를 바로 update해줄 수 있다.

별도의 배열을 이용하거나 Queue에 함께 넣어서 관리하지 않아도 쉽게 표시하고 이용할 수 있다.

 

 

단점

 

반면 큰 단점이 존재한다.

우선 전체 노드 수의 제곱에 해당하는 크기의 배열이 필요하기 때문에 최대 노드 수가 꽤 큰 문제에서는 메모리 초과에 걸리는 문제가 있을 수 있다.

따지고 보면 모든 노드들 사이에 간선을 저장할 공간을 만들어 두고, 간선이 있는지 없는지 표시하는 방식이기 때문에 메모리 낭비가 심한 방법이다.

 

 

이 때문에 탐색에도 많은 시간이 걸린다.

역시 마치 모든 노드 사이에 간선을 만들어 놓고 연결 되었는지 아닌지를 그 위에 표현한 것과 같은 방식이기 때문에 특정 한 노드에서 연결된 노드를 찾기 위해서 나머지 모든 노드를 확인해봐야 한다.

즉, 그래프 전체를 탐색하기 위해서 노드 수의 제곱, V * V 번 탐색해야 한다.

당연히 노드 수가 많으면 많을수록 시간 초과에 걸릴 가능성도 높다.

 

 

---

 

 

인접 리스트 (Adjacency List)

 

인접행렬의 치명적인 단점을 극복할 수 있는 방법이다.

즉, 실제로 존재하는 간선 정보만 표현하는 자료구조다.

 

 

이를 위해서 리스트의 배열을 활용한다.

전체 노드 수 크기의 1차원 배열을 만들어 각 노드에서 시작하는 간선들을 리스트로 이어놓는 형태를 가진다.

 

 

방향과 가중치가 없는 그래프의 인접리스트 표현

 

 

그림에서 1행에 연결되어있는 2와 4는 각각 ①→②, ①→④ 를 나타낸다.

①→②→④ 라는 표현이 아니다.

즉, 각 행은 시작 노드를, 각 행에 연결되어있는 리스트는 해당 시작 노드와 간선으로 연결되어있는 도착 노드 각각을 의미한다.

 

 

방향이 있는 그래프의 인접리스트 표현

 

방향이 있는 그래프의 경우 각 노드에서 출발하는 간선만 각 행에 연결시켜주면 된다.

따라서 출발하는 간선이 없는 노드는 리스트가 비어있게 된다.

 

 

가중치가 있는 그래프의 인접리스트 표현

 

가중치가 있는 그래프의 경우에는 간선 리스트에 연결되는 노드들이 (2, 1), (4, 3) 과 같이 (도착 노드, 가중치) 쌍으로 표현해주는 등 추가 작업이 필요하다.

 

 

아래는 간선 정보를 입력으로 받았을 때 인접 리스트로 표현하는 코드다.

인접행렬에서의 예와 마찬가지로 방향이 없는 그래프로 a와 b 시작점에 각각 b와 a노드를 리스트로 추가시켜줬다.

 

9 // 간선의 수 1 2 1 4 2 5 3 4 3 5 4 6 4 7 5 6 5 7

vector<int> adj[7];
int N, a, b;

cin >> N;

for (int i = 0; i < N; i++) {
	cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
}

 

 

장점

 

인접 리스트는 실제 존재하는 간선의 수 만큼만 정보를 저장한다.

즉, 간선이 연결되지 않은 노드 사이 관계를 저장할 공간이 필요하지 않고 탐색해서 확인할 필요가 없다.

바로 인접행렬의 단점들을 극복하는 표현 방법이다.

 

 

메모리 공간을 낭비하지 않기 때문에 최대 노드 수와 무관하게 간선 수 만큼의 메모리만 요구한다.

메모리 초과가 발생하지 않는다.

 

 

모든 노드를 탐색할 때 노드 수 만큼 방문이 필요하지 않고 역시 간선 수 만큼만 탐색하기 때문에 굳이 반복 방문하지 않는 이상 시간 초과를 극복할 수 있다.

①에 연결된 노드들을 너비 우선으로 탐색할 경우 [1][2], [1][3], [1][4], [1][5], [1][6], [1][7]을 모두 확인해서 간선이 있는지 판단하는 것이 아니라 adj[1]에 연결된 리스트를 따라서 ②, ④ 만 방문시키면 된다.

즉, 간선의 수 E번만으로 그래프 전체를 탐색할 수 있다.

 

 

각 노드에 연결된 간선의 수를 구할 때에도 해당 행에 연결된 리스트의 크기만으로 확인할 수 있다.

다른 모든 노드와 간선 여부를 확인해 카운트 해주지 않아도 된다.

 

 

단점

 

만약 a, b 두 노드가 간선으로 연결되어있는지 확인하고자 한다면 어떻게 해야할까?

인접행렬을 사용한다면 단순히 adj[a][b] 로 배열 요소의 값을 확인하는 것으로 한번만에 확인할 수 있다.

인접리스트에서는 이를 위해 adj[a] 행에 연결된 리스트를 모두 확인해야 한다.

 

 

인접 행렬에 비해 구현이 다소 번거롭거나 어려울 수 있다는 점도 단점이다.

물론 대부분의 언어에서는 Library를 통해 리스트나 리스트를 대신할 자료구조를 제공하기 때문에 구현 난이도 차이가 크다고 할 수 없다.

 

 

하지만 만약 C언어를 사용한다면 불필요한 리스트 형태를 구현하느라 문제풀이 시간이 크게 늘어날 수 있다.

C언어에서는 지겨우면서 실수도 자주 발생하는 Linked List 구조를 직접 구현해 넣어야 한다.

당연히 차라리 C++이나 그외 다른 언어를 사용하는 것만으로 이 단점은 쉽게 극복할 수 있다.