그래프를 구현하는 방법 - 인접 행렬, 인접 리스트

저번 포스트에서는 그래프에 대한 전반적인 개념을 살펴봤습니다.

그럼 그래프는 컴퓨터로 어떻게 구현할 수 있을까요?

 

그래프에서 가장 중요한 2가지 개념을 뽑는다면 정점과 간선이었습니다.

그럼 컴퓨터로 구현하려면, 정점과 간선의 관계를 나타내는 자료구조가 필요하겠네요!

바로 인접 행렬과 인접 리스트입니다.

 

일단 예시를 하나 들어보도록 하겠습니다. 

 

인접 행렬 ( adjacency matrix )

위의 예시는 아래의 표로 나타낼 수 있습니다. 

 

i / j	0	1	2	3
0	0	1	1	1
1	1	0	1	0
2	1	1	0	0
3	1	0	0	0

 

형식이 대략 이해가 가시나요? 

2차원 배열의 형식(행렬)로 표현을 했는데,

a[i][j] 는 i번 노드에서 j번 노드로 향하는 경로(간선)이 있는지를 알려줍니다.

 

예를 들어, a[0][1] == 1 이므로 0번에서 1번으로 향하는 간선은 존재하고, a[1][3]은 0 이므로 1번에서 3번으로 향하는 간선은 존재하지 않음을 의미합니다. 하나 더 해볼까요? a[1][2] 의 값은 1이므로, 1번에서 2번으로 향하는 간선이 존재한다는 의미입니다. 

 

참고로, 무방향 그래프의 경우 대칭 행렬이고 (a[i][j] == a[j][i] ), a[i][i] (혹은 a[j][j] )의 값은 자신에게 향하는 self-loop가 있지 않는 한 0입니다. 

 

이제, 코드로 표현해보면 다음과 같이 됩니다!

//위의 그림을 인접행렬로 표현할 경우
bool a[4][4] = {
    {0, 1, 1, 1},
    {1, 0, 1, 0},
    {1, 1, 0, 0},
    {1, 0, 0, 0},
};

//인접 행렬을 일반화 할 경우 - 참고로 V는 정점의 수를 의미함.
bool a[V][V]

for(int i = 0;i < V; i++){
    for(int j = 0; j < V; j++){
        if(a[i][j]){
            //출력하는 로직
            cout << i << "부터 " << j << "까지 경로가 있습니다.\n";
            // 해당 정점으로 부터 탐색하는 로직 - DFS 혹은 BFS를 사용하는 예시 (실제로는 더 다양한 알고리즘 사용 가능)
            BFS(i);
            DFS(i);
        }
    }
}

 

 

인접 리스트 ( adjacency list )

위의 예시는 아래의 리스트 형식으로도 나타낼 수 있습니다.

살짝 설명해보자면, 각 노드(0, 1, 2, 3)에 연결되어 있는 노드들을 linked list 형식으로 나타내는겁니다.

위의 그림을 보면, 0번 노드는 1번, 2번, 3번 노드와 연결되어 있고 1번 노드는 0번, 2번 노드와 연결되어 있으며 2번 노드는 0번, 1번 노드와 연결되어있고 3번 노드는 0번 노드와 연결되어 있음을 알 수 있네요.

 

