[C++로 배우는 알고리즘과 자료구조 심화] Day 12: 네트워크 흐름 알고리즘 (Ford-Fulkerson, Edmonds-Karp)

네트워크 흐름 알고리즘

네트워크 흐름 알고리즘은 유량 네트워크에서 최대 유량을 찾는 데 사용됩니다. 유량 네트워크는 용량이 지정된 방향성 그래프로, 네트워크의 한 정점에서 다른 정점으로 흐르는 유량을 나타냅니다. 오늘은 Ford-Fulkerson 알고리즘과 Edmonds-Karp 알고리즘에 대해 학습하겠습니다.

Ford-Fulkerson 알고리즘

Ford-Fulkerson 알고리즘은 증가 경로(augmenting path)를 반복적으로 찾아 최대 유량을 계산하는 알고리즘입니다. 이 알고리즘은 DFS를 사용하여 증가 경로를 찾습니다.

Ford-Fulkerson 알고리즘의 시간 복잡도:

• 최악의 경우: (O(E \times f)), 여기서 (E)는 간선의 수, (f)는 최대 유량입니다.

Ford-Fulkerson 알고리즘 구현

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v, int capacity);
    int fordFulkerson(int source, int sink);

private:
    bool dfs(int source, int sink, std::vector<int>& parent);
    void printFlow();

    int vertices;
    std::vector<std::vector<int>> capacity;
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> flow;
};

Graph::Graph(int vertices) {
    this->vertices = vertices;
    capacity.resize(vertices, std::vector<int>(vertices, 0));
    adj.resize(vertices);
    flow.resize(vertices, std::vector<int>(vertices, 0));
}

void Graph::addEdge(int u, int v, int cap) {
    capacity[u][v] = cap;
    adj[u].push_back(v);
    adj[v].push_back(u); // 역방향 간선 추가
}

bool Graph::dfs(int source, int sink, std::vector<int>& parent) {
    std::vector<bool> visited(vertices, false);
    std::vector<int> stack;
    stack.push_back(source);
    visited[source] = true;
    parent[source] = -1;

    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();

        for (int v : adj[u]) {
            if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
                parent[v] = u;
                visited[v] = true;
                stack.push_back(v);

                if (v == sink) {
                    return true;
                }
            }
        }
    }
    return false;
}

int Graph::fordFulkerson(int source, int sink) {
    std::vector<int> parent(vertices);
    int maxFlow = 0;

    while (dfs(source, sink, parent)) {
        int pathFlow = INT_MAX;

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = std::min(pathFlow, capacity[u][v] - flow[u][v]);
        }

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

        maxFlow += pathFlow;
    }

    return maxFlow;
}

int main() {
    Graph g(6);
    g.addEdge(0, 1, 16);
    g.addEdge(0, 2, 13);
    g.addEdge(1, 2, 10);
    g.addEdge(1, 3, 12);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 4, 14);
    g.addEdge(3, 2, 9);
    g.addEdge(3, 5, 20);
    g.addEdge(4, 3, 7);
    g.addEdge(4, 5, 4);

    std::cout << "최대 유량: " << g.fordFulkerson(0, 5) << std::endl;

    return 0;
}

 

Edmonds-Karp 알고리즘

Edmonds-Karp 알고리즘은 Ford-Fulkerson 알고리즘의 구현 중 하나로, BFS를 사용하여 증가 경로를 찾습니다. 이는 Ford-Fulkerson 알고리즘의 성능을 개선합니다.

Edmonds-Karp 알고리즘의 시간 복잡도:

• (O(VE^2)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

Edmonds-Karp 알고리즘 구현

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v, int capacity);
    int edmondsKarp(int source, int sink);

private:
    bool bfs(int source, int sink, std::vector<int>& parent);
    void printFlow();

    int vertices;
    std::vector<std::vector<int>> capacity;
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> flow;
};

Graph::Graph(int vertices) {
    this->vertices = vertices;
    capacity.resize(vertices, std::vector<int>(vertices, 0));
    adj.resize(vertices);
    flow.resize(vertices, std::vector<int>(vertices, 0));
}

void Graph::addEdge(int u, int v, int cap) {
    capacity[u][v] = cap;
    adj[u].push_back(v);
    adj[v].push_back(u); // 역방향 간선 추가
}

bool Graph::bfs(int source, int sink, std::vector<int>& parent) {
    std::vector<bool> visited(vertices, false);
    std::queue<int> q;
    q.push(source);
    visited[source] = true;
    parent[source] = -1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
                parent[v] = u;
                visited[v] = true;
                q.push(v);

                if (v == sink) {
                    return true;
                }
            }
        }
    }
    return false;
}

int Graph::edmondsKarp(int source, int sink) {
    std::vector<int> parent(vertices);
    int maxFlow = 0;

    while (bfs(source, sink, parent)) {
        int pathFlow = INT_MAX;

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = std::min(pathFlow, capacity[u][v] - flow[u][v]);
        }

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

        maxFlow += pathFlow;
    }

    return maxFlow;
}

int main() {
    Graph g(6);
    g.addEdge(0, 1, 16);
    g.addEdge(0, 2, 13);
    g.addEdge(1, 2, 10);
    g.addEdge(1, 3, 12);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 4, 14);
    g.addEdge(3, 2, 9);
    g.addEdge(3, 5, 20);
    g.addEdge(4, 3, 7);
    g.addEdge(4, 5, 4);

    std::cout << "최대 유량: " << g.edmondsKarp(0, 5) << std::endl;

    return 0;
}

 

설명

1. Ford-Fulkerson 알고리즘:
   • DFS를 사용하여 증가 경로를 찾습니다.
   • 경로의 최소 잔여 용량을 찾아 유량을 증가시킵니다.
   • 증가 경로가 더 이상 없을 때까지 반복합니다.
2. Edmonds-Karp 알고리즘:
   • BFS를 사용하여 증가 경로를 찾습니다.
   • 경로의 최소 잔여 용량을 찾아 유량을 증가시킵니다.
   • 증가 경로가 더 이상 없을 때까지 반복합니다.

Ford-Fulkerson 알고리즘과 Edmonds-Karp 알고리즘의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 13: 이분 그래프 매칭 (Hopcroft-Karp 알고리즘)"에 대해 학습하겠습니다.