그래프

흐름을 표현하는 방향성

간선은 방향을 가질 수도, 없을 수도 있습니다. 방향이 있는 간선을 포함하면 방향 그래프, 방향이 없는 간선을 포함하면 무방향 그래프라고 합니다.

이때 방향 그래프는 한쪽만 가리키는 것이 아닌 서로 반대를 가리키는 간선이 있을 수도 있습니다.

흐름의 정도를 표현하는 가중치

두 번째 특성은 가중치입니다. 가중치는 흐름의 방향 뿐만 아니라 양도 중요할 수 있습니다. 이런 가중치가 있는 그래프를 가중치 그래프(weighted graph)라고 합니다.

시작과 끝의 연결 여부를 보는 순환

순환이 존재하는 그래프를 순환 그래프라고 하고, 순환이 존재하지 않는 그래프를 비순환 그래프라고 합니다.

인접 행렬 그래프 표현

2차원 배열을 활용하여 구현하는 경우가 많습니다. 이때 배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고, 인덱스의 세로 방향을 출발 노드, 가로 방향을 도착 노드로 생각하면 자연스럽게 노드로 표현할 수 있습니다.

인접 리스트 그래프 표현

인접 리스트 그래프 표현 방식은 다음과 같은 과정으로 동작합니다.

1. 우선은 노드 개수만큼 배열을 준비합니다.

2. 배열의 인덱스는 각 시작 노드를 의미하며 배열의 값에는 다음 노드를 연결합니다.

인접 행렬과 인접 리스트의 장단점

두 방식으로 그래프를 표현할 때 어느 한쪽이 매우 뛰어나거나 하지 않습니다. 모두 장단점이 있습니다.

인접 행렬의 장단점

인접 행렬은 크게 두 가지의 단점이 있습니다. 인접 행렬로 희소 그래프를 표현하는 경우 인접 행렬은 크기가 고정되어 최악의 경우를 고려해서 크기를 결정해야 합니다. 따라서 노드가 N개 있을 때 N x N 크기의 인접 행렬이 필요합니다.

인접 행렬의 장점은 간선의 정보를 확인할 때의 시간 복잡도가 로 가장 좋습니다. 인접 행렬에서는 인덱스 임의 접근을 통해 노드 간 간선 정보를 바로 확인할 수 있기 때문입니다.

인접 리스트의 장단점 인접 리스트는 인접 행렬과 정반대의 장단점을 가집니다. 인접 리스트는 실제 연결된 노드에 대해서만 노드의 값을 담아 연결하기만 하면 됩니다. 때문에 모든 노드가 연결되어 있을 경우 효율이 떨어질 수 있습니다. 하지만 그런 경우는 굉장히 드뭅니다. 보통은 인접 리스트를 활용하면 메모리를 아낄 수 있습니다. 특정 노드를 검색할 때 탐색 시간이 입니다.

깊이 탐색한 다음 되돌아오는 깊이 우선 탐색

가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문 노드부터 다시 탐색을 진행한다는 특징이 있어서 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우 활용할 수 있습니다.

최단 경로를 찾는 문제가 아니라면 깊이 우선 탐색을 우선 고려해보는 것이 좋습니다.

최단 경로를 보장하는 너비 우선 탐색

너비 우선 탐색은 찾은 노드가 시작 노드로부터 최단 경로임을 보장합니다. 왜냐하면 가까운 간선을 통해 모든 노드를 방문하기 때문입니다.

가장 가까운 답을 찾는 문제라면 너비 우선 탐색으로 구현하면 됩니다.

왜 정점 개수 -1만큼 반복하는가? 매연산마다 최단 경로가 1개씩 확정되므로!

왜 한 번 더 연산을 반복하는가? 음의 순환을 찾기 위해!

음의 순환에 빠지는 건 벨만-포드 알고리즘의 한계다?

모든 알고리즘은 음의 순환이 있다면 어떤 알고리즘도 최단 경로를 구할 수 없습니다.