在 QuickGraph 中 - 是否有用于查找一组顶点的所有父项(直到根顶点)的算法。换句话说,所有在它们下方某处(在通往叶节点的路上)一个或多个顶点输入的顶点。因此,如果顶点是节点,而边是依赖关系,则找到将受给定节点集影响的所有节点。
如果不是,编写自己的算法有多难?
最佳答案
这是我用来在给定顶点上完成前驱搜索的方法:
IBidirectionalGraph<int, IEdge<int>> CreateGraph(int vertexCount)
{
BidirectionalGraph<int, IEdge<int>> graph = new BidirectionalGraph<int, IEdge<int>>(true);
for (int i = 0; i < vertexCount; i++)
graph.AddVertex(i);
for (int i = 1; i < vertexCount; i++)
graph.AddEdge(new Edge<int>(i - 1, i));
return graph;
}
static public void Main()
{
IBidirectionalGraph<int, IEdge<int>> graph = CreateGraph(5);
var dfs = new DepthFirstSearchAlgorithm<int, IEdge<int>>(graph);
var observer = new VertexPredecessorRecorderObserver<int, IEdge<int>>();
using (observer.Attach(dfs)) // attach, detach to dfs events
dfs.Compute();
int vertexToFind = 3;
IEnumerable<IEdge<int>> edges;
if (observer.TryGetPath(vertexToFind, out edges))
{
Console.WriteLine("To get to vertex '" + vertexToFind + "', take the following edges:");
foreach (IEdge<int> edge in edges)
Console.WriteLine(edge.Source + " -> " + edge.Target);
}
}
请注意,如果您事先知道您的根,则可以在 dfs.Compute()
方法中指定它(即 dfs.Compute(0)
)。
-道格
关于c# - QuickGraph - 是否有用于查找一组顶点的所有父项(直到根顶点)的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2719052/