10.1 그래프란?

그래프의 소개

그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조이다. 그래프의 대표적인 예는 지도이다.
그래프는 아주 일반적인 자료 구조로서 앞에서 배웠던 트리도 그래프의 하나의 특수한 종류로 볼 수 있다. 그래프 이론은 컴퓨터 학문 분야의 활발한 연구 주제이며 문제 해결을 위한 도구로서 많은 이론과 응용이 존재한다. 우리는 여기서 그래프의 기본적인 알고리즘에 대해서 학습한다.

그래프의 역사

1736년에 수학자 오일러(Euler)는 "Konigsberg의 다리" 문제를 해결하기 위하여 그래프를 처음으로 사용하였다. Konigsberg시의 한 가운데는 Pregel 강이 흐르고 있고 여기에는 7개의 다리가 있다. "Konigsberg의 다리" 문제란 "임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가"이다.
오일러는 이 문제에서 핵심적이고 중요한 것은 'A, B, C, D의 위치가 어떠한 관계로 연결되었는가?'라고 생각하고, 특정 지역은 정점(node)로, 다리는 간선(edge)로 표현하여 그래프(graph) 문제로 변환하였다. 오일러는 이러한 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명하였다.

10.2 그래프의 정의와 용어

그래프의 정의

그래프는 vertex(정점)와 edge(간선)들의 유한 집합이다. 수학적으로는 G = (V, E)와 같이 표시한다. 여기서 V(G)는 그래프 G의 vertices의 집합을, E(G)는 그래프 G의 edges의 집합을 의미한다. 정점은 여러 가지 특성을 가질 수 있ㅅ는 객체를 의미하고, 간선은 이러한 정점들 간의 관계를 의미한다. 정점은 노드라고도 불리며, 간선은 링크라고도 불린다.

무방향 그래프와 방향 그래프

간선의 종류에 따라 그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다.

네트워크

간선에 가중치를 할당하게 되면, 간선의 역할이 두 정점 간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 된다. 이렇게 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 네트워크(network)라 한다.

부분 그래프

어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프(subgraph)라 한다.

정점의 차수

그래프에서 인접 정점(adjacent vertex)란 간선에 의해 직접 연결된 정점을 뜻한다.
무방향 그래프에서 모든 정점의 차수를 함하면 간선 수의 2배가 된다. 방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree)라 하고 향하는 간선의 개수를 진출 차수(out-degree)라 한다.

경로

무방향 그래프에서 정점 s로부터 정점 e까지의 경로는 정점의 나열 s, v1, v2, ..., vk, e로서, 나열된 정점들 간에는 반드시 간선이 존재해야 한다.
경로 중에서 반복되는 간선이 없을 경우에 이러한 경로를 단순 경로(simple path)라 한다. 만약에 단순 경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클(cycle)이라 한다.

연결 그래프

무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며, 이러한 무방향 그래프 G를 연결 그래프(connected graph)라 부른다. 그렇지 않은 그래프는 비연결 그래프(unconnected graph)라고 한다. 트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프이다.

완전 그래프

그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프(complete graph)라고 한다. 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2가 된다.

그래프 추상 데이터 타입

객체: 정점의 집합과 간선의 집합
연산:
  create_graph() ::= 그래프를 생성한다.
  init(g) ::= 그래프 g를 초기화한다.
  insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입한다.
  insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입한다.
  delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제한다.
  delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제한다.
  is_empty(g) ::= 그래프 g가 공백 상태인지 확인한다.
  adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환한다.
  destroy_graph(g) ::= 그래프 g를 제거한다.

10.3 그래프의 표현 방법

인접 행렬

n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모릭 공간이 필요하다. 이에 따라 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(sparse graph)의 경우에는 메모리의 낭비가 크므로 적합하지 않다.
인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1)시간 안에 즉시 알 수 있는 장점이 있다. 또한 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산에 의해 알 수 있다.
반면에 그래프에 존재하는 모든 간선의 수를 알아내려면 O(n^2)의 시간이 요구된다.