이제 코드로 구현해봅시다 !

 #include<bits/stdc++.h>
 using namespace std;
 const int V = 4;
 vector<int> adj[V];
 int main(){
     adj[0].push_back(1);
     adj[0].push_back(2);
     adj[0].push_back(3);
     adj[1].push_back(0);
     adj[1].push_back(2);
     adj[2].push_back(0);
     adj[2].push_back(1);
     adj[3].push_back(0);
     
     //출력하는 방법 1
     for(int i = 0; i < 4; i++){
         cout << i << " :: ";
         for(int there : adj[i]){
             cout << there << " ";
         }
         cout << '\n';
     }
 
     //출력하는 방법2
     for(int i = 0; i < 4; i++){
         cout << i << " :: ";
         for(int j = 0; j < adj[i].size(); j++){
             cout << adj[i][j] << " ";
         }
         cout << '\n';
     }
}
 /*
 0 :: 1 2 3
 1 :: 0 2
 2 :: 0 1
 3 :: 0
 *

 

이 코드를 보면 2가지의 의문점이 생길 수도 있습니다.

1. 인접'리스트' 라면서 왜 vector를 사용했지?
2. vector<int> adj 가 아니라 vector<int> adj[V] 라고?

차근 차근 답변해보겠습니다.

 

첫 번째 의문에 답변을 드리자면, 사실 vector 가 아닌 list를 사용해도 됩니다 !

 // vector
 vector<int> adj[1004];
 // list
 list<int> adj[1004];

 

다만 vector를 사용한 이유는 list와 vector의 시간복잡도 차이 때문입니다. 

	n번째 인덱스에 삽입, 삭제	마지막 요소에 삽입, 삭제	특정요소 탐색	n번째 요소 탐색
vector	O(n)	O(1)	O(n)	O(1)
list	O(1)	O(1)	O(n)	O(n)

 

인접리스트로 로직을 구현할 때, 가장 많이 사용되는 연산은 마지막 요소에 삽입 & 해당 배열의 n번째 요소 탐색 입니다.

따라서 vector로 인접리스트를 구현하는 것이 더욱 효율적입니다.

 

 

두 번째 의문은 사실 간단합니다. vector<int> adj[V]  를 잘 해석해보면, 'int 자료형을 담는 벡터' 를 담는 adj 배열을 정의한겁니다. 그리고 그리고 노드 수(정점 수)만큼 벡터가 만들어지게 되는거고, 각각의 벡터가 linked list 역학을 하게 되는겁니다.

 

 

 

---

인접 행렬, 인접 리스트 응용하기

적응을 위해 2가지 문제를 풀어봅시다.

 

1.정점은 0번 부터9번까지 10개의 노드가 있다. 1- 2 / 1- 3 / 3-4라는경로가있다.(1번과2번, 1번과 3번, 3번과 4번은 연결되어있다.) 이를 인접행렬 표현하라. (혹은, 인접 리스트로 표현하라.)

 

2. 0번부터 방문 안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들어라.여기서 정점을 방문하고 다시 방문하지 않게 만들어야 한다.

 

인접 행렬로 풀어보기

#include <iostream>
using namespace std;

const int V = 10; //정점의 개수
bool a[V][V], visited[V];
void go(int from) {
	visited[from] = 1; //방문 처리
	cout << from << "\n";
	for (int i = 0; i < V; i++) {
		if (visited[i]) continue;
		if (a[from][i]) {
			go(i);
		}
	}

	//위의 반복문과 같은 기능을 하는 다른 코드 
	/*for (int i = 0; i < V; i++) {
		if (a[from][i] && !visited[i]) {
			go(i);
		}
	}*/
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	//인접 행렬 구성
	a[1][2] = 1; a[1][3] = 1; a[3][4] = 1;
	a[2][1] = 1; a[3][1] = 1; a[4][3] = 1;

	//모든 노드에서 돌려봄 - unconnected component 고려!
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			if (a[i][j] && visited[i] == 0) {
				go(i);
			}
		}
	}
	
	
	return 0;
}

 

 

인접 리스트로 풀어보기

#include <iostream>
#include <vector>
using namespace std;

const int V = 10; //정점의 개수
vector<int> adj[V];
int visited[V]; //bool로 정의해도 됨

//idx 라고 네이밍 짓긴 했지만, from이랑 같은 의미 
void go(int idx) {
	visited[idx] = 1; //방문 처리
	cout << idx << "\n";
	for (int there : adj[idx]) {
		if (visited[there]) continue;
		go(there);
	}	
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	//인접 리스트 구성 (사실 무방향 그래프라 양방향 간선처럼 연결해주는 것!
	adj[1].push_back(2);
	adj[2].push_back(1);

	adj[1].push_back(3);
	adj[3].push_back(1);

	//심화 - 만약 아래 2줄 주석화 하면, 1,2,3만 출력함 (4는 고립되어 있다고 판단)
	adj[3].push_back(4);
	adj[4].push_back(3);

	//모든 노드에서 돌려봄 - unconnected component 고려!
	for (int i = 0; i < V; i++) {
		if (adj[i].size() && visited[i] == 0) go(i);
	}
	
	
	return 0;
}

 

 

---

 

이제 마지막으로, 인접 행렬과 인접 리스트를 어느 기준으로 채택하면 좋을지 고민해봅시다.

간단하게 생각해보면, 메모리를 더 적게 쓰는건 인접 리스트이고, 접근 시간이 더 적은건 인접 행렬입니다.

따라서 Graph가 Sparse(드문 드문)할 때는 인접 리스트를, Dense(조밀)할 때는 인접 행렬을 사용하면 됩니다.

 

Tip! 코딩테스트 출제자는 대부분 sparse한 문제를 내니까, 인접 리스트를 주로 활용하시면 됩니다.

 

자세한 내용은 아래에서 확인하세요!

공간 복잡도 및 시간복잡도(모든 간선 찾으려고 할 때)

-인접행렬:O(V^2)

-인접리스트:O(V+E)

 

시간 복잡도 (하나의 특정한 간선 찾기)

-인접행렬:O(1)

-인접리스트:O(V)