Graph Algorithms (그래프 알고리즘)

"그래프 문제에서 정점을 어떤 순서로 방문할지(BFS·DFS·위상 정렬), 모든 정점을 최소 비용으로 어떻게 연결할지(MST·Kruskal)는 각각 어떤 자료구조와 전제를 쓰고, 최단 경로 문제와는 어디서 갈리는가?" 이 페이지는 그 질문에 답한다. 원문 노트들은 BFS·DFS를 탐색 기법으로, 위상 정렬을 정렬·순서 문제로, MST와 Kruskal을 최소 신장 트리로 따로 묶는다.^[1] 이 페이지는 이를 "정점을 방문하는 순서를 정하는 문제"와 "간선 가중치의 합을 줄이는 문제" 두 갈래로 다시 묶어 읽는다. 이 두 갈래 구분은 원문 분류를 이 Wiki가 재구성한 것이다. 가중치 경로의 최단 거리는 Shortest Path Algorithms가 따로 다룬다.

탐색: BFS와 DFS

BFS (너비우선탐색)

• BFS는 시작 정점에 인접한 정점을 먼저 모두 차례로 방문한 뒤, 방문했던 정점을 다시 시작점으로 삼아 그 인접 정점들을 차례로 방문한다.^[2]
• 인접 정점을 방문한 순서대로 다시 넓혀 가야 하므로, BFS는 선입선출 자료구조인 큐를 쓴다.^[2:1]
• 원문 의사코드는 다음과 같다. 시작 정점을 큐에 넣을 때 방문 표시를 하고, 큐에서 꺼낸 정점의 미방문 인접 정점도 큐에 넣는 순간 바로 표시한다.^[3]

BFS(V)
	큐 생성
	방문관리 배열 생성
	시작 정점 V를 큐에 삽입
	정점 V를 방문한 것으로 표시
	while (큐가 비어 있지 않은 경우) {
		t <- 큐의 첫 번째 원소 반환
		for (t와 연결된 모든 간선에 대해) {
			u <- t의 인접 정점
			u가 방문되지 않은 곳이면,
			u를 큐에 넣고, 방문한 것으로 표시
		}
	}

• 원문은 이 블록에 pascal 표시를 붙였지만 Pascal 코드가 아니라 한국어 의사코드이므로, 이 페이지에서는 text로 바꿔 옮겼다.

DFS (깊이우선탐색)

• DFS는 방문 플래그를 쓰는 재귀 방식이나, 스택과 방문 플래그를 쓰는 반복 방식으로 구현한다.^[4]
• 인접 행렬로 구현한 재귀 DFS는 현재 정점 v를 방문 표시한 뒤, arr[v][i] == 1이고 아직 방문하지 않은 정점 i마다 DFS(i)를 호출한다.^[5]
• 원문 인접 행렬 코드에는 "방문하지 않은 노드가 없을 경우"를 처리하려는 if (i == N) return;이 for (int i = 0; i < N; i++) 루프 안에 있다.^[5:1] 루프 안에서는 i < N이므로 이 조건은 참이 될 수 없어 실행되지 않는 줄이다. 이 판독은 이 Wiki가 코드를 읽고 덧붙인 것이다.
• 연결 리스트(node)로 구현한 재귀 DFS는 인접 리스트를 따라가며 방문하지 않은 정점을 재귀 호출한다.^[5:2]

void dfs(int v)
{
	nodePointer w;
	visited[v]  = true;
	printf("%d",v);
	for(w = graph[v]; w; w=w->link) 
		if(!visited[w->vertex]) dfs(w->vertex);
}

• 반복 DFS 의사코드는 스택 top의 미방문 인접 정점이 있으면 push하면서 방문 표시를 하고, 없으면 pop하는 일을 스택이 빌 때까지 반복한다.^[6] 원문은 top을 w라 부르고 "방문하지 않은 w"를 push한다고만 적으므로, 이를 top의 미방문 인접 정점으로 읽은 것은 이 Wiki의 해석이다.

1. 시작 정점(= v) 결정
2. stack의 top(= w)읽기
3. 방문하지 않은 w가 존재 => push(w) & visite 표시
4. 방문하지 않은 w가 없음 => pop()
5. 스택이 공백이 될 때 까지 2~4번 반복 수행

• 원문의 C++ 반복 코드는 격자(2차원 배열)에서 값이 1인 칸을 4방향으로 탐색한다. 스택에서 칸을 꺼낸 뒤 아직 방문하지 않았으면 그때 방문 표시를 하고, 경계와 조건을 통과한 미방문 이웃 칸을 모두 push한다.^[7] 아래는 그 탐색 루프 부분만 빈 줄을 빼고 들여쓰기를 줄여 옮긴 것이다. 원문 프로그램은 이 루프를 모든 칸을 도는 이중 for문 안에서 돌려, 값이 1이고 방문하지 않은 칸을 시작점으로 push하며, 탐색 결과를 출력하거나 세지 않는다.^[7:1]

