Ford-Fulkerson 알고리즘 Java 코드

Ford-Fulkerson

그래프에서 최대 유량을 찾아내는 알고리즘

*시간복잡도: O(E*f)

Java code

public class FordFulkerson {
    int vertexNum;
    int[][] capacity;
    int[][] flow;
    
    public int networkFlow(int source, int sink){
        int totalFlow = 0;
        while(true){ //최대 maxflow번 반복함
            int[] parent = new int[vertexNum];
            Arrays.fill(parent, -1);
            Queue<Integer> q = new LinkedList<>();
            parent[source] = source;
            q.add(source);
            while(!q.isEmpty() && parent[sink] == -1){
                int here = q.poll();
                for(int there=0; there<vertexNum; there++){
                    if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1){
                        q.add(there);
                        parent[there] = here;
                    }
                }
            }
            if(parent[sink] == -1) break;
            int amount = Integer.MAX_VALUE;
            for(int p = sink; p != source; p = parent[p]){
                amount = Math.min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
            }
            for(int p = sink; p != source; p = parent[p]){
                flow[parent[p]][p] += amount;
                flow[p][parent[p]] -= amount;
            }
            totalFlow += amount;
        }
        return totalFlow;
    }
}