yg log --graph --oneline --all

Home Stack Notes AboutRSS

9. 그래프의 저장 방식이 탐색 비용을 바꾼다

작성 · 5분 읽기 · 조회수 —수정

기초 개념과 예제를 보강하고 시리즈 흐름을 연결

연결 관계를 저장하는 문제

그래프를 처음 볼 때는 복잡한 그림보다 입력과 원하는 답을 먼저 정하면 이해하기 쉽다. 사람 네 명을 0, 1, 2, 3으로 부르고, 서로 연락할 수 있는 쌍을 다음처럼 받는다고 하자.

정점 수: 4
연결: 0-1, 0-2, 1-3
질문: 0과 바로 연결된 정점은 무엇인가
답: 1, 2

여기서 정점(vertex)은 사람처럼 하나의 대상을 뜻하고, 간선(edge)은 두 대상 사이의 관계를 뜻한다. 0-1은 정점 0과 1을 잇는 간선이다. 방향이 없는 간선이라면 0-1과 1-0은 같은 관계다. 간선에 거리나 요금이 붙으면 그 숫자를 가중치(weight)라고 한다.

그래프는 보통 $G=(V,E)$로 적는다. $V$는 정점의 집합, $E$는 간선의 집합이다. 이 글의 문제는 탐색 알고리즘을 실행하는 것이 아니라, 다음 질문에 빠르게 답할 수 있도록 $V$와 $E$를 메모리에 배치하는 것이다.

  • 한 정점의 이웃을 모두 찾기
  • 두 정점 사이에 간선이 있는지 확인하기
  • 간선을 추가하거나 삭제하기
  • 연결되지 않은 정점도 잃지 않고 보관하기

인접(adjacent)하다는 말은 두 정점이 간선 하나로 직접 연결됐다는 뜻이다. 차수(degree)는 무방향 그래프에서 한 정점에 닿는 간선 수다. 위 예시에서 정점 0의 이웃은 1과 2이고 차수는 2다. 이 기본 질문을 어떤 방식으로 자주 물을지에 따라 저장 구조가 달라진다.

간선만 남길 수 있는지 물었던 기록

그래프 노트의 부그래프 부분에 이런 질문을 적어 두었다.

그럼 간선만 있고 정점은 없는 그런 그래프도 있나?

바로 아래에는 “간선의 정의는 정점쌍의 집합이므로 정점이 없는데 간선이 있을 수 없음”이라고 답했다. 정점 집합의 부분집합과 간선 집합의 부분집합을 고른다는 정의를 읽다가, 두 집합을 아무렇게나 따로 골라도 되는지 확인한 흔적이다.

이 질문은 C로 옮길 때도 남는다. 간선 노드에 vertex = 3을 적었다면, 3이라는 정점이 그래프에 실제로 있어야 한다. 간선의 양끝점을 담는 방법은 달라도 존재하지 않는 정점을 간선이 참조하지 않는다는 조건은 같아야 한다.

확인한 공개 25-2 저장소에는 그래프 구현이 없었고, 「그래프 인접리스트」 노트에는 구조체와 노드 생성 코드 조각이 남아 있었다. 이번에는 그 조각을 바탕으로 작은 검증 코드를 완성했다. 정점은 0부터 n-1까지의 번호로 나타내고, 간선의 삽입 전에 양끝점이 그 범위에 있는지 확인한다.

next는 다음 방문 정점이 아니다

인접리스트 노트는 이렇게 시작한다.

인접리스트 방식은 노드와 배열을 동시에 이용한다.

정점마다 연결리스트의 시작 주소 하나를 배열에 저장한다. 그 연결리스트는 해당 정점에서 나가는 간선들을 담는다.

typedef struct Node {
    int vertex;
    int weight;
    struct Node *next;
} Node;

Node *adj[16];

예를 들어 0—1, 0—2, 1—3, 2—3의 네 무방향 간선이 있다면 다음처럼 저장할 수 있다. 여기서 화살표는 그래프의 방향이 아니라 연결리스트의 next다.

adj[0] -> (vertex=1) -> (vertex=2) -> NULL
adj[1] -> (vertex=0) -> (vertex=3) -> NULL
adj[2] -> (vertex=0) -> (vertex=3) -> NULL
adj[3] -> (vertex=1) -> (vertex=2) -> NULL
adj[4] -> NULL

adj[0]의 첫 노드에서 next로 이동하면 “0에서 갈 수 있는 다른 이웃인 2”를 확인한다. 정점 1에서 다음 이동을 시작하는 것은 아니다. 정점 1의 이웃을 보려면 adj[1]로 들어가야 한다. 이 차이가 다음 글의 DFS 재귀 호출과 BFS 큐를 읽는 기준이 된다.

