引言
最小顶点覆盖（Minimum Vertex Cover）是图论中的经典NP-hard问题：寻找一个最小的顶点集合，使得图中的每条边至少有一个端点在该集合中。然而，当图限制为二分图时，该问题可以在多项式时间内求解——这便是著名的Kőnig定理，它揭示了二分图中最小顶点覆盖的大小等于最大匹配的大小。本文将用Java实现基于匈牙利算法的二分图最小顶点覆盖求解，并展示其在游戏开发中监控点最优布局、资源冲突检测等场景中的应用。
算法核心思想
Kőnig定理
对于任意二分图 G = (U, V, E)：
– 最大匹配的大小 = 最小顶点覆盖的大小
这意味着我们可以通过求最大匹配来间接获得最小顶点覆盖的大小，再通过交替树标记法构造出具体的最小顶点覆盖集合。
从最大匹配构造最小顶点覆盖
- 求最大匹配：使用匈牙利算法（Hopcroft-Karp算法更优，但匈牙利更易理解）。
- 构建交替树：
- 从U侧所有未匹配的顶点出发，沿”未匹配边→匹配边→未匹配边→…”的交替路径进行BFS/DFS。
- 标记所有访问到的顶点。
- 构造覆盖集：
- 最小顶点覆盖 = (U侧未被标记的顶点) ∪ (V侧被标记的顶点)
匈牙利算法（二分图最大匹配）
采用DFS增广路策略：对于U侧每个顶点，尝试找到一条增广路（从未匹配点出发，交替经过非匹配边和匹配边，最终到达V侧未匹配点的路径）。找到增广路后，将路径上的匹配状态翻转。
Java实现
import java.util.*;
/**
* 二分图最小顶点覆盖
* 基于Kőnig定理：最小顶点覆盖大小 = 最大匹配大小
* 使用匈牙利算法求最大匹配，再通过交替树标记构造覆盖集
*/
public class MinimumVertexCover {
// 二分图结构
static class BipartiteGraph {
int nLeft; // 左侧顶点数
int nRight; // 右侧顶点数
List<Integer>[] adj; // 左侧顶点到右侧的邻接表
@SuppressWarnings("unchecked")
public BipartiteGraph(int nLeft, int nRight) {
this.nLeft = nLeft;
this.nRight = nRight;
this.adj = new ArrayList[nLeft];
for (int i = 0; i < nLeft; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int u, int v) {
// u ∈ [0, nLeft), v ∈ [0, nRight)
adj[u].add(v);
}
}
private BipartiteGraph graph;
private int[] matchR; // matchR[v] = u 表示右侧v与左侧u匹配
private boolean[] seen; // DFS访问标记
public MinimumVertexCover(BipartiteGraph graph) {
this.graph = graph;
this.matchR = new int[graph.nRight];
Arrays.fill(matchR, -1);
}
/**
* 匈牙利算法：求二分图最大匹配
*/
public int maxMatching() {
int result = 0;
// 对左侧每个顶点尝试找增广路
for (int u = 0; u < graph.nLeft; u++) {
seen = new boolean[graph.nRight];
if (dfs(u)) {
result++;
}
}
return result;
}
/**
* DFS找从u出发的增广路
*/
private boolean dfs(int u) {
for (int v : graph.adj[u]) {
if (seen[v]) continue;
seen[v] = true;
// 如果v未匹配，或者v的匹配点能找到新的匹配
if (matchR[v] < 0 || dfs(matchR[v])) {
matchR[v] = u;
return true;
}
}
return false;
}
/**
* 获取左侧各顶点的匹配对象（-1表示未匹配）
*/
public int[] getLeftMatches() {
int[] matchL = new int[graph.nLeft];
Arrays.fill(matchL, -1);
for (int v = 0; v < graph.nRight; v++) {
if (matchR[v] >= 0) {
matchL[matchR[v]] = v;
}
}
return matchL;
}
/**
* 使用交替树标记法构造最小顶点覆盖
* @return [leftCover, rightCover] 分别是两侧选入覆盖集的顶点列表
*/
public List<List<Integer>> findMinimumVertexCover() {
int maxMatch = maxMatching();
System.out.println("最大匹配大小: " + maxMatch);
int[] matchL = getLeftMatches();
// Step 1: 从U侧未匹配顶点出发，沿交替路径DFS标记
boolean[] visitedLeft = new boolean[graph.nLeft];
boolean[] visitedRight = new boolean[graph.nRight];
for (int u = 0; u < graph.nLeft; u++) {
if (matchL[u] == -1 && !visitedLeft[u]) {
alternatingDfs(u, visitedLeft, visitedRight, matchL, true);
}
}
// Step 2: 构造最小顶点覆盖
// 覆盖集 = U侧未被标记的顶点 + V侧被标记的顶点
List<Integer> leftCover = new ArrayList<>();
List<Integer> rightCover = new ArrayList<>();
for (int u = 0; u < graph.nLeft; u++) {
if (!visitedLeft[u]) {
leftCover.add(u);
}
}
for (int v = 0; v < graph.nRight; v++) {
if (visitedRight[v]) {
rightCover.add(v);
}
}
return Arrays.asList(leftCover, rightCover);
}
/**
* 交替路径DFS
* fromLeft: 当前是否在左侧
* 如果在左侧：只能走非匹配边到右侧
* 如果在右侧：只能走匹配边到左侧
*/
private void alternatingDfs(int u, boolean[] visitedLeft, boolean[] visitedRight,
int[] matchL, boolean fromLeft) {
if (fromLeft) {
visitedLeft[u] = true;
for (int v : graph.adj[u]) {
// 只能走非匹配边
if (matchL[u] == v) continue; // 这是匹配边，跳过
if (!visitedRight[v]) {
alternatingDfs(v, visitedLeft, visitedRight, matchL, false);
}
}
} else {
// 在右侧，只能走匹配边到左侧
visitedRight[u] = true;
int matchedU = matchR[u];
if (matchedU >= 0 && !visitedLeft[matchedU]) {
alternatingDfs(matchedU, visitedLeft, visitedRight, matchL, true);
}
}
}
/**
* 验证顶点覆盖的合法性
*/
public boolean verifyVertexCover(List<Integer> leftCover, List<Integer> rightCover) {
Set<Integer> coverL = new HashSet<>(leftCover);
Set<Integer> coverR = new HashSet<>(rightCover);
for (int u = 0; u < graph.nLeft; u++) {
for (int v : graph.adj[u]) {
if (!coverL.contains(u) && !coverR.contains(v)) {
return false; // 边(u,v)未被覆盖
}
}
}
return true;
}
// ========== 游戏应用：监控点最优布局 ==========
/**
* 游戏场景：在地图中放置最少数量的监控塔，覆盖所有通道
*
* 地图建模为网格图，将交叉点分为棋盘的两色（二分图）
* 每条通道是连接两个交叉点的边
* 最小顶点覆盖 = 需要放置监控塔的最少交叉点
*/
static class GameMapSurveillance {
int width, height;
boolean[][] isCorridor; // true表示该格子是通道
public GameMapSurveillance(int width, int height) {
this.width = width;
this.height = height;
this.isCorridor = new boolean[height][width];
}
public void addCorridor(int x, int y) {
isCorridor[y][x] = true;
}
/**
* 将地图通道交叉点建模为二分图
* 使用棋盘着色：根据 (x+y)%2 将顶点分为左右两部分
*/
public BipartiteGraph buildBipartiteGraph() {
// 给每个通道格子分配ID
int[][] id = new int[height][width];
int leftCount = 0, rightCount = 0;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (isCorridor[y][x]) {
if ((x + y) % 2 == 0) {
id[y][x] = leftCount++;
} else {
id[y][x] = rightCount++;
}
} else {
id[y][x] = -1;
}
}
}
BipartiteGraph g = new BipartiteGraph(leftCount, rightCount);
int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (!isCorridor[y][x] || (x + y) % 2 != 0) continue;
int u = id[y][x];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < width && ny >= 0 && ny < height
&& isCorridor[ny][nx]) {
int v = id[ny][nx];
g.addEdge(u, v);
}
}
}
}
return g;
}
/**
* 计算监控点最优布局并打印地图
*/
public void solveAndPrint() {
BipartiteGraph g = buildBipartiteGraph();
MinimumVertexCover mvc = new MinimumVertexCover(g);
List<List<Integer>> cover = mvc.findMinimumVertexCover();
List<Integer> leftCover = cover.get(0);
List<Integer> rightCover = cover.get(1);
// 重建ID映射
int[][] id = new int[height][width];
int leftCount = 0, rightCount = 0;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (isCorridor[y][x]) {
if ((x + y) % 2 == 0) {
id[y][x] = leftCount++;
} else {
id[y][x] = rightCount++;
}
}
}
}
Set<Integer> coverL = new HashSet<>(leftCover);
Set<Integer> coverR = new HashSet<>(rightCover);
System.out.println("地图布局 (C=通道, T=监控塔, .=空地):");
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (!isCorridor[y][x]) {
System.out.print(". ");
} else {
int vid = id[y][x];
boolean isCover = ((x + y) % 2 == 0 && coverL.contains(vid))
|| ((x + y) % 2 == 1 && coverR.contains(vid));
System.out.print(isCover ? "T " : "C ");
}
}
System.out.println();
}
System.out.println("监控塔数量: " + (leftCover.size() + rightCover.size()));
}
}
public static void main(String[] args) {
System.out.println("=== 最小顶点覆盖基础测试 ===");
// 测试1：经典二分图
// 0 --- 0
// | |
// 1 --- 1
// | |
// 2 --- 2
BipartiteGraph g1 = new BipartiteGraph(3, 3);
g1.addEdge(0, 0); g1.addEdge(0, 1);
g1.addEdge(1, 0); g1.addEdge(1, 1); g1.addEdge(1, 2);
g1.addEdge(2, 1); g1.addEdge(2, 2);
MinimumVertexCover mvc1 = new MinimumVertexCover(g1);
List<List<Integer>> cover1 = mvc1.findMinimumVertexCover();
System.out.println("左侧覆盖顶点: " + cover1.get(0));
System.out.println("右侧覆盖顶点: " + cover1.get(1));
System.out.println("验证覆盖: " + mvc1.verifyVertexCover(cover1.get(0), cover1.get(1)));
// 测试2：星型图
System.out.println("\n=== 星型图测试 ===");
BipartiteGraph g2 = new BipartiteGraph(1, 5);
for (int i = 0; i < 5; i++) g2.addEdge(0, i);
MinimumVertexCover mvc2 = new MinimumVertexCover(g2);
List<List<Integer>> cover2 = mvc2.findMinimumVertexCover();
System.out.println("左侧覆盖: " + cover2.get(0));
System.out.println("右侧覆盖: " + cover2.get(1));
System.out.println("验证覆盖: " + mvc2.verifyVertexCover(cover2.get(0), cover2.get(1)));
// 测试3：游戏地图监控布局
System.out.println("\n=== 游戏地图监控最优布局 ===");
GameMapSurveillance map = new GameMapSurveillance(8, 6);
// 设计一个迷宫式通道布局
int[][] corridors = {
{1,1}, {2,1}, {3,1}, {4,1}, {5,1},
{1,2}, {3,2}, {5,2},
{1,3}, {2,3}, {3,3}, {4,3}, {5,3}, {6,3},
{3,4}, {6,4},
{1,4}, {2,4}, {3,4}, {4,4}
};
for (int[] c : corridors) {
map.addCorridor(c[0], c[1]);
}
map.solveAndPrint();
// 测试4：Kőnig定理验证
System.out.println("\n=== Kőnig定理验证 ===");
BipartiteGraph g3 = new BipartiteGraph(4, 4);
g3.addEdge(0, 0); g3.addEdge(0, 1);
g3.addEdge(1, 1); g3.addEdge(1, 2);
g3.addEdge(2, 2); g3.addEdge(2, 3);
g3.addEdge(3, 0); g3.addEdge(3, 3);
MinimumVertexCover mvc3 = new MinimumVertexCover(g3);
int matchSize = mvc3.maxMatching();
List<List<Integer>> cover3 = mvc3.findMinimumVertexCover();
int coverSize = cover3.get(0).size() + cover3.get(1).size();
System.out.println("最大匹配: " + matchSize);
System.out.println("最小顶点覆盖: " + coverSize);
System.out.println("Kőnig定理成立: " + (matchSize == coverSize));
}
}
复杂度分析
- 匈牙利算法（DFS增广路）：
- 时间复杂度：O(V · E)，其中V是左侧顶点数，E是边数。
- 对于稠密图，可使用Hopcroft-Karp算法优化至O(√V · E)。
- 交替树标记：O(V + E)。
- 整体最小顶点覆盖求解：O(V · E)。
- 空间复杂度：O(V + E)。
总结
Kőnig定理将二分图的最小顶点覆盖问题优雅地转化为最大匹配问题，使得这一NP-hard问题在二分图限制下获得了多项式时间解法。本文通过匈牙利算法求得最大匹配，再利用交替树标记构造出具体的最小覆盖集，完整展现了从理论到实现的完整链条。在游戏开发中，这一算法可广泛应用于监控点布局、资源冲突消解、任务分配中的最少约束选择等场景。对于更大规模的图，可将匈牙利算法替换为Hopcroft-Karp算法以获得更优的渐进复杂度。
