그래프(Graph): 연결 관계를 저장하고 탐색하기

그래프는 정점(vertex)의 집합 V와 간선(edge)의 집합 E로 이루어진다. 소셜 관계에서 사람은 정점, 친구 관계는 간선이다. 도로망에서는 교차로가 정점, 도로가 간선이다. 트리와 달리 순환이나 여러 경로가 있을 수 있으므로 방문 여부를 관리하지 않으면 탐색이 같은 정점을 끝없이 다시 방문할 수 있다.

무방향 간선 A—B는 양쪽으로 이동할 수 있고, 방향 간선 A→B는 A에서 B로만 이동한다. 무방향 그래프의 차수는 연결된 간선 수다. 방향 그래프는 들어오는 진입 차수와 나가는 진출 차수를 구분한다. 간선에 시간·거리·비용을 붙이면 가중 그래프가 된다. 자기 자신으로 향하는 간선(자기 루프)과 같은 두 정점 사이의 여러 간선(다중 간선)을 허용할지는 모델과 문제 조건에 따라 다르다. 그래프라서 반드시 금지되는 것은 아니다.

경로는 연속한 간선을 따라 방문하는 정점의 순서다. 정점이 반복되지 않는 경로를 단순 경로라고 한다. 시작 정점과 끝 정점이 같고 중간 간선을 따라 한 바퀴 돌아오면 사이클이다. 무방향 완전 그래프에 정점이 n개라면 각 정점의 이웃이 n-1개이고 각 간선을 두 번 세므로 간선은 n(n-1)/2개다.

인접 행렬과 인접 리스트

A—B, A—C, B—D라는 무방향 그래프를 정점 A=0, B=1, C=2, D=3으로 번호 붙여 보자.

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

인접 행렬에서 matrix[u][v]는 u와 v의 간선 존재 여부다. 무방향 그래프라면 matrix[u][v]와 matrix[v][u]를 함께 갱신한다. 방향 그래프라면 한쪽만 갱신한다. 행렬은 간선 존재 여부를 O(1)에 확인하지만 정점 수 V에 대해 O(V²) 공간이 필요하다. 한 정점의 이웃을 모두 찾으려면 행 전체 V칸을 살핀다. 간선이 조밀한 그래프, 작은 고정 정점 집합, 잦은 간선 존재 질의에 잘 맞는다.

인접 리스트로 같은 그래프를 적으면 0:[1,2], 1:[0,3], 2:[0], 3:[1]이다. 각 정점의 이웃만 저장하므로 공간은 O(V+E)다. 한 정점의 이웃 순회는 그 정점의 차수만큼 들지만, 특정 간선 하나의 존재 여부를 목록에서 찾는 데는 최악 O(차수)가 걸린다. 간선이 드문 큰 그래프나 전체 탐색에는 인접 리스트가 편리하다.

표현	공간	간선 확인	모든 이웃 열거
인접 행렬	O(V²)	O(1)	O(V)
인접 리스트	O(V+E)	O(차수), 별도 집합이면 평균 O(1)	O(차수)

아래 C 예제는 정점 번호를 0부터 n-1까지로 제한하고 무방향 행렬을 만든다. 잘못된 번호를 검사하지 않고 배열에 접근하면 범위 밖 메모리를 건드리므로 addEdge가 결과를 반환한다.

#include <stdbool.h>
#include <stdio.h>

#define MAX_VERTICES 10

typedef struct {
    int count;
    bool edge[MAX_VERTICES][MAX_VERTICES];
} MatrixGraph;

bool addEdge(MatrixGraph *graph, int from, int to) {
    if (graph == NULL || from < 0 || to < 0 ||
        from >= graph->count || to >= graph->count) {
        return false;
    }
    graph->edge[from][to] = true;
    graph->edge[to][from] = true; // 무방향 그래프
    return true;
}

int main(void) {
    MatrixGraph graph = {.count = 4};
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    for (int row = 0; row < graph.count; row++) {
        for (int col = 0; col < graph.count; col++) {
            printf("%d ", graph.edge[row][col] ? 1 : 0);
        }
        printf("\n");
    }
    return 0;
}

초기화에서 지정하지 않은 행렬 원소는 0으로 채워진다. 정점 0—1을 넣으면 [0][1]과 [1][0]이 true가 된다. 자기 루프를 막는 모델이라면 from == to 검사도 추가한다. 가중 그래프에서는 bool 대신 가중치와 ‘간선 없음’을 구분할 표현을 써야 한다. 가중치 0도 유효할 수 있으므로 0을 무조건 ‘없음’으로 쓰면 안 된다.

깊이 우선 탐색(DFS)

DFS는 한 경로를 가능한 깊이 따라간 뒤 더 갈 곳이 없으면 되돌아온다. 재귀 호출 스택이 돌아올 위치를 기억한다. A—B, A—C, B—D인 예에서 0부터 번호순으로 이웃을 보면 방문 순서는 0,1,3,2다. 1에서 3을 보고 돌아온 다음 0의 남은 이웃 2로 간다.

불변식: 방문 표시가 된 정점은 다시 재귀 호출하지 않는다. 정점이 함수에 들어올 때 방문 처리하면 무방향 간선의 반대편을 통해 되돌아오는 재귀를 막는다. 연결되지 않은 정점까지 모두 방문해야 하면 모든 정점에 대해 아직 방문하지 않은 곳에서 DFS를 새로 시작해야 한다.

