그래프의 간선 리스트 표현

그래프를 처음 배울 때, 그래프의 두 가지 표현 방법을 배운다. 인접 행렬과 인접 리스트. 인접 행렬은 $V^2$개의 원소를 가진 2차원 배열로, 인접 리스트는 $V$개의 연결 리스트(또는 흔히 동적 배열)로 그래프를 표현한다. 다른 표현 방식 하나인 간선 리스트는 그 두 가지를 조합한 방법이다.

인접 리스트(간선 리스트 이야기가 아니다.)는 각 정점에 대해 그 정점에서 시작하는 간선을 리스트로 나타낸 표현 방식이다. 대부분의 대형 그래프에서 인접 리스트 표현을 사용하면 편리하지만 느낄 수 있는 단점이 몇 가지 있다.

1. 동적 배열(vector) 기반이라 느리다. 극히 드물지만, 인접 리스트로는 시간 초과가 나는 문제도 있다.

2. 간선에 번호를 붙일 때 굉장히 불편하다. 다른 말로는, 간선을 순회하기 힘들다.

물론 모두 적절한 구현으로 해결할 수 있는 문제이다. 하지만 이들을 모두 복잡한 아이디어를 요구하지 않고 해결할 수 있는 배열의 표현 방법이 간선 리스트이다.

먼저, 약간 원시적인 아이디어를 위해 간선 배열을 생각해보자. 내가 임의로 이름지은 이 방법은 그냥 간선을 배열로 저장하고 있는 것이다. 

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pint;
#define x first
#define y second
 
const int maxv = 100000, maxe = 200000;
pint edge[maxe]; // 각 간선은 (x, y)를 잇고 있음.
int st[maxv]; // 간선을 정렬한 후, 각 점에서 시작하는 간선의 첫 인덱스
int v, e;
 
int main() {
    // Input
    cin >> v >> e;
    for (int i=1; i<=e; i++)
        cin >> edge[i].x >> edge[i].y;
 
    // Processing
    sort(edge+1, edge+e+1);
    st[v+1] = e+1;
    for (int i=1, k=1; i<=e; i++)
        while (edge[i].x >= k) st[k++] = i;
 
    // Output
    for (int i=1; i<=v; i++)
        for (int j=st[i]; j<st[i+1]; j++)
            cout << i << " and " << edge[j].y << " are connected.\n";
}
 

간선을 시작점(그리고 시작점이 같으면 끝점) 순서대로 정렬해놓고, 각 정점에서 시작하는 간선을 찾기 위해 $st$ 배열을 구축했다. $st[i]$번 간선부터 $st[i+1] - 1$ 번 간선까지는 정점 $i$에서 시작한다. 단방향 간선이라 가정했음에 유의하고, 양방향이면 단지 반대 방향 간선을 같이 추가해 주면 된다.

이 방법을 사용하면 위에서 지적했던 인접 리스트의 단점인 간선을 순회(이터레이팅)하기 불편하다는 단점을 보완할 수 있다. 물론, 동적 배열 기반이 아니라 조금 더 빨라졌을 것이다. (2배 정도 빠르다고 한다)

위 방법의 시간 복잡도는 $O(ElogE)$이다. 하지만 이 과정을 $O(E)$에 할 수 있는 방법이 있다. 이 방법을 쓰면 간선 배열보다는 2배, 인접 리스트보다는 4배 빨라진다고 한다. 그 방법이 간선 리스트이다.

간선 리스트를 구현한 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxv = 100000, maxe = 200000;
int a[maxe], b[maxe], nxt[maxe], st[maxv], p = 2;
void add(int x, int y) {
    a[np] = x; b[np] = y; nxt[np] = st[x]; st[x] = p++;
}
int v, e;
 
int main() {
    cin >> v >> e;
    for (int i=1; i<=e; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    
    for (int i=1; i<=v; i++)
        for (int j=st[i]; j; j=nxt[j])
            cout << a[j] << " and " << b[j] << " are connected.\n";
}
 

코드 자체는 인접 리스트만큼이나 간결한 것을 확인할 수 있다. 이 방법은 이전의 인접 배열 방법에서 배열을 연결 리스트로 바꾼 것일 뿐이다. 각 정점은 자신과 연결된 간선들을 저장하는 연결 리스트를 하나씩 가지고 있는데(이 연결 리스트들은 하나의 배열 안에 모두 들어있다.), 이 연결 리스트는 다음 원소의 포인터가 아닌, 다음 원소의 '배열에서의 인덱스'를 가리키고 있다.

간선 리스트라는 하나의 자료구조는 1. 간선들을 저장하는 배열과 2. 각 정점에서 연결되는 간선들을 저장하는 연결 리스트들로 이루어져 있다.

1. $a$와 $b$ 배열은 이전에 보았던 pair의 배열인 $edge$와 정확히 같은 역할을 한다. 다만, 절대 정렬될 일이 없다.

2. $st$ 배열은 각 정점이 가지고 있는 연결 리스트의 시작 인덱스(배열에서 첫 간선의 인덱스)이 들어있다. $con$ 배열은 연결 리스트의 각 원소가 가리키는 다음 원소를 담고 있다. 0은, 다음 원소가 없다는 뜻이다. 어떤 정점 $i$에 대해 어떤 간선도 연결되어 있지 않다면, 즉 이 정점의 연결 리스트가 비어 있다면 $st[i]=0$일 것이다. 새로운 간선의 추가는, 연결 리스트의 시작점에 수행한다. 새로운 간선이 맨 앞에 추가되는 셈이므로, 입력의 역순으로 순회하게 되는 셈이다. $add$ 함수의 뒷 두 문장이 이를 나타내고 있다.

이 방법은, 앞서 말한 $O(E \log E)$의 방법과 달리 선형 시간 $O(E)$에 작동한다. 상수도 작다. 그래프가 정점, 간선 두 가지 요소로 분리되어 있으므로 생각이 훨씬 유연해진다. 다음은 weight 인자를 추가한(즉 weighted graph인) 그래프를 표현한 코드이다.

#include <iostream>
using namespace std;
 
const int maxv = 100000, maxe = 200000;
int a[maxe], b[maxe], w[maxe], nxt[maxe], st[maxv], p = 2;
void add(int x, int y, int wt) {
    a[np] = x; b[np] = y; w[np] = wt; nxt[np] = st[x]; st[x] = p++;
}
int v, e;
 
int main() {
    cin >> v >> e;
    for (int i=1; i<=e; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        add(x, y, w);
    }
 
    for (int i=1; i<=v; i++)
        for (int j=st[i]; j; j=nxt[j])
            cout << a[j] << " and " << b[j] << " are connected in weight " << w[j] << ".\n";
}
 

실제로 유량 알고리즘에서는 역간선을 쉽게 구해야 하는데, 간선과 역간선을 리스트의 인접한 인덱스에 넣어두면 쉽게 역간선에 접근할 수 있기 때문에 매우 편하다. 위 구현체에서는 $i$번 간선의 역간선은 $i \mbox{xor} 1$번 간선이다(이렇게 무방향 그래프에서 홀짝성을 맞추려고 $p$의 초기값을 $1$이 아닌 $2$로 설정했다).

물론 간선의 순서를 적절히 섞어주어야 하는 상황에서는 간선 리스트를 쓰면 안 된다. 예를 들어 그래프를 간선 리스트에 넣고 크루스칼 알고리즘이라도 돌리려다가는 파국을 맞이하게 될 것이다.