[알고리즘] 23. 그래프 기초

[알고리즘] 23. 그래프 기초

지난 글에서는 트리 기초에 대해 정리했습니다. 이번 글에서는 알고리즘에서 매우 중요한 자료구조인 그래프(Graph)에 대해 알아보겠습니다.

그래프는 여러 개의 대상이 서로 연결되어 있는 관계를 표현하는 자료구조입니다. 지하철 노선도, 도로망, 친구 관계, 컴퓨터 네트워크, 웹페이지 링크 구조처럼 연결 관계가 있는 문제에서 자주 사용됩니다.

그래프는 정점과 간선을 이용해 데이터 사이의 연결 관계를 표현하는 자료구조입니다.

---

1. 그래프란?

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 정점은 하나의 대상이고, 간선은 정점과 정점을 연결하는 선입니다.

A --- B
|     |
C --- D

위 구조에서 A, B, C, D는 정점입니다. A와 B를 연결하는 선, A와 C를 연결하는 선은 간선입니다.

그래프는 트리보다 더 자유로운 연결 구조를 표현할 수 있습니다. 트리는 계층 구조에 가깝지만, 그래프는 여러 정점이 다양한 방식으로 연결될 수 있습니다.

그래프는 데이터들이 서로 어떻게 연결되어 있는지를 표현할 때 사용합니다.

---

2. 그래프가 필요한 이유

알고리즘 문제에서는 단순히 값을 저장하는 것보다, 값들 사이의 관계를 처리해야 하는 경우가 많습니다. 이럴 때 그래프를 사용합니다.

• 도시와 도로의 연결 관계
• 사람과 사람의 친구 관계
• 컴퓨터 네트워크 연결
• 지하철역과 노선
• 웹페이지와 링크
• 작업 순서와 의존 관계
• 게임 맵에서 이동 가능한 위치

이런 문제들은 “어떤 값이 있는가”보다 “어떤 값과 어떤 값이 연결되어 있는가”가 중요합니다. 그래프는 이런 연결 정보를 표현하는 데 적합합니다.

---

3. 그래프의 기본 용어

그래프를 이해하기 위해 먼저 기본 용어를 정리해보겠습니다.

용어	의미
정점(Vertex)	그래프를 구성하는 각각의 대상
간선(Edge)	정점과 정점을 연결하는 선
인접(Adjacent)	두 정점이 간선으로 직접 연결된 상태
경로(Path)	정점에서 다른 정점까지 이동하는 순서
사이클(Cycle)	출발한 정점으로 다시 돌아오는 경로
차수(Degree)	한 정점에 연결된 간선의 개수

그래프 문제에서는 정점과 간선이라는 표현이 가장 자주 등장합니다. 문제에 따라 정점을 노드(Node)라고 부르기도 합니다.

그래프에서는 정점이 데이터, 간선이 연결 관계를 의미합니다.

---

4. 정점과 간선 예시

다음 그래프를 보겠습니다.

1 --- 2
|   / |
3 --- 4

이 그래프에는 정점 1, 2, 3, 4가 있습니다. 간선은 정점과 정점을 연결하는 선입니다.

구분	내용
정점	1, 2, 3, 4
간선	1-2, 1-3, 2-3, 2-4, 3-4

정점 1과 2는 직접 연결되어 있으므로 인접해 있습니다. 정점 1과 4는 직접 연결되어 있지는 않지만, 1 → 2 → 4 또는 1 → 3 → 4 경로로 이동할 수 있습니다.

---

5. 무방향 그래프

무방향 그래프는 간선에 방향이 없는 그래프입니다. 두 정점이 연결되어 있다면 양쪽으로 이동할 수 있습니다.

A --- B

위 그래프에서는 A에서 B로 갈 수 있고, B에서 A로도 갈 수 있습니다. 도로가 양방향으로 연결된 상황을 생각하면 이해하기 쉽습니다.

A → B 가능
B → A 가능

무방향 그래프에서는 간선 A-B와 B-A를 같은 연결로 봅니다.

무방향 그래프는 연결된 두 정점 사이를 양쪽 방향으로 이동할 수 있습니다.

---

6. 방향 그래프

방향 그래프는 간선에 방향이 있는 그래프입니다. 연결되어 있어도 정해진 방향으로만 이동할 수 있습니다.

A → B

위 그래프에서는 A에서 B로 이동할 수 있지만, B에서 A로 이동할 수는 없습니다.

A → B 가능
B → A 불가능

방향 그래프는 작업 순서, 웹페이지 링크, 팔로우 관계 같은 문제에서 자주 등장합니다. 예를 들어 내가 어떤 사람을 팔로우한다고 해서 그 사람이 나를 팔로우하는 것은 아닙니다.

방향 그래프는 간선의 방향을 반드시 고려해야 합니다.

---

7. 가중치 그래프

가중치 그래프는 간선에 비용이나 거리 같은 값이 붙어 있는 그래프입니다.

A -- 5 -- B
B -- 3 -- C
A -- 10 -- C

