그래프: 관계를 정점과 간선으로 바꾸어 생각하기
그래프는 정점 집합과 정점 사이 간선으로 관계를 표현하는 수학적 구조다. 도시는 정점, 도로는 간선이 될 수 있고 사람과 친구 관계, 과목과 선수 조건도 같은 방식으로 모델링할 수 있다. 무엇을 정점으로 둘지에 따라 문제의 의미가 달라진다.
정점은 대상을, 간선은 대상 사이의 관계를 나타낸다.
간선에 담는 정보
무방향 간선은 양쪽 관계를 나타내고 방향 간선은 한쪽에서 다른 쪽으로의 관계를 나타낸다. 가중치는 거리, 시간, 비용 등을 담는다. 한 길의 거리와 소요 시간을 같은 숫자로 취급하면 계산은 맞아도 해결한 문제가 달라질 수 있다.
경로는 간선을 따라 이어진 정점열이다. 정점 수와 간선 수는 다르며, 같은 정점을 반복하지 않는 단순 경로인지도 구분한다. 사이클은 출발점으로 되돌아오는 관계다. 방향 그래프에서는 A에서 B로 갈 수 있다고 B에서 A로 갈 수 있는 것은 아니다.
작은 도로망을 코드로 표현하기
아래는 거리 가중치를 가진 무방향 그래프를 인접 리스트로 표현한 예다. 양방향 도로는 두 정점의 목록에 모두 나타난다.
roads = {
"A": [("B", 4), ("C", 2)],
"B": [("A", 4), ("C", 1), ("D", 5)],
"C": [("A", 2), ("B", 1)],
"D": [("B", 5)],
}
route = ["A", "C", "B", "D"]
# The route uses three edges.
# Total distance is 2 + 1 + 5 = 8.
A→B→D의 거리는 9이지만 A→C→B→D는 8이다. 간선 수가 적은 경로가 가중치 합도 작다는 보장은 없다. 무가중치 최단 경로와 가중치 최단 경로를 서로 다른 문제로 다루는 이유다.
표현 방식도 중요하다. 인접 행렬은 두 정점의 간선 유무를 빠르게 확인하지만 O(V²) 공간을 쓴다. 인접 리스트는 O(V+E) 공간으로 희소 그래프에 유리하고 각 정점의 이웃을 순회하기 쉽다. 여기서 V와 E는 각각 정점 수와 간선 수다.
연결성은 모든 정점이 경로로 이어지는지에 관한 성질이다. 방향 그래프에는 강한 연결과 약한 연결이라는 서로 다른 기준이 있다. 비연결 그래프에서 출발점 하나의 탐색으로 모든 정점을 방문할 수 있다고 가정하면 일부 데이터를 놓친다.
실제 모델에는 자기 루프, 평행 간선, 방향, 음수 가중치 허용 여부를 명시해야 한다. 탐색·경로·연결·매칭 문제마다 요구하는 알고리즘과 가정이 다르다. 그래프를 그리는 것보다 먼저 관계가 무엇을 뜻하고 어떤 질문에 답할지 정의하는 일이 정확한 출발점이다.
표현에서 간선을 하나 빠뜨리면 알고리즘은 잘못된 입력 그래프의 답을 정확하게 계산할 수 있다. 실제 도로의 일방통행이나 이동 비용을 모델에 반영했는지 검토해야 한다. 다리 하나의 삭제가 전체 연결을 끊을 수도 있고, 같은 두 도시의 평행 도로는 다른 비용을 가질 수도 있다. 계산 결과를 현실의 질문으로 되돌려 해석하는 단계까지가 그래프 모델링이다. 동일한 정점 이름의 중복 등록이나 단위가 다른 가중치도 모델 입력에서 검사해야 한다.