정점(노드)들과 그것을 잇는 간선들의 집합. 트리에서 루트가 하나라는 제약과 사이클이 없다는 제약을 걷어낸 것이 그래프다. 지하철 노선도, 친구 관계, 웹 페이지 링크처럼 무엇과 무엇이 이어져 있는지를 표현할 때 쓴다.
그래프를 이루는 용어
각각의 지점을 정점(vertex) 또는 노드(node)라 하고, 두 정점을 잇는 선을 간선(edge)이라 한다. 간선에 값이 적혀 있으면 그 값이 가중치(weight)이고 거리나 비용을 뜻한다. 한 정점에 붙은 간선의 수가 차수(degree)다.
간선에 방향이 있으면 차수가 둘로 갈린다. 들어오는 간선 수가 진입차수(in-degree), 나가는 간선 수가 진출차수(out-degree)다. 진입차수는 위상 정렬에서 그대로 쓰인다.
출발한 정점으로 되돌아오는 경로가 있으면 사이클이 존재한다고 한다. 모든 정점 쌍 사이에 경로가 있으면 연결 그래프, 없으면 비연결 그래프다. 간선으로 이어진 정점들을 묶었을 때 나오는 덩어리를 연결 요소(connected component)라고 부른다.
인접 행렬과 인접 리스트
구현은 인접 행렬과 인접 리스트 두 가지다. 인접 행렬은 정점 수 곱하기 정점 수 크기의 2차원 배열에 연결 여부를 적고, 인접 리스트는 정점마다 이어진 정점들의 리스트를 들고 있는다.
| 인접 행렬 | 인접 리스트 | |
|---|---|---|
| i와 j가 이어졌나 | O(1), 한 칸만 본다 | O(min(deg i, deg j)) |
| i에 이어진 정점 전부 | O(V), 한 행을 훑는다 | O(deg i), 리스트 길이만큼 |
| 공간 | O(V²) | O(V + E) |
대부분의 경우 인접 리스트를 쓴다. 현실의 그래프는 대개 희소해서, 인접 행렬을 쓰면 이어지지 않은 쌍까지 전부 자리를 차지한다. 정점이 10만 개면 인접 행렬은 100억 칸이라 아예 못 만든다.
인접 행렬이 나은 경우는 정점이 적고 간선이 빽빽하거나, i와 j가 이어졌는지를 계속 물어야 할 때다. 플로이드-워셜이 인접 행렬 위에서 도는 이유다.
연결 요소가 여럿일 때
연결 요소가 2개 이상이면 DFS나 BFS를 한 번만 돌려서는 전부 방문할 수 없다. 한 정점에서 시작한 탐색은 그 정점에서 갈 수 있는 곳만 보기 때문이다.
1번 정점부터 N번 정점까지 훑으면서 아직 방문하지 않은 정점이 있으면 거기서 탐색을 새로 시작해야 한다. 연결 요소의 개수를 세는 문제가 이 구조를 그대로 쓰고, 위상 정렬도 마찬가지다. 그래프 문제에서 자주 틀리는 지점이다.