需要一些帮助来理解这个用于图匹配的代码

Question

代码可以在这里找到：https://sites.google.com/site/indy256/algo/kuhn_matching2 更具体地说，我不确定int n2是用来做什么的以及它是如何被使用的。

- user2923535

---

你为什么认为“在集合n2中的顶点大于或等于（n1 + 1），但小于或等于（n1 + n2）。”？如果我理解正确，你的输入应该是“3 3 3 0 0 1 1 2 0”，至少这是程序作者所假设的。 - Alex Pakka

我认为这不会解决你的问题，请看下面我的回答。该算法使用0索引数组，增加匹配大小将使算法偏斜。按照我展示的方式转换输入，然后在需要时转换输出要容易得多。至于打印，你只需要理解maxMatching方法结束时匹配包含什么即可。 - Alex Pakka

matching 包含了从 n2 出发计入最大匹配的每条边对应到 n1 中的顶点的索引，如果该顶点不计入，则值为 -1。请注意，所有的索引都是从 0 开始的。在你提供的原始示例（在你改动 main 方法之前），matching 的值为 [0,-1,1]，即 “coding 可以由 John 完成，QA 没有人负责，支持由 Bob 负责”。也就是说，这里是反过来的。你可以像这样输出： System.out.println(Arrays.toString(matching)); - 那么你就不需要循环了。祝你好运。你正在做的事情需要对数组、索引以及一些图形和集合有很好的理解。 - Alex Pakka

@AlexPakka 我现在明白了。非常感谢你的帮助！ - user2923535

Answer 1

在这里，对于二分图，n1表示第一组（划分）的顶点数，n2表示第二组的顶点数。例如，你可能会有一组工人和一组他们要执行的任务。在上面的例子中，有两个工人（比如John=0和Bob=1）和三个任务（比如coding=0，QA=1，support=2）。John可以编码和支持，Bob只能支持。他们都不能做QA（没有g[i]==1）。

然后，该算法遵循Kuhn的建议，找到最大匹配（不要与极大匹配混淆）。在我们的示例中，最大匹配有两条边（例如，John->coding和Bob->support）。

该算法不适用于加权二分图。 更新 为了适应问题中的输入规则，需要进行以下操作。只需确保在 g[x]=y 中：0 <= x < n1 且 0 <= y < n2。

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n1 = sc.nextInt();
  int n2 = sc.nextInt();
  int m = sc.nextInt();
  LinkedList<Integer>[] g = new LinkedList[n1];
  for (int j = 0; j < n1; j++) {
    g[j] = new LinkedList<Integer>();
  }
  int i = 0;
  while(i != m){
    int v = sc.nextInt();
    int v2 = sc.nextInt();
    if(v>=1 && v<=n1) { 
        //v belongs in first set 
        g[v-1].add(v2-n1-1);
    }else if(v>=n1+1 && v<=n1+n2) { 
        //v belongs in the second set, v2 into the first
        g[v2-1].add(v-n1-1);
    }
    i++;
  }
  System.out.println(maxMatching(g, n2));
}

- Alex Pakka

---

好的。我只是在玩弄这段代码，并想修改边缘的输入。我将主方法更改为我在主帖中发布的内容，但出现了一些错误。 - user2923535

顶点是从0开始索引的。当n1==n2==3时，最大索引为2。如果我回答了你的问题，请标记它。 - Alex Pakka