인접 행렬과 인접 리스트 cf. 그래프

그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후 푸는 것이 보편적이다.

이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있다.

👉 1. 인접 행렬 2. 인접 리스트

 

🟩 인접 행렬

그래프의 연결 관계를 이차원 배열로 나타내는 방식

인접 행렬을 adj[][]라고 한다면, adj[i][j]에 대해서 다음과 같이 정의 가능

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

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

 

🌟 예시

 

유향 그래프가 아닌 무향 그래프에서는, 노드 i 👉 노드 j 라는 말은, 노드 j  👉 노드 i라는 의미이다.

따라서, 인접 행렬이 대각성분(i=j인 원소들)을 기준으로 대칭인 성질을 갖게 된다.

 

 

🟩 장점

구현이 쉽다.

연결되어 있는지 확인하고  싶을 때, 1/0 확인만 하면 되기 때문에 O(1) 시간복잡도를 갖는다.

 

🟩 단점

전체 노드의 개수를 V, 간선의 개수를 E라고 하면, 노드 i에 연결된 모든 노드들에 방문해보고 싶은 경우, adj[i][1] ~ adj[i][V]를 모두 확인해보아야 하기 때문에 총 O(V)의 시간이 걸린다. 이는 노드의 개수에 비해 간선의 개수가 훨씬 적은 그래프라면 치명적이다. 만약, 노드의 개수가 총 1억개인데, 각 노드마다 연결된 간선이 많아봤자 2개인 그래프가 있다면, 특정 노드와 연결된 노드들이 몇 번 노드인지 확인하기 위해 총 1억 개의 노드들을 모두 확인해야 한다. 

👉 연결 리스트로 단점 보완 가능

 

🟩 구현

노드의 개수, 간선의 개수, 각 간선의 양끝 노드가 주어진다.

#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;
        // 무향 그래프라면
        adj[b][a] = 1;
    }
}

 

🟩 인접 리스트

STL의 vector를 사용하는 것이 편하다. vector의 배열 vector<int> ad[]로 나타내는 방식. 여기에는 노드의 번호가 직접 저장된다.

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

cf. 만약 간선에 가중치가 있다면 pair<int, int> adj[]를 통해 구현 가능하다.

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

 

🌟 예시

 

adj[1][0] = 2, adj[1][1] = 3, adj[1][2] = 4, adj[2][0] = 3

 

오른쪽 인접 리스트에서 adj[1]에 있는 세 노드의  순서는 의미가 없다. 보기 좋게 오름차순으로 표현한 것 뿐이다.

따라서 adj[1]의 노드2와 노드3 사이에 화살표가 있는 것을 노드2와 노드3 사이에 간선이 있는 것이 아닌, vector에 노드 3이 노드 2보다 나중에 push_back 되었다고 이해하면 된다.

 

무향그래프는 아래와 같다.

 

🟩 장점

실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 모든 벡터들의 원소의 개수의 합이 간선의 개수와 같다는 점

즉, 간선의 개수에 비례하는 메모리만 차지한다.

만약, 노드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)의 시간복잡도를 갖는다. 이러한 단점이 있기 때문에, 문제의 상황에 따라 적절한 표현 방식을 이용해서 연결 관계를 저장하는 것이 중요하다.

 

🟩 구현

#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';
    }
}

 

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

 

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

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