간선 하나가 양쪽 리스트에 한 번씩 저장되는 것도 보인다. 무방향 간선이 E개면 간선 노드는 2E개다. 정점 4는 간선이 없어도 배열에 자리를 갖는다. 간선만 따로 저장하면서 정점 수를 추정하면 이런 고립 정점을 놓치기 쉽다.

오름차순은 직접 유지해야 한다

노트에는 “간선은 정점의 오름차순 순서로 존재”한다고 적혀 있다. 인접리스트라서 저절로 정렬되는 것은 아니다. 이번 구현에서는 같은 순회 결과를 재현하기 위해 삽입할 위치를 찾아 오름차순을 유지했다.

static void add_arc(Graph *g, int u, int v, int w) {
    assert(u >= 0 && u < g->n && v >= 0 && v < g->n);
    assert(w >= -1000 && w <= 1000);
    Node **slot = &g->adj[u];
    while (*slot && (*slot)->vertex < v) slot = &(*slot)->next;
    if (*slot && (*slot)->vertex == v) { (*slot)->weight = w; return; }
    Node *p = malloc(sizeof *p); assert(p);
    *p = (Node){v, w, *slot}; *slot = p;
}

slot은 새 노드를 연결할 포인터의 자리다. 처음에는 adj[u]이고, 앞의 이웃들을 지나면 어떤 노드의 next가 된다. 그래서 맨 앞 삽입과 중간 삽입을 같은 대입으로 처리할 수 있다. *slot이 기존 뒤쪽을 보존하고, 마지막 *slot = p가 앞쪽을 새 노드로 연결한다.

같은 이웃 번호가 이미 있으면 가중치만 갱신한다. 따라서 이 코드는 병렬 간선을 표현하지 않는 단순 그래프용이다. 무방향 간선은 add_arc(u, v)와 add_arc(v, u)를 함께 호출하고, 삭제도 양쪽에 적용해야 한다. 한쪽만 지우면 의도와 다른 방향 그래프가 된다.

저장한 자리만 볼지 가능한 자리를 모두 볼지

같은 그래프를 인접행렬로 저장하면 (u, v)마다 간선이 있는지 바로 읽을 수 있다. 반면 정점 u의 모든 이웃을 찾으려면 그 행의 V칸을 검사해야 한다. 인접리스트는 실제 이웃 수만큼만 따라간다.

작업 정렬된 인접리스트 인접행렬
그래프 저장 공간 O(V+E) O(V²)
u의 이웃 전부 확인 O(deg(u)) O(V)
u→v 간선 조회 최악 O(deg(u)) O(1)
간선 삽입 위치 탐색 포함 O(deg(u)) O(1)
모든 정점의 이웃 확인 O(V+E) O(V²)

노트의 “그래프 알고리즘의 선택은 간선의 밀집도에 따라 좌우된다”는 문장을 이 표로 구체화할 수 있다. 정점이 많아도 간선이 적으면 빈 칸을 매번 검사하는 비용이 커진다. 반대로 거의 모든 정점이 연결되어 있고 두 정점 사이의 간선을 자주 물으면 행렬의 직접 조회가 편하다. 인접리스트를 사용하는 그래프 순회가 O(V+E)인 이유도 여기에 있다. Algorithms, 4th Edition의 그래프 표현과 순회 설명

희소 그래프의 간선 수가 반드시 V에 가깝다는 뜻은 아니다. 고립 정점만 있는 그래프는 E=0이다. 연결된 무방향 그래프라는 조건이 붙어야 E≥V-1이라는 하한이 생긴다.

0원 간선과 없는 간선을 구분한다

가중치 행렬에서 0을 “간선 없음”으로 정하면 가중치가 0인 간선을 표현할 수 없다. 이번 검증 코드에서는 행렬로 변환할 때 존재 여부 has[u][v]와 가중치 weight[u][v]를 따로 두었다. 0→2의 가중치가 0이어도 has[0][2]는 참이고, 없는 0→4는 거짓이다.

새 검증에서는 0원 간선, 고립 정점, 같은 간선의 가중치 갱신, 삭제 후 재삽입을 확인했다. 그래프를 어떤 모양으로 저장할지만 정하는 것이 아니라, 그 표현이 무엇을 구분할 수 있어야 하는지를 먼저 적어 보는 과정이다. 처음의 “간선만 남길 수 있나”도 결국 그 조건을 묻고 있었다.

기록과 실행 코드

관련 포스트