如何在Java中实现带权非二分图的最大权匹配？求替代库

Hey there! I see you've got a solid implementation going in NetworkX for max-cardinality max-weight matching on a weighted non-bipartite graph, and you're stuck finding a Java equivalent after trying JGraphT. Good news—JGraphT does support this use case, you just might have overlooked the right algorithm class. Let's walk through the solution, plus a backup option if you need it:

Option 1: JGraphT Implementation (The Right Way) #

JGraphT has the BlossomVAlgorithm class specifically designed for solving max-weight matching problems on general (non-bipartite) graphs, and it lets you prioritize max cardinality exactly like your Python code does with maxcardinality=True.

Full Code Example #

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;
import org.jgrapht.alg.matching.BlossomVAlgorithm;
import org.jgrapht.alg.matching.MatchingAlgorithm;

import java.util.Set;

public class MaxWeightMatchingDemo {
    public static void main(String[] args) {
        // Initialize weighted undirected graph
        Graph<Integer, DefaultWeightedEdge> graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);
        
        // Add vertices
        graph.addVertex(1);
        graph.addVertex(2);
        graph.addVertex(3);
        graph.addVertex(4);
        
        // Add weighted edges (matches your Python graph exactly)
        graph.setEdgeWeight(graph.addEdge(1, 2), 30);
        graph.setEdgeWeight(graph.addEdge(1, 3), 100);
        graph.setEdgeWeight(graph.addEdge(1, 4), 30);
        graph.setEdgeWeight(graph.addEdge(2, 3), 0);
        graph.setEdgeWeight(graph.addEdge(2, 4), 30);
        graph.setEdgeWeight(graph.addEdge(3, 4), 30);
        
        // Set up BlossomV algorithm, enable max-cardinality priority
        BlossomVAlgorithm<Integer, DefaultWeightedEdge> blossomV = new BlossomVAlgorithm<>(graph);
        // Passing `true` here prioritizes maximum cardinality first, then maximum weight
        MatchingAlgorithm.Matching<Integer, DefaultWeightedEdge> matching = blossomV.getMatching(true);
        
        // Output the result
        System.out.println("Max-Cardinality Max-Weight Matching Result:");
        for (DefaultWeightedEdge edge : matching.getEdges()) {
            int u = graph.getEdgeSource(edge);
            int v = graph.getEdgeTarget(edge);
            System.out.printf("(%d, %d)%n", u, v);
        }
    }
}

Maven Dependency #

Add this to your pom.xml to pull in JGraphT's core library (use the latest stable version if available):

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-core</artifactId>
    <version>1.5.1</version>
</dependency>

When you run this code, you'll get the exact same output as your Python implementation: (1, 3) and (2, 4).

Option 2: Alternative Library (If JGraphT Still Doesn't Fit) #

If you need another option, Apache Commons Graph is a lesser-known but capable library that supports general graph matching algorithms. That said, JGraphT is far more widely used and well-documented, so it's the better default choice.

Quick Note on Your JGraphT Troubles #

Chances are you were looking at bipartite matching algorithms (like HopcroftKarpAlgorithm) instead of the general graph-focused BlossomVAlgorithm. Easy mix-up—bipartite matching algorithms won't work for non-bipartite graphs, which is why you hit a wall earlier!

内容的提问来源于stack exchange，提问作者Gevorg Harutyunyan