Maximal Matching - Hungarian Algorithm

Maximal Matching - Hungarian Algorithm

1.Reference

(1) Visual Exmaple: https://comzyh.com/blog/archives/148/#more-148

(2) DFS and BFS version: http://blog.jobbole.com/106084/

2.Implementation

public class HungarianAlgorithm {
    public static boolean find(List<List<Integer>> adjList, int start, boolean[] visited, int[] match) {
        if (adjList.size() == 0 || adjList.get(0).size() == 0) {
            return false;
        }

        for (int next : adjList.get(start)) {
            if (!visited[next]) {
                visited[next] = true;
                // next is not matched or we find an augmented path
                if (match[next] == -1 || find(adjList, next, visited, match)) {
                    match[next] = start;
                    return true;
                }
            }
        }
        return false;
    }

    public static int hungarian(int[][] relations, int n) {
        // Construct adjacent list
        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] relation : relations) {
            adjList.get(relation[0]).add(relation[1]);
        }

        boolean[] visited = new boolean[n];
        int[] match = new int[n];
        Arrays.fill(match, -1);

        int res = 0;

        for (int i = 0; i < n; i++) {
            if (find(adjList, i, visited, match)) {
                ++res;
            }
            // We need to clear visited array before we find the match for the next candidate
            Arrays.fill(visited, false);
        }

        System.out.println("Final Matching");
        for (int i = 0; i < n; i++) {
            System.out.println("Match " + i + " with " + match[i]);
        }

        return res;
    }

    public static void main(String[] args) {
        int[][] relations = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {3,2}};
        int n = 4;
        int matches = hungarian(relations, n);
        System.out.println("The maximal matching is " + matches);
    }
}

3.Time & Space Complexity

Time: O(V * E)

Space: O(V + E) for adjacent list