int x[4] = {0, 0, 1, -1};
int y[4] = {1, -1, 0, 0};
// ...
while (!s.empty())
{
    a = s.top();
    s.pop();
    if (u[a.first][a.second] == 1 && !v[a.first][a.second])
    {
        v[a.first][a.second] = true;
        // 4방향 탐색
        for (int k = 0; k < 4; ++k)
        {
            int nx = a.first + x[k];
            int ny = a.second + y[k];
            // 경계 확인 및 조건 확인
            if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                u[nx][ny] == 1 && !v[nx][ny])
            {
                s.push({nx, ny});
            }
        }
    }
}

• 의사코드는 push할 때 방문 표시를 하고, C++ 코드는 pop한 뒤에 표시한다는 점에서 두 방식이 다르다.^[6:1][7:2] C++ 방식에서는 같은 칸이 꺼내지기 전에 여러 이웃에게서 중복으로 push될 수 있고, 꺼낼 때의 !v[...] 검사가 그 중복을 걸러 낸다고 볼 수 있다. 이 차이 분석은 이 Wiki의 해석이다.
• 격자 DFS의 4방향 배열과 경계 검사는 Implementation Problem Approach의 방향 벡터·범위 체크 도구와 같은 역할을 한다고 볼 수 있다.^[7:3][8] 두 노트의 방향 순서는 서로 다르다.
• 원문은 DFS의 결과가 "유일하게 결정X"이고 그 이유를 "순서가 없기 때문"이라고만 적는다.^[9] 이는 인접 정점 가운데 무엇을 먼저 고를지 정해져 있지 않다는 뜻으로 읽을 수 있다. 이 뒷부분은 이 Wiki의 해석이다.

BFS와 DFS 비교

• 위 표는 BFS 노트와 DFS 노트의 정의·의사코드·코드를 이 Wiki가 한 표로 맞춰 놓은 것이다.^{[2:2][3:1][4:1][6:2][7:4]}
• 원문은 BFS·DFS의 시간 복잡도, BFS가 가중치 없는 그래프에서 최단 거리를 준다는 성질, 인접 행렬과 인접 리스트의 비용 차이를 다루지 않는다. 그래서 이 페이지도 그 내용을 싣지 않는다.

백트래킹과의 관계

• 백트래킹은 상태 공간 트리를 탐색하다가 현재 경로가 해가 될 수 없으면 이전 단계로 되돌아가는 기법이며, 원문은 이를 DFS의 최적화 형태로 본다.^[10] 가지치기와 구현 틀은 Algorithm Design Strategies의 백트래킹 절에서 다룬다.

위상 정렬 (Topological Sort)

• 위상 정렬은 "A를 하려면 B를 먼저 해야 한다"는 선후 관계를 만족하도록, 방향 그래프의 정점을 선형으로 나열하는 알고리즘이다.^[11]
• 위상 정렬은 사이클이 없는 방향 그래프(DAG)에서만 유효하다. 사이클이 있으면 선후 관계가 순환해서 누가 먼저인지 정할 수 없다.^[12]
• 진입 차수(in-degree)는 어떤 노드로 들어오는 간선의 수다. 진입 차수가 0인 노드는 지금 바로 처리할 수 있고, 0보다 크면 먼저 처리되어야 할 노드가 남아 있어 기다린다.^[13]
• 그래서 위상 정렬은 진입 차수가 0인 노드를 처리하고, 그 노드를 제거했을 때 새로 0이 되는 노드를 이어서 처리하는 방식으로 동작한다.^[13:1]

Kahn 알고리즘

• Kahn 알고리즘은 다음 순서로 동작한다.^[14]
  1. 모든 노드의 진입 차수를 계산한다.
  2. 진입 차수가 0인 노드를 큐에 넣는다.
  3. 큐에서 노드를 꺼내 결과 리스트에 추가한다.
  4. 그 노드에서 출발하는 간선을 제거해 인접 노드의 진입 차수를 1 줄인다.
  5. 새로 진입 차수가 0이 된 노드를 큐에 넣는다.
  6. 큐가 빌 때까지 이 과정을 반복한다.
• 원문 Java 구현은 다음과 같다. 정점 번호를 1부터 V까지로 가정하고 진입 차수 0인 정점을 찾는다.^[14:1]

int[] inDegree = new int[V + 1];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= V; i++) graph.add(new ArrayList<>());

// 간선 입력
for (int[] edge : edges) {
    graph.get(edge[0]).add(edge[1]);
    inDegree[edge[1]]++;
}

Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= V; i++)
    if (inDegree[i] == 0) queue.offer(i);

