[FEATURE REQUEST] Hungarian Algorithm (Kuhn–Munkres) for the Assignment Problem [Graphs]

[SamXop123]

What would you like to Propose?

What would you like to Propose?

• [type] New algorithm implementation
• [name] Hungarian Algorithm (Kuhn–Munkres) for the Assignment Problem
• [why]
  • Complements graph/ with a classic O(n^3) minimum-cost assignment solver.
  • Useful for scheduling, matching, optimization tasks; pairs well with HopcroftKarp, max-flow.
  • Supports rectangular matrices by padding; practical and frequently used.

Issue details

Issue Details

• [problem statement]

  • Given a non-negative r×c cost matrix, find a minimum-cost one-to-one assignment of rows to columns. If rows > cols, some rows remain unassigned.

• [proposed API]

  • Class: com.thealgorithms.graph.HungarianAlgorithm
  • Method: public static HungarianAlgorithm.Result solve(int[][] cost)
  • Result: Result { int[] assignment, int minCost }
    • assignment[i] = column index for row i, or -1 if row is unassigned (when rectangular).
    • minCost is the total minimal cost of assigned pairs.

• [constraints/validation]

  • Cost matrix is non-null, rectangular (all rows same length), entries ≥ 0.
  • Rectangular inputs are internally padded to square; unassigned rows preserved as -1.
  • Deterministic tests; algorithm complexity O(n^3), where n = max(r, c).

• [files to add/update]

  • src/main/java/com/thealgorithms/graph/HungarianAlgorithm.java
  • src/test/java/com/thealgorithms/graph/HungarianAlgorithmTest.java
  • DIRECTORY.md → add index under graph/ (alphabetical).

• [tests]

  • [classic 3×3] Known minimal cost and assignment (e.g., [1,0,2], cost 5).
  • [rectangular 3×2] Two assignments, one -1; verify minimal cost 3.
  • [zero diagonal] 3×3 zero-diagonal → total cost 0.

• [acceptance criteria]

  • All unit tests pass locally and in CI (Checkstyle, PMD, SpotBugs via mvn verify).
  • Clear Javadoc with constraints and reference.
  • DIRECTORY.md updated, alphabetical placement.

Additional Information

Additional Information

• [reference] Wikipedia: https://en.wikipedia.org/wiki/Hungarian_algorithm
• [notes]
  • Implementation is integer-based to align with repository conventions.
  • Future enhancements: return column-to-row mapping; long costs for larger ranges.