📌읽고 나면 진짜 쉬워지는 자료 구조 - 15. 그래프

그래프는 여러 개의 객체(노드)가 서로 관계(간선)로 연결되어 있는 구조

🔖 5.1 그래프란?

그래프 개념

• 그래프는 노드(정점) 와 간선(엣지) 로 구성된다.

• 다른 자료 구조와 달리, 그래프는 어떤 특정한 연산을 최적화하려고 만든 게 아니라, 현실 세계의 관계나 흐름을 그대로 표현하기 위해 만들어졌다.

그래프의 특징

• 간선은 방향성이 있을 수도, 없을 수도 있다

  • 방향이 있으면 A → B처럼 흐름이 정해짐

  • 방향이 없으면 A - B처럼 양방향 연결.

• 간선에 가중치(비용) 를 줄 수 있다

  • e.g. A에서 B로 가는 데 걸리는 시간이나 거리

• 방향성과 가중치를 조합하면 복잡한 관계도 표현 가능하다.

그래프를 메모리에 표현하는 방법

• 인접 행렬: 2차원 배열로 표현. 노드 수가 적고 간선 수가 많을 때 효율적

• 인접 리스트: 각 노드가 연결된 노드를 리스트로 관리. 간선이 적은 희소 그래프에 적합

• 이 두 방식 모두 방향, 가중치 여부에 따라 유연하게 사용할 수 있다.

🔖 5.2. 다익스트라 알고리즘 - 최단 경로 찾기

어떤 알고리즘인가?

• 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.

• 가중치가 있는 그래프에서 동작하며, 음수 가중치는 허용하지 않음.

동작 방식

1. 시작 노드로부터 각 노드까지의 거리를 저장할 배열을 만들고, 모든 거리를 무한대로 설정

2. 시작 노드의 거리는 0으로 설정하고, 아직 방문하지 않은 노드 집합을 관리

3. 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택해 방문

4. 그 노드와 연결된 이웃 노드들의 거리 정보를 현재 거리 + 간선 가중치로 갱신

5. 위 과정을 모든 노드를 방문할 때까지 반복

요약

• 현재까지 찾은 최단 거리 정보를 계속 업데이트하면서 나아간다.

• 우선순위 큐(힙) 를 사용하면 효율적으로 구현 가능

🔖 5.3. 프림 알고리즘 - 최소 스패닝 트리 찾기

최소 스패닝 트리란?

• 모든 노드를 연결하면서, 전체 간선의 가중치 합이 최소가 되는 트리 구조를 말함.

• 순환이 없고, 노드는 모두 연결되어 있음.

프림 알고리즘은?

• 최소 스패닝 트리를 구하는 대표적인 알고리즘

• 다익스트라 알고리즘과 비슷하게 생겼지만, 최단 거리가 아니라 최소 비용의 연결을 목표로 한다.

동작 방식

1. 아무 노드 하나에서 시작.

2. 현재 트리에 연결 가능한 가장 가중치가 작은 간선을 선택해서 노드를 하나씩 추가.

3. 새로 추가한 노드를 기준으로 또 가장 싼 간선을 찾아 연결.

4. 모든 노드가 트리에 포함될 때까지 반복.

요약

• 기존 트리에 가장 저렴하게 연결할 수 있는 노드를 하나씩 추가해나가는 방식.

🔖 5.4. 칸 알고리즘 - 위상 정렬

위상 정렬이란?

• 순서가 중요한 작업들을 처리할 때 사용.

• e.g. 어떤 작업이 끝나야 다음 작업이 시작되는 경우.

• 이를 표현하려면 순환이 없는 방향 그래프(DAG) 가 필요함.

칸 알고리즘은?

• 방향 그래프에서 위상 정렬을 수행하는 알고리즘.

• 노드 간의 의존 관계를 고려하여 작업 순서를 결정한다.

동작 방식

1. 모든 노드의 진입 차수(자기한테 들어오는 간선 수) 를 센다.

2. 진입 차수가 0인 노드를 큐에 넣는다.

3. 큐에서 노드를 하나씩 꺼내면서 연결된 노드들의 진입 차수를 줄인다.

4. 새로 진입 차수가 0이 된 노드를 큐에 넣는다.

5. 이 과정을 반복해 모든 노드를 한 번씩 꺼낸 순서가 위상 정렬 결과가 된다.

🔖 5.5. 그래프가 중요한 이유

• 그래프는 현실 세계의 복잡한 관계나 흐름을 자연스럽게 표현할 수 있는 구조다.

• 도시 간의 도로, SNS 친구 관계, 컴파일 순서, 작업 스케줄링 등 다양한 문제를 그래프로 모델링할 수 있다.

• 그래프 알고리즘은 최단 경로, 최소 비용 연결, 의존 관계 정렬 등 실제 문제 해결에 직접적으로 활용된다.