二分图Minimum Vertex Cover实现bug排查：最大匹配与覆盖基数不符

你的代码存在4个核心逻辑错误，均不符合Kőnig定理构造最小顶点覆盖的交替路径遍历规则：

错误1：交替路径遍历逻辑缺失未匹配右侧顶点的标记 #

当前代码通过非匹配边走到右侧Project顶点后，只有该顶点存在匹配边时才会将其加入已访问集合，未匹配的右侧顶点会被直接跳过，不符合交替路径可达顶点的标记要求：所有从左侧未匹配点出发、沿交替路径能走到的所有顶点（无论左右侧、无论是否匹配）都需要被标记。

错误2：已访问集合重复合并导致逻辑混乱 #

你在FindAlternatingNodes方法内部直接修改传入的已访问列表，同时又将返回值和原有列表做Union合并，会导致节点重复统计，遍历逻辑混乱，且多次ToList操作会大幅降低性能。

错误3：多余的未匹配左侧节点合并操作 #

遍历完所有未匹配学生节点后，额外执行的visitedVertices = unmatchedStudentNodes.Union(visitedVertices).ToList()完全多余，遍历初始就已经把这些未匹配学生节点加入了已访问集合，重复操作可能引入未知问题。

错误4：匹配边查询效率极低 #

每次查找项目对应的匹配边都调用matching.SingleOrDefault，时间复杂度为O(n)，在边数较多的场景下性能损耗非常大。

修复后的代码 #

调整点说明 #

• 改用HashSet<Vertex>存储已访问节点，避免重复，提升查询性能
• 修正交替路径遍历逻辑：走到右侧顶点后无论是否匹配都先标记为已访问，存在匹配边时再沿匹配边递归遍历对应的左侧学生顶点
• 移除多余的集合合并操作，简化逻辑
• 预先构建项目到匹配边的映射字典，将匹配边查询复杂度从O(n)降到O(1)

internal static List<Vertex> FindMinimumVertexCover(IReadOnlyList<Edge> matching, IReadOnlyList<Vertex> studentVertices, IReadOnlyList<Vertex> projectVertices)
{
    // 预先建立项目到匹配边的映射，避免每次查询遍历整个匹配列表
    var projectToMatchEdge = matching.ToDictionary(e => e.GetProjectVertex());
    var unmatchedStudents = studentVertices.Except(matching.Select(e => e.GetStudentVertex())).ToHashSet();
    var visited = new HashSet<Vertex>();
    var edgeComparer = new EdgeComparer();

    foreach (var student in unmatchedStudents)
    {
        TraverseAlternatingPath(student, matching, projectToMatchEdge, edgeComparer, visited);
    }

    // Kőnig定理构造规则：左侧未访问顶点 + 右侧已访问顶点 = 最小顶点覆盖
    return studentVertices.Except(visited).Concat(projectVertices.Intersect(visited)).ToList();
}

private static void TraverseAlternatingPath(Vertex currentVertex, IReadOnlyList<Edge> matching, 
    Dictionary<Vertex, Edge> projectToMatchEdge, EdgeComparer edgeComparer, HashSet<Vertex> visited)
{
    if (visited.Contains(currentVertex))
        return;

    visited.Add(currentVertex);

    // 当前是左侧学生顶点，先走非匹配边到右侧项目顶点
    // 此处可替换为你自己的顶点类型判断逻辑，比如Vertex的Type属性等
    if (currentVertex.GetType() == typeof(Student)) 
    {
        var unmatchedEdges = currentVertex.Edges.Except(matching, edgeComparer);
        foreach (var edge in unmatchedEdges)
        {
            var project = edge.GetProjectVertex();
            TraverseAlternatingPath(project, matching, projectToMatchEdge, edgeComparer, visited);
        }
    }
    // 当前是右侧项目顶点，走匹配边到左侧学生顶点
    else
    {
        if (projectToMatchEdge.TryGetValue(currentVertex, out var matchedEdge))
        {
            var student = matchedEdge.GetStudentVertex();
            TraverseAlternatingPath(student, matching, projectToMatchEdge, edgeComparer, visited);
        }
    }
}

class EdgeComparer : IEqualityComparer<Edge>
{
    public bool Equals(Edge x, Edge y)
    {
        if (ReferenceEquals(x, y))
            return true;
        if (x is null || y is null)
            return false;
        return ReferenceEquals(x.GetStudentVertex(), y.GetStudentVertex()) 
               && ReferenceEquals(x.GetProjectVertex(), y.GetProjectVertex());
    }

    public int GetHashCode(Edge edge)
    {
        return HashCode.Combine(edge.GetStudentVertex(), edge.GetProjectVertex());
    }
}

内容的提问来源于stack exchange，提问作者DarkBarbarian