用js写一个匈牙利最优匹配算法

匈牙利算法是一种求解二分图最大匹配问题的经典算法。它的基本思想是利用增广路不断扩展当前的匹配，直到无法再找到增广路为止。下面是使用 JavaScript 实现的匈牙利算法：

function hungarianAlgorithm(matrix) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;
  
  // 初始化匹配
  const matching = new Array(numCols).fill(-1);
  
  // 定义辅助函数：寻找增广路
  function findAugmentingPath(startRow, visitedCols) {
    for (let j = 0; j < numCols; j++) {
      if (matrix[startRow][j] && !visitedCols.has(j)) {
        visitedCols.add(j);
        const nextRow = matching[j];
        if (nextRow === -1 || findAugmentingPath(nextRow, visitedCols)) {
          matching[j] = startRow;
          return true;
        }
      }
    }
    return false;
  }
  
  // 开始匹配
  for (let i = 0; i < numRows; i++) {
    findAugmentingPath(i, new Set());
  }
  
  // 计算匹配权重
  let weight = 0;
  for (let j = 0; j < numCols; j++) {
    if (matching[j] !== -1) {
      weight += matrix[matching[j]][j];
    }
  }
  
  return { matching, weight };
}

输入参数 `matrix` 是一个二维矩阵，表示二分图的邻接矩阵。输出结果是一个对象，包含两个属性：

- `matching`：表示最优匹配方案，是一个长度为 `numCols` 的数组，每个元素表示与该列匹配的行号（如果该列没有匹配则为 -1）。
- `weight`：表示最优匹配的权重和。

例如，下面是一个简单的使用示例：

const matrix = [
  [4, 2, 0],
  [2, 0, 1],
  [3, 2, 4],
];
const result = hungarianAlgorithm(matrix);
console.log(result); // { matching: [0, 2, 1], weight: 3 }

该示例表示一个三行三列的二分图，邻接矩阵为：

4 2 0
2 0 1
3 2 4

按照匈牙利算法，最优匹配方案为第一列与第一行匹配，第二列与第三行匹配，第三列与第二行匹配，匹配权重和为 3。