[그래프 알고리즘]그래프의 표현

그래프란

그래프란 유한개의 노드와 노드들을 연결하는 유한개의 엣지들로 이루어진 자료구조

현실 세상의 많은 것들을 그래프로 추상화하여 표현이 가능하다.

예) 지하철, 컴퓨터 네트워크, 인스타그램에서 사람들간의 팔로우

노드

그래프를 구성하는 기본 원소로 다른 노드들과 관계를 맺는다.

지하철의 역, 컴퓨터 네트워크에서의 컴퓨터, SNS에서의 계정이 그래프에서의 노드로 추상화될 수 있다.

엣지

다른 노드들간의 관계를 표현한 것으로 최소 노드 1개이상이 존재해야 엣지도 존재할 수 있다.

(자기 자신으로의 엣지)

노드 u와 노드 v 사이의 연결은 (u, v)로 표현한다.

주의할 점은 방향 그래프에서는 엣지는 방향을 가진다는 것이다.

따라서 방향 그래프에서는 (u, v)와 (v, u)는 같지 않다.

인접 행렬 Adjacency Matrix

그래프를 구체적으로 구현할 때 한 방법으로, 노드들간의 관계를 행렬로 표현한 것이다.

총 N개의 노드들이 있다면, NxN 크기의 행렬 M을 준비한다.

모든 노드에 1부터 N까지의 숫자를 부여한다.

노드 i와 노드 j 사이에 엣지 (i, j)가 있다면, 행렬 M의 i행 j열에 값이 있음을 표시한다.

무향 그래프라면 노드 i와 노드 j사이의 엣지를 i행 j열과 j행 i열 모두 표시해야 할 것이다.

 

C++에서 인접 행렬을 구현한다면 2차원 배열로 가능하다.

장점 : 노드 u와 노드 v 사이에 엣지가 있는지 바로 확인할 수 있다.

단점 : 고정적으로 NxN크기의 행렬을 저장해야 하므로 N이 큰 경우에 많은 메모리가 필요하다.

엣지가 많이 없는 희소 그래프인 경우에는 상대적으로 메모리의 낭비가 심하다.

인접 리스트 Adjacency List

한 노드가 다른 노드들과 연결 되어 있는지를 리스트로 표현한 것으로,

한 노드는 자기와 연결된 노드들을 리스트로 갖는다.

N개의 노드가 있다면, 총 N개의 리스트가 존재한다.

노드들에게 번호를 부여하면, i번째 리스트에는 노드 i와 연결된 노드들의 번호가 저장된다.

 

C++에서는 인접 리스트를 vector로 쉽게 구현 가능하다.

장점 : 엣지가 많이 없는 희소그래프여도 메모리를 많이 요구하지 않는다.

단점 : 노드 u와 노드 v가 연결되어 있는지 확인하기 위해, 노드u의 인접 리스트를 순회하며 v가 있는지 확인해야 한다.

 

set을 이용하면 인접리스트의 단점을 완화할 수 있다.

set을 이용하면 노드 u와 노드 v가 연결되어있는지 확인하기 위해,

u 번째 set에서 logN 이하의 횟수로 노드 v가 있는지 알 수 있다.

set자료구조에 들어가야하는 데이터는 순서비교가 가능해야하므로, 노드를 숫자로 표현한 경우는 적절하다고 할 수 있다.