import java.util.*;

public class AdjacencyMatrixGraph {
    private final Map<String, Integer> vertexIndexMap = new HashMap<>();
    private final List<String> indexVertexList = new ArrayList<>();
    private int[][] matrix;
    private int size;

    public AdjacencyMatrixGraph(int capacity) {
        this.size = 0;
        this.matrix = new int[capacity][capacity];
    }

    public static AdjacencyMatrixGraph create_graph(int capacity) {
        return new AdjacencyMatrixGraph(capacity);
    }

    public void init() {
        size = 0;
        vertexIndexMap.clear();
        indexVertexList.clear();
        for (int[] row : matrix) {
            Arrays.fill(row, 0);
        }
    }

    public void insert_vertex(String v) {
        if (vertexIndexMap.containsKey(v)) return;
        vertexIndexMap.put(v, size);
        indexVertexList.add(v);
        size++;
    }

    public void insert_edge(String u, String v) {
        Integer i = vertexIndexMap.get(u);
        Integer j = vertexIndexMap.get(v);
        if (i == null || j == null) return;
        matrix[i][j] = 1;
        matrix[j][i] = 1;
    }

    public void delete_edge(String u, String v) {
        Integer i = vertexIndexMap.get(u);
        Integer j = vertexIndexMap.get(v);
        if (i == null || j == null) return;
        matrix[i][j] = 0;
        matrix[j][i] = 0;
    }

    public void delete_vertex(String v) {
        Integer idx = vertexIndexMap.remove(v);
        if (idx == null) return;
        indexVertexList.set(idx, null); // 자리 유지

        for (int i = 0; i < matrix.length; i++) {
            matrix[idx][i] = 0;
            matrix[i][idx] = 0;
        }
    }

    public boolean is_empty() {
        return vertexIndexMap.isEmpty();
    }

    public List<String> adjacent(String v) {
        List<String> result = new ArrayList<>();
        Integer idx = vertexIndexMap.get(v);
        if (idx == null) return result;

        for (int j = 0; j < size; j++) {
            if (matrix[idx][j] == 1 && indexVertexList.get(j) != null) {
                result.add(indexVertexList.get(j));
            }
        }
        return result;
    }

    public void destroy_graph() {
        init();
    }

