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

Question

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

根据柯尼格定理，存在一个与最大匹配(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边，最小顶点覆盖返回200顶点。因为这是一个二部图，这些数字不应该不同(因为定理)。也许你能帮我，告诉我我错在哪里。提前感谢!!

(Student's和Project's是我在二部图中的两种顶点)

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类的实现中。

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