위 그래프에서 A와 B 사이의 비용은 5, B와 C 사이의 비용은 3, A와 C 사이의 비용은 10입니다.

가중치 그래프는 아래와 같은 문제에서 자주 사용됩니다.

• 도시 사이의 거리
• 도로 통행 시간
• 이동 비용
• 네트워크 전송 비용
• 최단 경로 문제

다익스트라 알고리즘 같은 최단 경로 알고리즘은 가중치 그래프에서 자주 사용됩니다.

---

8. 차수

차수는 한 정점에 연결된 간선의 개수입니다. 무방향 그래프에서는 해당 정점에 연결된 선의 개수를 세면 됩니다.

1 --- 2
|   / |
3 --- 4

위 그래프에서 각 정점의 차수를 보면 다음과 같습니다.

정점	연결된 정점	차수
1	2, 3	2
2	1, 3, 4	3
3	1, 2, 4	3
4	2, 3	2

방향 그래프에서는 들어오는 간선과 나가는 간선을 구분하기도 합니다. 들어오는 간선 수를 진입 차수, 나가는 간선 수를 진출 차수라고 합니다.

---

9. 경로와 사이클

경로는 한 정점에서 다른 정점까지 이동하는 순서입니다.

A --- B --- C
      |
      D

A에서 C까지 가는 경로는 A → B → C입니다. A에서 D까지 가는 경로는 A → B → D입니다.

사이클은 어떤 정점에서 출발해 다시 자기 자신으로 돌아오는 경로입니다.

A --- B
|     |
D --- C

위 그래프에서는 A → B → C → D → A처럼 다시 A로 돌아올 수 있습니다. 이런 구조를 사이클이라고 합니다.

사이클은 출발한 정점으로 다시 돌아올 수 있는 경로입니다.

---

10. 연결 그래프

연결 그래프는 모든 정점이 서로 어떻게든 연결되어 있는 그래프입니다. 직접 연결되어 있지 않아도 중간 정점을 거쳐 이동할 수 있으면 연결된 것으로 봅니다.

1 --- 2 --- 3
      |
      4

위 그래프에서는 1에서 3으로 직접 갈 수는 없지만, 1 → 2 → 3 경로로 이동할 수 있습니다. 모든 정점이 하나의 덩어리처럼 연결되어 있으므로 연결 그래프입니다.

반대로 아래처럼 두 그룹으로 나뉘어 있으면 연결 그래프가 아닙니다.

1 --- 2      3 --- 4

1과 3 사이에는 이동할 방법이 없습니다. 이런 경우 그래프가 여러 컴포넌트로 나뉘어 있다고 말할 수 있습니다.

---

11. 그래프 표현 방법

그래프를 코드로 다루려면 연결 정보를 저장해야 합니다. 대표적인 방법은 두 가지입니다.

표현 방법	설명
인접 행렬	2차원 배열로 연결 여부를 저장
인접 리스트	각 정점마다 연결된 정점 목록을 저장

그래프 문제에서는 입력으로 간선 정보가 주어지는 경우가 많습니다. 예를 들어 아래처럼 정점 1과 2가 연결되어 있다는 정보가 들어올 수 있습니다.

1 2
1 3
2 4

이 간선 정보를 인접 행렬이나 인접 리스트 형태로 저장한 뒤 탐색에 사용합니다.

---

12. 인접 행렬

인접 행렬은 2차원 배열을 이용해 정점 사이의 연결 여부를 저장하는 방식입니다. 정점 i와 j가 연결되어 있으면 graph[i][j]에 1 또는 true를 저장합니다.

예를 들어 정점 1, 2, 3이 있고, 1-2와 2-3이 연결되어 있다고 하겠습니다.

1 --- 2 --- 3

이를 인접 행렬로 표현하면 다음과 같습니다.

	1	2	3
1	0	1	0
2	1	0	1
3	0	1	0

무방향 그래프에서는 1과 2가 연결되어 있으면 graph[1][2]와 graph[2][1]을 모두 표시합니다.

int n = 3;
int[][] graph = new int[n + 1][n + 1];

graph[1][2] = 1;
graph[2][1] = 1;

graph[2][3] = 1;
graph[3][2] = 1;

인접 행렬은 두 정점이 연결되어 있는지 빠르게 확인할 수 있습니다.

---

13. 인접 리스트

인접 리스트는 각 정점마다 연결된 정점 목록을 저장하는 방식입니다. 그래프에서 간선 수가 많지 않을 때 효율적입니다.

예를 들어 아래 그래프를 인접 리스트로 표현해보겠습니다.

1 --- 2 --- 3
|
4

각 정점에 연결된 정점은 다음과 같습니다.

정점	연결된 정점
1	2, 4
2	1, 3
3	2
4	1

Java에서는 ArrayList 배열을 이용해 인접 리스트를 만들 수 있습니다.

import java.util.ArrayList;

int n = 4;
ArrayList<Integer>[] graph = new ArrayList[n + 1];

for (int i = 1; i <= n; i++) {
    graph[i] = new ArrayList<>();
}

