Description What would you like to Propose? Description Add an implementation of the Gomory–Hu tree for undirected graphs that computes all-pairs minimum cuts using n−1 max-flow computations. API returns {parent, weight} arrays where parent[v] is the parent in the tree and weight[v] is the min-cut capacity between v and parent[v]. Files src/main/java/com/thealgorithms/graph/GomoryHuTree.java src/test/java/com/thealgorithms/graph/GomoryHuTreeTest.java DIRECTORY.md entry added under graph. Issue details Algorithm For each vertex s = 1..n-1, compute max-flow between s and parent[s] (initially 0 for all). Determine the min-cut partition from the final residual graph (reachability from source). Reparent nodes on the same side of the cut and apply the classic “parent re-linking” step. We use an Edmonds–Karp helper that also returns the reachable set for the min-cut. API GomoryHuTree.buildTree(int[][] cap) -> int[][] Returns a 2-row array: [parent[], weight[]]. parent[0] = -1, weight[0] = 0.Expects non-negative, square matrix; symmetric for undirected graphs. Tests GomoryHuTreeTest: Single-node trivial case. Triangle graph with symmetric capacities. Random small undirected graphs (n ≤ 6): Validates that for all pairs (s, t) the minimum edge weight along the unique path in the tree equals EdmondsKarp.maxFlow(cap, s, t). Checklist Implementation added in com.thealgorithms.graph. Tests pass locally (mvn test). DIRECTORY.md updated. clang-format applied to new files. No extraneous comments; concise class-level Javadoc with reference link. Additional Information Reference Wikipedia: Gomory–Hu tree You can’t perform that action at this time.
