알고리즘 - 그래프

그래프

그래프는 노드와 엣지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 엣지는 노드를 연결한다.

엣지 리스트

엣지를 중심으로 그래프를 표현한다. 배열에 출발 노드, 도착 노드를 저장하여 엣지를 표현하는데 여기에 가중치를 표함하는 경우도 있다.

1. 엣지 리스트로 가중치가 없는 그래프 표현

가중치가 없다면 출발 노드와 도착 노드만 표현하니까 배열의 행은 2개면 충분하다.

[1,2]
[1,3]
[3,4]
[2,4]
[2,5]
[4,5]

1 -> 2 로 나가는 엣지를 [1,2] 로 표현한다. 이렇게 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다.
노드를 배열에 저장하여 엣지를 표현하니까 엣지 리스트라고 부른다.
(방향이 없는 그래프라면 [1,2]와 [2,1]은 같은 표현이 될 수 있다.)

1. 엣지 리스트로 가중치가 있는 그래프 표현

가중치가 있으면 행을 3개로 늘려서 3번째 행에 가중치를 저장하면 된다.

[1,2,8],
[1,3,3],
[3,4,13],
[2,4,4],
[2,5,15],
[4,5,2]

1 -> 2 로 나가는 엣지의 가중치는 8이라서 [1,2,8] 로 표현한다. 엣지 리스트 자체는 구현하기 쉽지만 특정 노드와 관련된 엣지를 탐색하기에 쉽지 않다.
엣지 리스튼 보통 벨만 포드나 크루스칼(MST) 알고리즘에서 사용되며 노드 중심 알고리즘에선 잘 안쓰인다.

인접 행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
인접행렬은 엣지 리스트와 다르게 노드 중심으로 그래프를 표현한다.

1. 인접 행렬로 가중치가 없는 그래프 표현

[0,1,1,0,0],
[0,0,0,1,1],
[0,0,0,1,0],
[0,0,0,0,1],
[0,0,0,0,0]

1 -> 2 로 향하는 엣지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.
가중치가 없어서 1을 저장하며 엣지가 있다는 표시를 노드 중심으로 한다고 이해하면 편하다.

2. 인접 행렬로 가중치가 있는 그래프 표현
   가중치가 없을때 1로 저장하던 2차원 배열에 가중치에 따른 값을 저장하면 된다.

[0,8,3,0,0],
[0,0,0,4,15],
[0,0,0,13,0],
[0,0,0,0,2],
[0,0,0,0,0]

인접 행렬을 이용한 그래프 구현은 쉽다. 두 노드를 연결하는 엣지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 장점이 있다.
하지만 노드와 관련된 엣지를 탐색하려면 N번 접근해야하므로 노드 갯수에 비해 엣지가 적을 때는 공간 효율성이 떨어진다.

또한 노드 갯수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다. 예를 들어 노드가 3만개가 넘어가면 자바에서 힙스페이스 에러가 발생한다.
인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력도 필요하다.

인접 리스트

ArrayList로 그래프를 표현한다. 노드 갯수만큼 ArrayList를 선언하는데 자료형은 경우에 맞게 사용한다.

1. 인접 리스트로 가중치 없는 그래프 표현
   N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 갯수만큼 배열을 연결하는 방식으로 표현

// ArrayList<Integer>[5] 로 선언

list[0] = [2,3];
list[1] = [4,5];
list[2] = [4];
list[3] = [5];
list[4]

노드1과 연결된 2,3 녿드는 ArrayList[1]에 [2,3]을 연결하는 방식으로 표현한다.

2. 인접 리스트로 가중치가 있는 그래프 표현
   가중치가 있을 경우 자료형을 클래스로 사용한다. 예를 들어 (도착노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용한다.

list[0] = [[2,8],[3,3]];
list[1] = [[4,4],[5,15]];
list[2] = [[4,13]];
list[3] = [[5,2]];
list[4]

ArrayList[1]에 [(2,8), (3,3)] 이 연결되어 있다. 이는 노드1과 가중치8 엣지로 노드 1과 3이 가중치 3 엣지로 연결되어 있다는 걸 보여주고 방향성도 알수 있다.
인접 리스트를 이용한 그래프 구현은 다른 방법들에 비해 복잡한 편이지만
노드와 연결되어 있는 엣지를 탐색하는 시간은 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.
그래서 많은 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.