yeolyi.com성열의 컴퓨터공학

그래프

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

지하철 앱이 길을 찾으려면 먼저 역이 서로 어떻게 이어졌는지를 메모리에 담아야 합니다. 그런데 역은 여러 노선으로 얽혀 있어 한 역에서 다른 역으로 가는 길이 여럿입니다. 부모가 하나뿐인 트리로는 이런 연결을 담을 수 없습니다.

정점과 간선

대상을 점으로, 관계를 점 사이의 선으로 나타낸 것을 그래프(graph)라 합니다. 점은 정점(vertex), 선은 간선(edge)이라 부릅니다. 지하철 노선도라면 역이 정점, 역 사이 구간이 간선입니다. 간선 하나로 바로 이어진 두 정점은 서로 인접(adjacent)해 있다고 합니다.

SNS 팔로우처럼 간선에 방향이 있으면 방향 그래프(directed graph), 친구 관계처럼 방향이 없으면 무방향 그래프(undirected graph)라 합니다. 간선에 거리나 시간 같은 값이 붙으면 가중치 그래프(weighted graph)입니다.

메모리는 번호가 매겨진 칸의 나열일 뿐입니다. 점과 선을 어떻게 칸에 담을까요?

인접 행렬과 인접 리스트

첫째는 표 한 장입니다. 정점이 n개면 n×n 칸짜리 표를 만들고, i에서 j로 가는 간선이 있으면 i행 j열 칸에 1, 없으면 0을 적습니다. 이 표를 인접 행렬(adjacency matrix)이라 합니다.

둘째는 정점마다 인접한 정점의 목록을 두는 방법입니다. 이것이 인접 리스트(adjacency list)입니다. 목록은 배열이나 연결 리스트로 만듭니다.

무방향 간선은 양쪽으로 다 갈 수 있으니 두 방법 모두 간선 하나를 두 번 적습니다. 행렬에는 i행 j열과 j행 i열에, 리스트에는 두 정점의 목록에 서로를 적습니다.

ABCDEF

정점 둘을 차례로 누르면 그 사이 간선을 넣거나 뺍니다. 표의 칸을 눌러도 됩니다.

인접 행렬 (행 → 열)
ABCDEF
A0
B0
C0
D0
E0
F0
인접 리스트
A→BF
B→ACE
C→BD
D→C
E→BF
F→AE

행렬은 늘 36칸, 그중 1인 칸 12개 · 리스트 항목 12개

  1. “방향 있음”으로 바꾸고 행렬에서 0인 칸을 눌러 봅시다.
  2. 간선을 넣고 빼며 맨 아래 숫자를 봅시다.

무엇을 고를까

사용자 100만 명이 각자 친구 100명씩 있다면 인접 행렬은 1조 칸이 필요하지만, 인접 리스트는 1억 칸이면 됩니다. 이렇게 간선이 드문 그래프는 인접 리스트가 유리하고, 간선이 촘촘하거나 이어졌는지를 자주 묻는다면 인접 행렬이 낫습니다.

도전 문제

정점이 7개인 무방향 그래프를 인접 리스트로 나타냅니다. 자기 자신으로 가는 간선이나 같은 두 정점 사이의 간선 여러 개는 없습니다. 목록 길이가 홀수인 정점은 많아야 몇 개일까요? 숫자로 답하세요.