그래프 저장

프로그래밍 문제에서는 대개 그래프의 정점에 $0$부터 $(n-1)$까지 번호를 매기는데, 이는 정점을 여러 배열의 인덱스로 편리하게 사용하기 위해서입니다.

문제에서 그래프는 대개 입력에서 읽어 들여야 하는 모든 간선의 목록으로 주어집니다. 그래프는 어떤 형식으로 저장하는 것이 최적입니까? 문제에 따라 여러 가지 방법이 있습니다.

#간선 리스트

때로는 입력으로 주어지는 간선 목록을 그대로 저장하는 것만으로 충분합니다. 그러나 이러한 방식은 특정 연산에서 비효율적인 경우가 많습니다.

예를 들어 정점 $a$와 $b$ 사이에 간선이 존재하는지 확인하려면, 단순한 방법으로는 그러한 간선을 찾기 위해 목록 전체를 훑어보아야 합니다.

이를 피하기 위해 이 리스트에 어떤 구조를 부여할 수 있습니다. 예를 들어, 리스트를 먼저 첫 번째 원소 기준으로, 그다음 두 번째 원소 기준으로 정렬하면 $O(\log m)$에 이진 탐색으로 확인을 수행할 수 있습니다. 더 나아가 리스트를 어떤 자료 구조, 예를 들어 이진 트리나, 더 좋게는 해시 테이블로 감쌀 수도 있지만, 어느 경우든 몇 가지 비효율이 생깁니다.

#인접 행렬

인접 행렬이란 크기가 $n \times n$인 2차원 행렬 $G$로, 간선 $(i, j)$가 존재하면 셀 $G_{ij}$에 1을, 그렇지 않으면 0을 저장하는 행렬입니다.

구현할 때는 보통 bool 타입의 일반적인 2차원 배열을 만듭니다. $n$개의 정점 각각에 대해 나머지 모든 정점으로 가는 간선이 존재하는지에 대한 정보를 저장한다면, 총 $n^2$개의 칸을 저장하게 되므로 메모리 점근 복잡도는 $O(n^2)$입니다.

중복 간선이 있는 그래프의 경우, 인접 행렬에 0과 1 대신 해당 간선의 중복도를 저장하기도 합니다.

단순 무향 그래프의 경우 인접 행렬은 대칭이며 주대각선의 원소가 모두 0이라는 점에 주목하십시오.

인접 행렬은 확인 작업에 매우 효율적입니다. 셀 하나만 읽어서 비교하면 됩니다. 그런데 주어진 정점 $v$의 모든 이웃을 빠르게 순회하고 싶다면 어떻게 해야 합니까? 이 경우에는 $O(n)$보다 빠르게 할 수 없습니다.

#인접 리스트

이제 $n$개의 각 정점마다 불리언 배열 대신 그 정점과 인접한 모든 정점의 번호를 저장해 봅시다. 이를 위해서는 아무 동적 자료구조나 필요한데, 예를 들어 C++의 std::vector를 사용할 수 있습니다.

// если на вход идет матрица смежности
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i){
    for (int j = 0;j < n;++j){
        cin >> a;
        if (a)
          g[i].push_back(j);
    }
}

// если на вход идет список ребер
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i){
  cin >> v1 >> v2;
  g[v1].push_back(v2);
  g[v2].push_back(v1);
}

여기서 메모리와 입력 시간에 대한 점근적 복잡도는 $O(n + m)$입니다. 총 $2m$개의 간선과 $n$개의 벡터를 저장하기 때문입니다.

간선이 많은 밀집 그래프는 인접 행렬로 저장하는 것이 좋고, 간선이 적은 희소 그래프는 인접 리스트로 저장하는 것이 더 효율적입니다.