二部图中最小顶点覆盖的实现

Question

我有一个相当大的二分图（每个部分大约有 200 个顶点，中间通常有 20,000 条或更多条边），我试图在其中找到最小顶点覆盖，因为我正在寻找一个两部分顶点之间的赋值。

根据Koenig定理，存在这样一个覆盖，其大小与最大匹配(https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))的基数相同。

我已经实现了 Hopcroft Karp 算法，该算法为我提供了最大匹配。如果需要，我可以提供我的实现，但我怀疑这就是我的问题所在。

实际问题是什么？
我怀疑我的实现，摘自上面的维基百科文章 (https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)#Constructive_proof)，有一个错误，但在检查它几个小时后，我无法找到错误的原因：虽然 Hopcroft Karp 算法找到了一个最大匹配 192 个边，最小顶点覆盖 returns 200 个顶点。由于这是一个二部图，这些数字不应该不同（因为定理）。也许你可以帮助我，告诉我我的错误在哪里。提前致谢！！

（Student和Project是我在二分图中的两种顶点）

internal static List<Vertex> FindMinimumVertexCover(IReadOnlyList<Edge> matching, IReadOnlyList<Vertex> studentVertices, IReadOnlyList<Vertex> projectVertices)
    {
        var unmatchedStudentNodes = studentVertices.Except(matching.Select(e => e.GetStudentVertex())).ToList();
        var visitedVertices = new List<Vertex>();
        var edgeComparer = new EdgeComparer();

        foreach (var unmatchedStudentNode in unmatchedStudentNodes)
        {
            visitedVertices = visitedVertices.Union(FindAlternatingNodes(matching, unmatchedStudentNode, visitedVertices, edgeComparer)).ToList();
        }

        visitedVertices = unmatchedStudentNodes.Union(visitedVertices).ToList();

        return studentVertices.Except(visitedVertices).Union(projectVertices.Intersect(visitedVertices)).ToList();
    }

private static List<Vertex> FindAlternatingNodes(IReadOnlyList<Edge> matching, Vertex initialVertex, List<Vertex> visitedVertices, EdgeComparer edgeComparer)
    {
        if (visitedVertices.Contains(initialVertex))
            return Enumerable.Empty<Vertex>().ToList();

        visitedVertices.Add(initialVertex);
        List<Edge> unmatchedEdges = initialVertex.Edges.Except(matching, edgeComparer).ToList();

        foreach (Edge unmatchedEdge in unmatchedEdges)
        {
            Vertex visitedVertex = unmatchedEdge.GetProjectVertex();
            Edge matchedEdge = matching.SingleOrDefault(e => e.GetProjectVertex().Equals(visitedVertex));

            if (matchedEdge != default(Edge))
            {
                visitedVertices.Add(visitedVertex);
                visitedVertex = matchedEdge.GetStudentVertex();
                visitedVertices = visitedVertices.Union(FindAlternatingNodes(matching, visitedVertex, visitedVertices, edgeComparer)).ToList();
            }
        }

        return visitedVertices;
    }

class EdgeComparer : IEqualityComparer<Edge>
{
    public bool Equals(Edge x, Edge y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x is null || y is null)
            return false;

        return Object.ReferenceEquals(x.GetStudentVertex(), y.GetStudentVertex()) && Object.ReferenceEquals(x.GetProjectVertex(), y.GetProjectVertex());
    }

    public int GetHashCode(Edge edge)
    {
        return (Student: edge.GetStudentVertex(), Project: edge.GetProjectVertex()).GetHashCode();
    }
}

Answer 1

我现在找到问题了。我要感谢@David Eisenstat，因为他建议重复生成小的随机图。

问题出在我执行 Vertex class。

每次我创建 Edge class 的实例时，我也会将该边添加到相应的顶点（这意味着我有效地获得了对边的 3 个引用）。再次调用外部算法（调用上面的方法）只会重新创建边列表，但会完整保留顶点中的旧引用。因此，后续调用并没有重新开始，最小顶点覆盖发现图中不再存在的边（即 List<Edge> unmatchedEdges = initialVertex.Edges.Except(matching, edgeComparer).ToList(); 行）。

二部图中最小顶点覆盖的实现

Implementation of Minimum Vertex Cover in a Bipartite Graph

c#

algorithm

graph-algorithm