程序包 edu.princeton.cs.algs4

类 BipartiteMatching

  • public class BipartiteMatching
extends java.lang.Object
    The BipartiteMatching class represents a data type for computing a maximum (cardinality) matching and a minimum (cardinality) vertex cover in a bipartite graph. A bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A matching in a graph is a subset of its edges with no common vertices. A maximum matching is a matching with the maximum number of edges. A perfect matching is a matching which matches all vertices in the graph. A vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any biparite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover. The maximum matching problem in nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

    This implementation uses the alternating-path algorithm. It is equivalent to reducing to the maximum-flow problem and running the augmenting-path algorithm on the resulting flow network, but it does so with less overhead. The order of growth of the running time in the worst case is (E + V) V, where E is the number of edges and V is the number of vertices in the graph. It uses extra space (not including the graph) proportional to V.

    See also HopcroftKarp, which solves the problem in O(E sqrt(V)) using the Hopcroft-Karp algorithm and BipartiteMatchingToMaxflow, which solves the problem in O(E V) time via a reduction to maxflow.

    For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      BipartiteMatching​(Graph G)
      Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.

    • 方法概要

      修饰符和类型 方法 说明
      boolean inMinVertexCover​(int v)
      Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
      boolean isMatched​(int v)
      Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
      boolean isPerfect()
      Returns true if the graph contains a perfect matching.
      static void main​(java.lang.String[] args)
      Unit tests the HopcroftKarp data type.
      int mate​(int v)
      Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
      int size()
      Returns the number of edges in a maximum matching.

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 构造器详细资料

      • BipartiteMatching

        public BipartiteMatching​(Graph G)
        Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.
        参数:
        G - the bipartite graph
        抛出:
        java.lang.IllegalArgumentException - if G is not bipartite

    • 方法详细资料

      • mate

        public int mate​(int v)
        Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
        参数:
        v - the vertex
        返回:
        the vertex to which vertex v is matched in the maximum matching; -1 if the vertex is not matched
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • isMatched

        public boolean isMatched​(int v)
        Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
        参数:
        v - the vertex
        返回:
        true if vertex v is matched in maximum matching; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • size

        public int size()
        Returns the number of edges in a maximum matching.
        返回:
        the number of edges in a maximum matching

      • isPerfect

        public boolean isPerfect()
        Returns true if the graph contains a perfect matching. That is, the number of edges in a maximum matching is equal to one half of the number of vertices in the graph (so that every vertex is matched).
        返回:
        true if the graph contains a perfect matching; false otherwise

      • inMinVertexCover

        public boolean inMinVertexCover​(int v)
        Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
        参数:
        v - the vertex
        返回:
        true if vertex v is in the minimum vertex cover; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the HopcroftKarp data type. Takes three command-line arguments V1, V2, and E; creates a random bipartite graph with V1 + V2 vertices and E edges; computes a maximum matching and minimum vertex cover; and prints the results.
        参数:
        args - the command-line arguments