如何完成这个BiPartite匹配程序？

Question

我正在为课堂做一项作业，在那里我必须读取一个邻接矩阵并输出Java中的二分匹配。我得到了两种方法来完成这一任务，而且我成功地让它在一个用例中工作，但是我在让它为另外两个用例工作时遇到了一些困难。我将粘贴我的源代码在下面。在程序开始时有3个测试用例，每个测试用例的预期输出都显示在最后。

我需要将矩阵实现为二维字符数组。我遇到的问题似乎是它的回溯部分。第二个测试用例返回正确的结果。如果有人能帮我理解我做错了什么，我会非常感激的。我寻找匹配的过程是：

1. 从最后一行开始
2. 遍历每一列
3. 如果该列标记为Y，且该列当前未被接受(标记为“T”)，则将该列标记为“T”。
4. 方法递归地调用下一行。
5. 遍历矩阵，显示匹配 公共类BiPartiteMatch { // *主*公共静态BiPartiteMatch(String[] args) { System.out.println("Case 1:不存在匹配“)。(n“)；// a b c d e没有匹配的A，C，E//*D*/ {'n'，'y'，'n'，'y'，'n'}，'n'，'n'，'y'，'n'}，/*B*/ {'y'，'n'，'y'，'y'，'y'}，/*A*/ {'y'，'n'，'n'，'y'，'n' }；System.out.println(“案例2:匹配而不需要回溯。(n“)；// a b c d e与no //'y'，'n'，'y'，'n'}，/*C*/ {'n'，'y'，'n'，'n'}，/*B*/ {'y'，'n'，'y'，'n'，'n'}，/*A*/ {'n'，'y'，'n'，'n'，'y' }；System.out.println(“案例3:与回溯匹配”)。(n“)；// a b c d e与//'y‘、’n‘、'n'}、/*C*/ {'n’、'y‘、'y’、'n'}、/*B*/ {'n‘、'y’、‘n’、'y‘、'n'}、/*A*/ {'y’、‘n’、'n'，'y'，'y' }；如果(findMatch(M，M.length-1)) //查找匹配，以最后一行displayMatches(M)开始；否则System.out.println(“没有匹配”)；}// end main // *递归findMatch *，递归findMatch*递归findMatch*递归的findMatch*c++) { if(MmyRow == 'y‘& !isTaken(M，myRow，c)) { MmyRow = 't'；}} findMatch(M，myRow-1)；返回true；}// end findMatch /* isTaken *公共静态布尔isTaken(char M，int row_Im_In，int col_Im_In) { for(int r= row_Im_In+1；r< M.length；( r++) {if( == 't')返回true；}返回false；}// isTaken /* displayMatches *对于(int r=M.M.length 1；r> -1；r-){ for(int c= 0；c< M.length；c++) {if( == t‘){ System.out.println(MatchFromr +“与”+MatchToc匹配)；}// end displayMatches }// end类声明

预期成果：

Case 1: No mathing exists. 

There is no matching.


Case 2: Matching with no backtracking needed. 

A matches to b
B matches to a
C matches to c
D matches to d
E matches to e


Case 3: Matching with backtracking. 

A matches to a
B matches to d
C matches to b
D matches to c
E matches to e

Answer 1

您需要用以下内容替换findMatch：

public static boolean findMatch(char [][]M, int myRow)
{           
        if(myRow < 0)
            return true;            

        for(int c = 0; c < M.length; c++)
        {
            if(M[myRow][c] == 'y' && !isTaken(M, myRow, c))
            {
                M[myRow][c] = 't';
                if (findMatch(M, myRow-1))
                    return true;
                M[myRow][c] = 'y';
            }
        }
        return false;

}

目前，您的代码将只尝试为每个元素找到第一个可能的匹配项。

要执行正确的回溯，您需要从循环内部调用递归函数，如果它找不到完全匹配，则需要测试下一个位置。