Adjacency Matrix and Adjacency Lists

 

 

 

00. Introduction

 

알고리즘을 공부하다 보면, Graph를 대상으로 하는 알고리즘들이 있다. 이를 효율적으로 표현하기 위해서 보통 Adjacency Matrix와 Adjacency Lists를 사용하는데, 본 글에서는 어떤 식으로 각 representation을 만드며, 어떻게 사용되는지에 대해서 알아보도록 한다.

 

아 Graph는 undirected graph와 directed graph가 있으며, 다음과 같다. 말 그대로라 설명은 생략.

 

undirected graph

 

directed graph

 

아 Graph는 수식적으로 다음과 같이 표기한다.

 

G = (V, E)

- V: Vertex(정점)의 집합

- E: Edge(간선)의 집합

 

 

01. Basic Notion

 

개념 자체는 말 그대로이다. 그래프는 말그대로 "그래프" 형식이기 때문에 컴퓨터가 처리하기에 어려움이 있다. 따라서 특정 자료구조로 바꾸어 처리하곤 한다.

 

01-1. Adjacency List

 

Undirected/Directed Graph에서의 Adjacency List

 

Adjacency List는 각 vertex에 대해서 연결되어있는 node들이 정리되어있다.

한 가지 볼 점은 Undirected Graph와 Directed Graph 모두 순서는 크게 중요하지 않다. 즉 Undirected Graph 예제의 1번 list에서 2와 5의 순서는 바뀌어도 무관하다. 또한 Directed Graph의 4번 list에서 4와 3의 순서가 바뀌는 것 또한 상관없다.

 

• 공간 복잡도: O(|V|+|E|)

 

 

01-2. Adjacency Matrix

 

Adjacency Matrix는 Matrix 형태로 Graph의 상태를 나타내는 자료구조를 뜻한다. Adjacency List와 동일하게 Undirected/Directed 여부에 상관없이 사용할 수 있다.

 

특징이 있다면 undirected graph의 Adjacency Matrix는 symmetrical하다는 것이다 (i->j, j->i 모두 valid로 보기 때문)

 

 

• 공간 복잡도: O(V^2)

 

 

이제 이걸 써서 대표적으로 BFS랑 DFS를 하게 되는데,, 이건 글이 너무 길어지므로 다음 글에서 이어쓰도록 하겠읍니다