[그래프] 인접 행렬과 인접 리스트

그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후에 푸는 것이 보편적입니다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다.

1. 인접 행렬

2. 인접 리스트

1. 인접 행렬

1) 정의

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]^[각주:1]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다.

 

adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

cf) 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수 있습니다.

2) 예시

간단한 예시를 통해 이해해보도록 하겠습니다. 다음과 같은 그래프가 있는 경우, 이 그래프의 연결 관계를 인접 행렬로 나타낸다면 인접 행렬은 다음과 같을 것입니다.

그렇다면, 위의 그래프처럼 간선에 방향이 있는 유향 그래프가 아닌, 간선에 방향이 없는 무향 그래프의 경우에는 어떻게 될까요?

노드 i에서 노드 j로 가는 간선이 있다는 말은 노드 j에서 노드 i로 가는 간선도 존재한다는 의미가 되겠죠? 따라서, 인접 행렬이 대각 성분(adj[i][j]에서 i와 j가 같은 원소들)을 기준으로 대칭인 성질을 갖게 됩니다. 위의 그래프의 간선들을 방향이 없는 간선으로 바꿔주면 아래와 같은 인접행렬을 갖게 됩니다.

3) 장단점

인접 행렬의 장점은 구현이 쉽다는 점입니다. 

그리고, 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 O(1)이라는 시간 복잡도에 확인할 수 있다는 점이 있습니다. 

하지만, 치명적인 단점 또한 존재합니다. 전체 노드의 개수를 V개, 간선의 개수를 E개라고 해봅시다. 노드 i에 연결된 모든 노드들에 방문해보고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해보아야 하기 때문에 총 O(V)의 시간이 걸린다는 점입니다. 위의 그래프와 같은 경우 큰 차이가 느껴지지 않을 수도 있지만, 노드의 개수에 비해 간선의 개수가 훨씬 적은 그래프라면 이야기가 달라질 것입니다. 만약, 노드의 개수는 총 1억개인데 각 노드마다 연결된 간선이 많아봤자 2개인 그래프가 있다고 해봅시다. 그렇다면, 특정 노드와 연결된 노드들이 몇 번 노드인지 확인하기 위해 총 1억 개의 노드들을 모두 확인해봐야 하는 치명적인 문제가 발생하게 됩니다. 정작 연결된 노드는 많아봤자 2개 뿐일텐데 말입니다. (이러한 단점을 보완할 수 있는 연결 관계 표현 방식이 인접 리스트입니다.)

4) 구현

문제를 풀 때엔 그래프에 대한 정보가 

① 노드의 개수

② 간선의 개수

③ 각 간선의 양끝 노드

의 순서로 주어지게 됩니다. 위의 무향 그래프를 입력으로 주고 싶다면, 문제에선 어떤 식으로 정보를 제공하게 될까요?

4 

5

1 2

1 3

1 4

2 3

3 4

다음과 같이 제공하게 되겠죠?? 그렇다면 이를 인접행렬로 저장하기 위해선, 어떻게 코드를 작성해야 할까요? 

노드의 개수와 간선의 개수를 입력받은 후, 간선의 개수만큼 for문을 돌면서 양끝 노드를 입력받으면 될 것입니다. 자세한 구현은 아래와 같습니다.

#include <iostream>
 
using namespace std;
 
int node, edge;
int adj[100][100];
 
int main()
{
    cin >> node >> edge;
 
    for(int i = 0; i < edge; i++)
    {
        int a, b; cin >> a >> b;
 
        adj[a][b] = 1;
        //무향 그래프이기 때문에
        //노드 a에서 노드 b로 가는 간선이 존재한다면
        //노드 b에서 노드 a로 가는 간선도 존재한다고 생각할 수 있음
        adj[b][a] = 1;
    }
}

2. 인접 리스트

인접 리스트를 구현하기 위해서는 STL의 vector를 사용하는 것이 편합니다. 아직 사용법을 모르신다면, 간단한 사용법을 익혀두는 것이 좋습니다. (vector 사용법 : http://sarah950716.tistory.com/4)

1) 정의

인접 리스트는 그래프의 연결 관계를 vector의 배열(vector<int> adj[])로 나타내는 방식입니다. 이 때, vector<int>에는 노드의 번호가 직접 저장됩니다. 인접 리스트는 adj[i](vector의 배열이기 때문에, adj[i]는 vector가 되겠죠?)를 다음과 같이 정의할 수 있습니다.

adj[i] : 노드 i에 연결된 노드들을 원소로 갖는 vector

cf) 만약 간선에 가중치가 있다면, pair<int,int> adj[]를 통해 구현할 수 있습니다. 

    pair<int,int>의 first에는 노드의 번호, second에는 간선의 가중치를 저장하는 방식으로 저장해주면 됩니다.

2) 예시

이번에도 역시 간단한 예시를 통해 이해해보도록 하겠습니다. 