너비 우선 탐색(BFS)

BFS는 시작점에서 한 간선 떨어진 정점들을 먼저, 이어서 두 간선 떨어진 정점들을 방문한다. 큐에는 발견했지만 아직 이웃을 전부 확인하지 않은 정점이 들어 있다. 같은 예에서 0으로 시작하면 1과 2가 먼저 큐에 들어가고, 1을 꺼냈을 때 3을 넣는다. 방문 순서는 0,1,2,3이고 간선 수로 잰 최단 거리는 각각 0,1,1,2다.

불변식: 정점은 큐에 넣을 때 발견 표시를 한다. 꺼낼 때 표시하면 여러 이웃이 같은 정점을 중복으로 넣을 수 있다. 모든 간선의 비용이 같은 무가중 그래프에서는 BFS가 최소 간선 수 경로를 준다. 가중치가 서로 다르거나 음수 간선이 있다면 BFS 거리값을 최단 비용으로 해석할 수 없다.

Java 인접 리스트로 두 탐색 구현

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class GraphTraversal {
    private final List<List<Integer>> edges;

    public GraphTraversal(int vertices) {
        if (vertices < 0) throw new IllegalArgumentException("음수 정점 수");
        edges = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            edges.add(new ArrayList<>());
        }
    }

    public void addUndirectedEdge(int a, int b) {
        checkVertex(a);
        checkVertex(b);
        edges.get(a).add(b);
        if (a != b) edges.get(b).add(a);
    }

    private void checkVertex(int v) {
        if (v < 0 || v >= edges.size()) {
            throw new IndexOutOfBoundsException("정점: " + v);
        }
    }

    public List<Integer> dfs(int start) {
        checkVertex(start);
        boolean[] visited = new boolean[edges.size()];
        List<Integer> order = new ArrayList<>();
        visitDepthFirst(start, visited, order);
        return order;
    }

    private void visitDepthFirst(int v, boolean[] visited, List<Integer> order) {
        visited[v] = true;
        order.add(v);
        for (int neighbor : edges.get(v)) {
            if (!visited[neighbor]) {
                visitDepthFirst(neighbor, visited, order);
            }
        }
    }

    public int[] bfsDistances(int start) {
        checkVertex(start);
        int[] distance = new int[edges.size()];
        Arrays.fill(distance, -1); // 도달 불가
        Deque<Integer> queue = new ArrayDeque<>();
        distance[start] = 0;
        queue.addLast(start);
        while (!queue.isEmpty()) {
            int v = queue.removeFirst();
            for (int neighbor : edges.get(v)) {
                if (distance[neighbor] != -1) continue;
                distance[neighbor] = distance[v] + 1;
                queue.addLast(neighbor);
            }
        }
        return distance;
    }

    public static void main(String[] args) {
        GraphTraversal graph = new GraphTraversal(4);
        graph.addUndirectedEdge(0, 1);
        graph.addUndirectedEdge(0, 2);
        graph.addUndirectedEdge(1, 3);
        System.out.println(graph.dfs(0)); // [0, 1, 3, 2]
        System.out.println(Arrays.toString(graph.bfsDistances(0)));
        // [0, 1, 1, 2]
    }
}

생성자는 정점 수만큼 빈 이웃 목록을 만들고, 간선 추가는 두 끝점에 서로를 기록한다. 자기 루프에서는 같은 간선을 중복 저장하지 않게 한 번만 기록한다. 이 예제는 다중 간선을 막지 않는다. 다중 간선을 피해야 한다면 add 전에 존재 여부를 확인하거나 이웃을 집합으로 저장한다. DFS의 visited와 BFS의 distance는 모두 ‘처음 발견했는가’를 기록한다. distance가 -1이면 시작 정점에서 도달할 수 없다.

인접 리스트에서는 각 정점을 한 번 발견하고 각 이웃 항목을 한 번씩 확인하므로 DFS와 BFS의 시간은 O(V+E), 추가 공간은 O(V)이다. 무방향 간선 하나가 두 목록에 있으므로 이웃 확인은 총 2E번이지만 빅오 표기는 같다. 재귀 DFS는 편향된 큰 그래프에서 호출 스택이 넘칠 수 있다. 그런 경우 명시적인 스택을 사용한다. 인접 행렬로 이웃을 찾는다면 모든 행을 훑으므로 탐색 시간은 O(V²)이다.

어떤 그래프 알고리즘으로 이어지는가

도달 가능성과 연결 요소는 DFS·BFS로 구할 수 있다. 간선 수가 최단 경로의 비용이라면 BFS를 사용한다. 간선마다 음수가 아닌 가중치가 있으면 다익스트라, 음수 간선까지 허용해야 하면 벨만–포드를 검토한다. 모든 정점을 최소 비용으로 연결하고 싶다면 최소 신장 트리 문제이며, 방향 간선·도달 가능성 조건을 별도로 확인해야 한다. 표현 방식과 탐색 알고리즘을 고르기 전에 그래프가 방향인지, 가중치가 있는지, 자기 루프·다중 간선이 가능한지를 먼저 정하자.