graph[1].add(2);
graph[2].add(1);

graph[2].add(3);
graph[3].add(2);

graph[1].add(4);
graph[4].add(1);

무방향 그래프이므로 양쪽에 모두 연결 정보를 추가했습니다.

인접 리스트는 각 정점에 연결된 정점만 저장하기 때문에 메모리를 아낄 수 있습니다.

---

14. 인접 행렬과 인접 리스트 비교

인접 행렬과 인접 리스트는 각각 장단점이 있습니다. 문제의 조건에 따라 적절한 방식을 선택해야 합니다.

구분	인접 행렬	인접 리스트
저장 방식	2차원 배열	연결된 정점 목록
연결 확인	O(1)	연결 목록을 확인해야 함
메모리	O(V²)	O(V + E)
적합한 경우	정점 수가 작고 연결 확인이 많을 때	정점 수가 크고 간선 수가 적을 때

여기서 V는 정점 수, E는 간선 수를 의미합니다. 알고리즘 문제에서는 보통 정점 수가 크고 간선 수가 상대적으로 적은 경우가 많기 때문에 인접 리스트를 자주 사용합니다.

---

15. 그래프 탐색

그래프를 저장했다면 이제 정점을 방문하면서 탐색할 수 있습니다. 대표적인 그래프 탐색 방법은 DFS와 BFS입니다.

탐색 방법	특징	주로 사용하는 자료구조
DFS	한 방향으로 깊게 탐색	재귀, 스택
BFS	가까운 정점부터 탐색	큐

그래프 탐색에서는 방문 여부를 저장하는 visited 배열이 매우 중요합니다. 방문 체크를 하지 않으면 사이클이 있는 그래프에서 같은 정점을 계속 방문할 수 있습니다.

boolean[] visited = new boolean[n + 1];

그래프 탐색에서는 방문 배열로 이미 방문한 정점을 체크해야 합니다.

---

16. 트리와 그래프 비교

지난 글에서 배운 트리와 이번 글의 그래프를 비교해보겠습니다. 트리는 그래프의 특수한 형태로 볼 수 있습니다.

구분	트리	그래프
구조	계층 구조	자유로운 연결 구조
루트	보통 하나 있음	없을 수 있음
사이클	없음	있을 수 있음
간선 수	노드 N개이면 N - 1개	문제에 따라 다양함
관계	부모-자식 관계	일반 연결 관계

트리는 사이클이 없고 모든 노드가 연결된 그래프라고 생각할 수 있습니다. 그래프는 트리보다 더 넓은 개념입니다.

---

17. 그래프에서 자주 하는 실수

그래프 문제를 풀 때는 아래 실수를 조심해야 합니다.

• 방향 그래프인데 양방향으로 저장하는 경우
• 무방향 그래프인데 한쪽 방향만 저장하는 경우
• 정점 번호가 1부터 시작하는데 배열 크기를 n으로만 만드는 경우
• 방문 배열을 사용하지 않아 무한 반복이 발생하는 경우
• 인접 행렬과 인접 리스트 중 부적절한 방식을 선택하는 경우
• 가중치가 있는 그래프인데 비용 정보를 저장하지 않는 경우
• 연결되지 않은 그래프를 하나의 시작점만 탐색하는 경우

특히 무방향 그래프에서는 간선을 양쪽에 모두 추가해야 합니다.

graph[a].add(b);
graph[b].add(a);

반대로 방향 그래프에서는 주어진 방향대로만 저장해야 합니다.

graph[a].add(b);

그래프 문제에서는 방향이 있는지 없는지를 먼저 확인해야 합니다.

---

18. 정리

이번 글에서는 그래프 기초에 대해 정리했습니다.

• 그래프는 정점과 간선으로 이루어진 자료구조이다.
• 정점은 데이터, 간선은 정점 사이의 연결 관계를 의미한다.
• 무방향 그래프는 양쪽으로 이동할 수 있다.
• 방향 그래프는 정해진 방향으로만 이동할 수 있다.
• 가중치 그래프는 간선에 비용이나 거리 정보가 있다.
• 경로는 한 정점에서 다른 정점으로 이동하는 순서이다.
• 사이클은 출발한 정점으로 다시 돌아오는 경로이다.
• 그래프는 인접 행렬이나 인접 리스트로 표현할 수 있다.
• 그래프 탐색에는 DFS와 BFS가 자주 사용된다.

그래프는 알고리즘에서 정말 중요한 자료구조입니다. 처음에는 용어가 많고 복잡해 보일 수 있지만, 핵심은 간단합니다. 정점과 간선으로 연결 관계를 표현하고, 그 연결을 따라 탐색하는 것입니다.

그래프의 핵심은 데이터 사이의 연결 관계를 정점과 간선으로 표현하는 것입니다.

---

다음 글 예고

다음 글에서는 유니온 파인드(Union-Find)에 대해 알아보겠습니다.

서로소 집합, 부모 배열, find와 union 연산, 같은 집합인지 확인하는 방법까지 예제로 정리해보겠습니다.