    public void print_graph() {
        System.out.println("   " + indexVertexList);
        for (int i = 0; i < size; i++) {
            String label = indexVertexList.get(i);
            if (label == null) continue;
            System.out.print(label + " → ");
            for (int j = 0; j < size; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

인접 리스트

import java.util.*;

public class AdjacencyListGraph {
    private final Map<String, List<String>> adjList = new HashMap<>();

    public static AdjacencyListGraph create_graph() {
        return new AdjacencyListGraph();
    }

    public void init() {
        adjList.clear();
    }

    public void insert_vertex(String v) {
        adjList.putIfAbsent(v, new ArrayList<>());
    }

    public void insert_edge(String u, String v) {
        if (!adjList.containsKey(u) || !adjList.containsKey(v)) return;

        if (!adjList.get(u).contains(v)) adjList.get(u).add(v);
        if (!adjList.get(v).contains(u)) adjList.get(v).add(u);
    }

    public void delete_vertex(String v) {
        if (!adjList.containsKey(v)) return;

        for (String neighbor : adjList.get(v)) {
            adjList.get(neighbor).remove(v);
        }
        adjList.remove(v);
    }

    public void delete_edge(String u, String v) {
        if (adjList.containsKey(u)) adjList.get(u).remove(v);
        if (adjList.containsKey(v)) adjList.get(v).remove(u);
    }

    public boolean is_empty() {
        return adjList.isEmpty();
    }

    public List<String> adjacent(String v) {
        return adjList.getOrDefault(v, new ArrayList<>());
    }

    public void destroy_graph() {
        adjList.clear();
    }

    public void print_graph() {
        for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
            System.out.println(entry.getKey() + " → " + entry.getValue());
        }
    }
}

10.5 Depth First Search(깊이 우선 탐색)

depth_first_search(v):

	v를 방문되었다고 표시;
    for all u ∈ (v에 인접한 정점) do
    	if (u가 아직 방문되지 않았으면)
        	then depth_first_search(u)

DFS 구현(인접 행렬 버전)

public void dfs(int start) {
    boolean[] visited = new boolean[size];
    dfsRecursive(start, visited);
}

private void dfsRecursive(int current, boolean[] visited) {
    visited[current] = true;
    for (int next = 0; next < size; next++) {
        if (matrix[current][next] == 1 && !visited[next]) {
            dfsRecursive(next, visited);
        }
    }
}

DFS 구현(인접 리스트 버전)

public void dfs(int start) {
    boolean[] visited = new boolean[size];
    dfsRecursive(start, visited);
}

private void dfsRecursive(int current, boolean[] visited) {
    visited[current] = true;
    for (int next : adjList.get(current)) {
        if (!visited[next]) {
            dfsRecursive(next, visited);
        }
    }
}

DFS 시간 복잡도

표현 방식	DFS 시간 복잡도	설명
인접 행렬	O(V²)	정점마다 모든 정점 탐색 → 이중 반복문 느낌
인접 리스트	O(V + E)	한 번씩만 순회함 (정점 + 간선)

Breath First Search(너비 우선 탐색)

breadth_first_search(v):

	v를 방문되었다고 표시;
    큐 Q에 정점 v를 삽입;
    while (Q가 공백이 아니면) do
    	Q에서 정점 w를 삭제;
        for all u ∈ (w에 인접한 정점) do
        	if (u가 아직 방문되지 않았으면)
            	then u를 큐에 삽입;
                	 u를 방문되었다고 표시;

BFS 구현(인접 행렬 버전)

public void bfs(int start) {
    boolean[] visited = new boolean[size];
	Queue<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (int next = 0; next < size; next++) {
            if (matrix[current][next] == 1 && !visited[next]) {
                visited[next] = true;
                queue.add(next);
            }
        }
    }
}

BFS 구현(인접 리스트 버전)

public void bfs(int start) {
    boolean[] visited = new boolean[size];
	Queue<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (int next : adjList.get(current)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.add(next);
            }
        }
    }
}

BFS 시간 복잡도

표현 방식	DFS 시간 복잡도	설명
인접 행렬	O(V²)	정점마다 모든 정점 탐색 → 이중 반복문 느낌
인접 리스트	O(V + E)	한 번씩만 순회함 (정점 + 간선)

DFS vs BFS

항목	DFS (Depth-First Search)	BFS (Breadth-First Search)
탐색 방향	한쪽 길 끝까지 깊게 파고듦	가까운 정점부터 넓게 탐색
자료구조	Stack (보통 재귀)	Queue
방문 순서	깊이 우선	레벨 우선
루프 감지	가능	가능
최단 거리 보장	❌ 아님	✅ 항상 보장 (무가중치 그래프)
메모리 사용	경로 깊이만큼	큐에 모든 레벨 저장 (폭)
시간 복잡도	O(V + E)	O(V + E)
그래프 표현별 차이	인접 리스트: O(V + E) 인접 행렬: O(V²)	동일

탐색 예시

     0
    / \
   1   2
  /     \
 3       4

• DFS(0): 0 → 1 → 3 → 2 → 4
• BFS(0): 0 → 1 → 2 → 3 → 4

언제 DFS를 쓰고, 언제 BFS를 쓰나?

목적	알고리즘	이유
미로 탐색 / 백트래킹	DFS	깊게 들어갔다가 되돌아오기
최단 거리 탐색 (무가중치)	BFS	가장 가까운 정점을 먼저 찾음
사이클 탐지	DFS	방문 중 노드 재방문 확인
경로 존재 여부만 필요	둘 다 가능	구현하기 편한 쪽 선택
가중치 그래프 최단 거리	❌ 둘 다 아님 → Dijkstra