9. Graph

Graph란?

그래프는 정점(vertex)들과 정점들을 잇는 간선(edge)으로 이루어진 자료구조이다.

예를 들어 위와 같은 그래프는 5개의 정점과 6개의 간선으로 이루어진 그래프이다.

그렇다면 이렇게 정점과 간선의 정보를 어떻게 저장해야 할까.

그래프는 크게 인접 리스트(Adjacency List) 형태나 인접 행렬(Adjacency Matrix) 형태로 구현된다.

인접 리스트는 각각의 정점마다 리스트를 할당하고,

해당 정점과 연결된 정점을 리스트에 저장함으로써 간선 정보를 저장한다.

인접 리스트를 사용할 경우 간선의 갯수만큼만 공간을 할당하여 메모리를 절약할 수 있으나,

연결되어 있지 않은 정점 두개의 연결 여부를 확인하려면 정점의 모든 간선을 찾아봐야 한다는 단점이 있다.

인접 행렬은 (정점 갯수+1)×(정점 갯수+1) 크기의 2차원 배열을 만들고, 각각의 index를 정점 번호로 생각했을 때,

정점끼리 연결되어 있다면 1, 연결되어 있지 않다면 0으로 채워 간선 정보를 저장한다.

인접 행렬은 두 정점의 연결 여부를 확인할 때 바로 배열에 접근하여 확인할 수 있지만,

인접 리스트가 간선 갯수 만큼의 저장 공간이 필요한 반면 인접 행렬은 정점^2 만큼의 저장 공간이 필요하다.

또한, 연결된 모든 노드를 찾으려면 정점 갯수 만큼의 시간이 필요하다는 단점이 있다.