Java实现二分图的最大匹配

1 问题描述

何为二分图的最大匹配问题？

引用自百度百科：

首先得说明一下何为匹配：

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

特别注意：二分图的最大匹配，其图为无权连通图。二分图的最大权分配，其图才是有权连通图，这两者是不同的概念。

2 解决方案

此处采用DFS方法。

package com.liuzhen.practice;

import java.util.Scanner;

public class Main {

    public static int n = 0, m = 0;  //二分图的左边和右边顶点数目

    /*

     * 参数map：给定的二分图，map[i][j]等于1表示i到j连通，为0则表示不连通

     * 参数linked：linked[i] = u表示顶点i与顶点u连接

     * 参数start：当前start顶点出发，寻找增广路径

     * 函数功能：如果能够找到已顶点start开始的增广路径返回true，否则返回false

     */

    public boolean dfs(int[][] map, boolean[] used, int[] linked, int start) {

        for(int i = 0;i < m;i++) {

            if(used[i] == false && map[start][i] == 1) {

                used[i] = true;

                if(linked[i] == -1 || dfs(map, used, linked, linked[i])) {

                    linked[i] = start;

                     return true;

                }

            }

        }

        return false;

    }

    public int getMaxNum(int[][] map) {

        int count = 0;

        int[] linked = new int[m];

        for(int i = 0;i < m;i++)

            linked[i] = -1;

        for(int i = 0;i < n;i++) {

            boolean[] used = new boolean[m];  //初始化m部分顶点均为被访问

            if(dfs(map, used, linked, i))  //从顶点i出发能够得到一条增广路径

                count++;

        }

        return count;

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        m = in.nextInt();

        int[][] map = new int[n][m];

        int k = in.nextInt();     //二分图中边的数目

        for(int i = 0;i < k;i++) {

            int a = in.nextInt();   //n部分中的顶点

            int b = in.nextInt();   //m部分中顶点

            map[a][b] = 1;

        }

        System.out.println(test.getMaxNum(map));

    }

}

巴特西

Java实现二分图的最大匹配

最新文章

热门文章