그래프

그래프

노드와 관선을 이용한 비선형 데이터 구조

그래프는 주로 데이터 간의 관계를 표현하는 데 사용

그래프별 특징

방향성이 있는 그래프

간선의 방향은 서로를 가리킬 수도 있음

• 방향 그래프: 방향이 있는 간선을 포함한 그래프
• 무방향 그래프: 방향이 없는 간선을 포함한 그래프

가중치가 있는 그래프

• 가중 그래프: 가중치가 있는 그래프

순환하는 그래프

순환: 특정 노드에서 출발해 을 다시 같은 노드로 돌아올 수 있는 것

• 순환 그래프: 하나 이상의 순환이 존재하는 그래프
• 비순환 그래프: 어떠한 순환도 존재하지 않는 그래프

그래프 구현

그래프의 구현 방식에는 인접 행렬과 인접 리스트가 있다.

인접 행렬 그래프

• 2차원 배열을 사용해 노드 간 연결 관계를 표현
• N개의 노드가 있다면 N × N 크기의 행렬을 사용
• 간선의 정보를 O(1) 시간에 확인할 수 있음
• 노드 수에 비해 간선 수가 적은 희소 그래프인 경우, 사용하지 않는 공간이 많아 비효율적
• 노드 간 값의 차이가 큰 경우, 가장 큰 값을 기준으로 인접 행렬의 크기를 정해야 하므로 비효율적

인접 리스트 그래프

• 각 노드에 연결된 노드들을 리스트로 관리
• 실제 연결된 간선 정보만 저장하므로 메모리를 효율적으로 사용
• 간선의 정보 확인 시 연결한 리스트의 길이만큼 탐색하므로 O(N)

장단점 정리

노드 개수가 1,000개 미만으로 주어지는 경우 인접 행렬 사용 고려

그래프 탐색

깊이 우선 탐색

시작 노드에서 최대한 깊이 내려가면서 탐색하는 알고리즘
한 경로를 끝까지 탐색한 후 더 이상 갈 곳이 없으면 가장 마지막에 방문했던 노드로 돌아와 다른 경로를 탐색
DFS는 주로 스택이나 재귀 함수를 통해 구현

너비 우선 탐색

시작 노드의 인접한 노드들을 먼저 탐색한 후 다음 깊이로 진행하는 알고리즘
현재 위치에서 가장 가까운 노드들을 모두 방문하고 다음 레벨로 이동하여 탐색을 진행
BFS는 주로 큐를 통해 구현
너비 우선 탐색은 최단 경로를 보장

최단 경로

• 가중치가 없다면 간선의 수가 적은 경로
• 가중치가 있다면 가중치의 총합이 최소가 되는 경로

다익스트라 알고리즘

가중치가 있는 그래프의 최단 경로를 구하는 문제에 대부분 사용
최소 비용과 직전 노드를 저장할 공간 준비
방문하지 않은 노드 중 최소 비용이 가장 적은 노드를 선택
이후, 해당 노드를 거쳐 각 노드까지 가는 비용과 기존에 구한 각 노드의 최소 비용을 비교해 작은 값을 최소 비용으로 갱신하고 직전 노드도 갱신

다익스트라 알고리즘은 그리디로 동작해 최소 비용으로 경로를 갱신하므로 음의 가중치가 있는 경우, 탐색하지 못하고 알고리즘이 종료될 수 있음

벨만-포드 알고리즘

매 단계마다 모든 간선의 가중치를 다시 확인해 최소 비용을 갱신
음의 가중치가 있는 그래프에서도 최단 경로를 구할 수 있음
음의 순환이 있는 경우는 최단 경로를 구할 수 없는데, 이는 모든 알고리즘에 적용되는 문제

정리