네트워크 플로우 알고리즘 Ford-Fulkerson 방법

Ford-Fulkerson 개요

Ford-Fulkerson 알고리즘은 그래프에서 최대 유량을 계산하는 네트워크 플로우 알고리즘 중 하나입니다. 이 알고리즘은 소스(source)에서 싱크(sink)로의 최대 흐름을 찾기 위해 사용됩니다. 그래프 이론에서 자주 다뤄지는 주제 중 하나로, 다양한 응용 문제에 사용될 수 있습니다. 예를 들어, 파이프 네트워크에서 최대 물의 흐름을 구하거나, 최대 매칭 문제를 해결하는 데 이용됩니다.

Ford-Fulkerson 알고리즘은 증가 경로(augmenting path) 를 찾아 반복적으로 흐름을 증가시키며, 그래프에 유량을 추가하는 방법입니다. 이는 일반적으로 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS) 알고리즘을 사용하여 구현됩니다.

이 글에서는 Ford-Fulkerson 알고리즘의 기본 개념과 예제 코드를 Java와 C 언어로 제공하겠습니다.

Ford-Fulkerson 알고리즘의 개념

Ford-Fulkerson 알고리즘은 다음과 같은 과정으로 동작합니다:

1. 초기 흐름을 0으로 설정합니다.
2. 소스에서 싱크로 가는 경로를 찾습니다. 이 경로는 잔여 용량(residual capacity) 이 있는 경로여야 합니다.
3. 잔여 용량 중 최소값만큼 흐름을 추가합니다.
4. 경로를 찾을 수 없을 때까지 2-3 단계를 반복합니다.

잔여 용량이란 간선에서 현재 흐름을 제외한 나머지 용량을 의미합니다. Ford-Fulkerson 알고리즘은 유량을 계속해서 증가시키며 최대 유량을 찾습니다.

Ford-Fulkerson의 시간 복잡도는 그래프에서 사용하는 탐색 방법에 따라 달라집니다. 일반적인 경우, BFS를 사용하여 구현하면 O(V * E^2)의 시간 복잡도를 가지며, 이때 V는 정점의 수, E는 간선의 수입니다.

예제 문제 설명

예제 그래프는 다음과 같습니다.

• 정점 6개 (0, 1, 2, 3, 4, 5)
• 간선: (0 -> 1), (0 -> 2), (1 -> 3), (2 -> 4), (3 -> 5), (4 -> 5), (1 -> 4), (3 -> 2)

소스 정점은 0, 싱크 정점은 5입니다. 이 그래프에서 Ford-Fulkerson 알고리즘을 사용하여 최대 유량을 계산해 보겠습니다.

Java 구현

import java.util.*;

public class FordFulkerson {
    static final int V = 6; // 정점의 개수

    // 깊이 우선 탐색(DFS) 사용
    boolean dfs(int[][] residualGraph, int source, int sink, int[] parent) {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();
        stack.push(source);
        visited[source] = true;
        parent[source] = -1;

        while (!stack.isEmpty()) {
            int u = stack.pop();

            for (int v = 0; v < V; v++) {
                if (!visited[v] && residualGraph[u][v] > 0) {
                    stack.push(v);
                    parent[v] = u;
                    visited[v] = true;
                    if (v == sink) return true;
                }
            }
        }
        return false;
    }

    // Ford-Fulkerson 알고리즘
    int fordFulkerson(int[][] graph, int source, int sink) {
        int[][] residualGraph = new int[V][V];
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                residualGraph[u][v] = graph[u][v];
            }
        }

        int[] parent = new int[V];
        int maxFlow = 0;

        // 증가 경로가 있을 때까지 반복
        while (dfs(residualGraph, source, sink, parent)) {
            int pathFlow = Integer.MAX_VALUE;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                pathFlow = Math.min(pathFlow, residualGraph[u][v]);
            }

            // 잔여 용량 업데이트
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                residualGraph[u][v] -= pathFlow;
                residualGraph[v][u] += pathFlow;
            }

            maxFlow += pathFlow;
        }

        return maxFlow;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 16, 13, 0, 0, 0},
                {0, 0, 10, 12, 0, 0},
                {0, 4, 0, 0, 14, 0},
                {0, 0, 9, 0, 0, 20},
                {0, 0, 0, 7, 0, 4},
                {0, 0, 0, 0, 0, 0}
        };
        FordFulkerson ff = new FordFulkerson();
        System.out.println("최대 유량: " + ff.fordFulkerson(graph, 0, 5));
    }
}

C 구현

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

#define V 6

bool dfs(int residualGraph[V][V], int source, int sink, int parent[]) {
    bool visited[V];
    memset(visited, 0, sizeof(visited));

    int stack[V], top = -1;
    stack[++top] = source;
    visited[source] = true;
    parent[source] = -1;

    while (top >= 0) {
        int u = stack[top--];

        for (int v = 0; v < V; v++) {
            if (!visited[v] && residualGraph[u][v] > 0) {
                stack[++top] = v;
                parent[v] = u;
                visited[v] = true;
                if (v == sink) return true;
            }
        }
    }
    return false;
}

int fordFulkerson(int graph[V][V], int source, int sink) {
    int residualGraph[V][V];
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            residualGraph[u][v] = graph[u][v];
        }
    }

    int parent[V];
    int maxFlow = 0;

    while (dfs(residualGraph, source, sink, parent)) {
        int pathFlow = INT_MAX;
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = (pathFlow < residualGraph[u][v]) ? pathFlow : residualGraph[u][v];
        }

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residualGraph[u][v] -= pathFlow;
            residualGraph[v][u] += pathFlow;
        }

        maxFlow += pathFlow;
    }

    return maxFlow;
}

int main() {
    int graph[V][V] = {
        {0, 16, 13, 0, 0, 0},
        {0, 0, 10, 12, 0, 0},
        {0, 4, 0, 0, 14, 0},
        {0, 0, 9, 0, 0, 20},
        {0, 0, 0, 7, 0, 4},
        {0, 0, 0, 0, 0, 0}
    };

    printf("최대 유량: %d\n", fordFulkerson(graph, 0, 5));
    return 0;
}

마무리

Ford-Fulkerson 알고리즘은 간단한 개념으로 복잡한 네트워크 플로우 문제를 해결할 수 있는 강력한 도구입니다. Java와 C 언어로 각각 구현된 예제를 통해 최대 유량을 찾는 과정을 직접 확인해보세요. 이 알고리즘은 유량을 반복적으로 증가시키며 최적의 흐름을 찾아가는 방식이기 때문에, 다양한 네트워크 문제에서 응용할 수 있습니다.