0

我正在使用 QuickGraph 创建一个有向无环图。我需要找到所有入度为零的顶点。我没有在图形的Vertices集合上看到这种支持，也没有看到使用 LINQ 进行过滤的方法。

这是我正在编写的示例数据结构：

var componentGraph = new AdjacencyGraph<Component, Edge<Component>>();

var serverOnMachineA = new TalismaServerComponent("CLTDEPAPI10");
var serverOnMachineB = new TalismaServerComponent("CLTDEPAPI11");
var appServerOnMachineB = new TalismaAppServerComponent("CLTDEPAPI11");
var webComponentsOnMachineC = new TalismaWebComponentsComponent("CLTDEPFE1");

componentGraph.AddVertex(serverOnMachineA);
componentGraph.AddVertex(serverOnMachineB);
componentGraph.AddVertex(appServerOnMachineB);
componentGraph.AddVertex(webComponentsOnMachineC);

componentGraph.AddEdge(new Edge<Component>(appServerOnMachineB, serverOnMachineA));
componentGraph.AddEdge(new Edge<Component>(webComponentsOnMachineC, appServerOnMachineB));
componentGraph.AddEdge(new Edge<Component>(webComponentsOnMachineC, serverOnMachineB));

我只需要此图中没有“入”边（入度 = 0）的顶点列表。

4

1 回答 1

2

您可能需要不同的图表类型。深入了解 QuickGraph 的论坛和来源，我发现了BidirectionalGraph类，它是

一种可变的有向图数据结构，对于需要枚举出边和入边的稀疏图表示有效。需要两倍于邻接图的内存。

IBidirectionalIncidenceGraph正如讨论所暗示的那样，检索入度的方法似乎可以在 上找到。

您使用的数据结构不会对传入边进行簿记，因此您必须通过遍历所有边并查看它们的目标来检索顶点的入度，这对于大图来说可能是一项昂贵的操作。

这样BidirectionalGraph做更快，但记账需要两倍的内存空间。使用它，您可以执行以下操作：

var orphans = graph.Vertices.Where(v => graph.InDegree(v) == 0)
于 2014-09-01T14:46:54.300 回答