위의 그림에서 편의상, 벡터를 링크드 리스트와 같은 형태로 나타내었고 (vector는 push_back을 통해 뒤에 원소를 계속 붙일 수 있기 때문에 링크드 리스트의  형태와 비슷하다고 생각하면 편하기 때문) , 보기 좋도록 adj[]를 세워서 나타냈습니다. 왼쪽의 그래프를 보면, 노드 1과 연결된 노드는 노드 2, 3, 4. 총 세 개가 있습니다. 따라서, adj[1]의 vector는 총 세 개의 성분을 갖게 됩니다. 각각의 성분에 접근하기 위해선 이차원 배열과 같은 방식을 이용하면 됩니다. (adj[1][0] = 2, adj[1][1] = 3, adj[1][2] = 4, adj[2][0] = 3) 

cf ) 오른쪽의 인접 리스트에서, adj[1]에 있는 세 노드의 순서는 의미가 없습니다. 2,3,4 순이 아닌 3,2,4 순이 되어도 무관하지만, 보기 좋도록 하기 위해 오름차순으로 저장해 놓은 것을 뿐입니다. 따라서, adj[1]의 노드 2와 노드 3사이에 화살표가 있는 것을 노드 2와 노드 3사이에 간선이 있다는 의미가 아니라 단순히, vector에 노드 3이 노드 2보다 나중에 push_back 되었기 때문이라고 이해하면 됩니다.

그렇다면, 간선에 방향이 없는 무향 그래프의 경우 인접 리스트가 어떻게 될까요?

그림으로 간단하게 이해하고 넘어가도록 하겠습니다.

 

3) 장단점

그렇다면, 인접 리스트로 그래프의 연결 관계를 저장할 때의 장점은 무엇일까요? 인접 리스트는 인접 행렬과 달리, 실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 모든 벡터들의 원소의 개수의 합이 간선의 개수와 같다는 점이 있습니다. 즉, 간선의 개수에 비례하는 메모리만 차지한다고 할 수 있겠죠? 위의 그림만 봐도 이러한 점을 확인할 수 있습니다. 그래프에 5개의 간선이 존재하고, 따라서 인접 리스트 상에 저장된 원소도 5개인 것을 확인할 수 있습니다.

만약, 노드 2와 연결된 모든 노드들을 방문해보고 싶다면, 인접 행렬의 경우 adj[2][1], adj[2][2], adj[2][3], adj[2][4]. 총 4번을 확인해보아야 하지만, 인접 리스트의 경우 실제 연결된 노드들만 확인해 볼 수 있기 때문에 adj[2][0] 부터 adj[2][adj[2].size()-1] 까지 총 1번만 확인해보면 됩니다. 

이를 전체 노드에 대한 탐색을 수행하는 상황으로 확장해서 생각해보도록 하겠습니다. 노드가 V개, 간선이 E개라고 해봅시다. 인접 행렬의 경우,  각 노드에 연결된 노드를 방문해보기 위해서 모든 노드에 대해 확인해보아야 하기 때문에 총 O(V*V)의 시간이 걸릴 것입니다. 하지만, 인접 리스트의 경우에는 각 노드마다 연결된 노드만 확인하는 것이 가능하기 때문에, 전체 간선의 개수만큼만 확인해 볼 수가 있습니다. 따라서, O(E)의 시간복잡도를 가진다고 할 수 있겠죠? 이렇게 각 노드에 연결된 모든 노드들을 방문해 보아야 하는 경우, 인접 리스트로 연결 관계를 저장하는 것이 시간상 큰 이점을 가진다고 할 수 있습니다. 

하지만, 인접 리스트에도 치명적인 단점이 존재합니다. 노드 i와 노드 j가 연결되어 있는지 알고 싶다면 어떻게 해야 할까요? adj[i]의 벡터 전체를 돌며, j를 성분으로 갖는지 확인해보아야 하겠죠? 따라서, 시간 복잡도는 O(V)가 될 것입니다. 위에서 언급했듯이, 인접 행렬의 경우 adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 O(1)의 시간 복잡도를 갖게 되지만 말입니다. 이러한 단점이 있기 때문에, 문제의 상황에 따라 적절한 표현 방식을 이용해서 연결 관계를 저장하는 것이 중요하다고 할 수 있습니다.

4) 구현

간선에 가중치가 없는 무향 그래프를 인접 리스트로 저장하는 방식을 구현하는 코드를 통해, 그래프의 연결 관계 저장 방법에 대한 공부를 마무리 하도록 하겠습니다.

#include <iostream>
 
using namespace std;
 
int node, edge;
vector<int> adj[100];
 
int main()
{
    cin >> node >> edge;
 
    for(int i = 0; i < edge; i++)
    {
        int a, b; cin >> a >> b;
 
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    //노드 1과 연결된 모든 노드들의 번호를 출력하고 싶은 경우
    for(int i = 0; i < adj[1].size(); i++)
        cout << adj[1][i] << '\n';
}

+예시)

간선에 가중치가 있는 그래프를 인접리스트로 나타내는 경우, vector<pair<int,int>>의 배열로 구현하게 됩니다.

adj[a][0].first = b, adj[a][0].second = c 라고 하면,

시점이 노드 a, 종점이 노드 b, 가중치가 c인 간선이 존재한다는 것을 의미합니다.

1. 인접 행렬을 영어로 하면 adjacent matrix이기 때문에 주로 adj[][]라고 변수명을 줄여 말합니다. [본문으로]