List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
    int node = queue.poll();
    result.add(node);
    for (int next : graph.get(node)) {
        inDegree[next]--;
        if (inDegree[next] == 0) queue.offer(next);
    }
}

if (result.size() != V) {
    System.out.println("사이클 존재");
}

• 모든 정점과 간선을 한 번씩 처리하므로 시간 복잡도는 O(V + E)다.^[15]

결과가 유일하지 않은 이유

• 진입 차수가 0인 노드가 동시에 여럿이면, 어느 것을 먼저 처리하느냐에 따라 결과가 달라진다.^[16]
• 원문 예시 그래프에서는 4와 5의 진입 차수가 처음부터 0이라 두 노드가 함께 큐에 들어가므로, 4로 시작하는 순서와 5로 시작하는 순서가 모두 유효하다.^[16:1]

flowchart LR
    n5((5)) --> n2((2)) --> n3((3)) --> n1((1))
    n5 --> n0((0))
    n4((4)) --> n0
    n4 --> n1

• 사전순으로 가장 빠른 순서를 요구하는 문제라면 Queue 대신 PriorityQueue를 쓴다.^[16:2]

사이클 판별

• 결과 리스트의 크기가 정점 수 V보다 작으면 큐가 일찍 비었다는 뜻이고, 그래프에 사이클이 있다.^[17]
• 사이클에 묶인 노드들은 서로가 서로의 진입 차수를 유지시켜 0이 될 수 없으므로, 큐에 한 번도 들어가지 못하고 결과에서 빠진다.^[17:1]

활용과 DFS 기반 방식

• 위 활용 표는 원문 표를 옮긴 것이다.^[18]

• Kahn 방식은 진입 차수와 큐를 쓰는 BFS 기반이고, 다른 방식은 재귀 DFS와 스택을 쓰며 사이클을 탐지하려고 방문 상태 3가지를 관리한다.^[19] 직관성과 실전 선호 행은 원문 노트의 평가다. 원문은 DFS 기반 방식의 구현이나 세 방문 상태의 의미를 따로 설명하지 않는다.

최소 비용 연결: MST와 Kruskal

• 신장 트리는 n개 정점으로 이루어진 무향 그래프에서, n개 정점과 n-1개 간선으로 이루어진 트리다.^[20]
• 최소 신장 트리(MST)는 무향 가중치 그래프의 신장 트리 가운데 간선 가중치의 합이 최소인 것이다.^[20:1]
• Kruskal 알고리즘은 간선을 하나씩 골라 MST를 찾는다.^[21]
  1. 처음에 모든 간선을 가중치 오름차순으로 정렬한다.
  2. 가중치가 가장 낮은 간선부터 고르며 트리를 키운다. 사이클이 생기면, 남은 간선 가운데 그다음으로 가중치가 낮은 간선을 고른다.
  3. n-1개 간선을 고를 때까지 2를 반복한다.
• 원문은 간선이 사이클을 만드는지를 어떻게 판정하는지, Kruskal의 복잡도, 그래프가 연결되어 있어야 한다는 조건을 적지 않는다. 그래서 이 페이지도 그 내용을 싣지 않는다.

최단 경로와의 경계

• 원문은 그래프의 최소 비용 문제로 두 가지를 나란히 든다. 하나는 모든 정점을 잇는 간선 가중치의 합이 최소인 트리를 찾는 문제이고, 다른 하나는 두 정점 사이의 최소 비용 경로를 찾는 문제다.^[22]
• 첫째는 MST, 둘째는 최단 경로 문제에 해당한다. MST는 전체 연결 비용을, 최단 경로는 특정 두 정점 사이의 경로 비용을 줄이는 별개 문제로 나열되므로, MST를 최단 경로의 해법으로 바꿔 쓸 수 있다고 볼 근거는 원문에 없다. 이 구분은 이 Wiki의 해석이며, 둘이 다른 답을 내는 구체 예는 원문에 없다.

관련

• Shortest Path Algorithms: 같은 "최소 비용 문제"의 다른 갈래인 두 정점 사이 최단 경로를 Dijkstra, Bellman-Ford, Floyd-Warshall로 다룬다.
• Algorithm Design Strategies: DFS에 가지치기를 더한 백트래킹과, 완전 탐색과의 차이를 다룬다.
• Implementation Problem Approach: 격자 DFS가 쓰는 방향 벡터·범위 체크와, BFS·DFS·위상 정렬이 쓰는 Java 큐·스택·우선순위 큐 선택을 다룬다.

테스트 질문

• BFS와 DFS는 각각 어떤 자료구조를 쓰며, 원문 의사코드에서 방문 표시는 언제 하는가?
• Kahn 알고리즘에서 결과 리스트의 크기가 정점 수보다 작으면 무엇을 뜻하고, 왜 그런가?
• MST와 최단 경로는 둘 다 "최소 비용" 문제인데, 각각 무엇을 최소화하는가?

출처