创建无向图并在 QuickGraph 中使用 BFS 遍历它

Question

我试图弄清楚如何使用 QuickGraph for C# 创建无向加权图的新实例。

我的目标是创建一个无向加权图，其中填充了随机数量的节点以及随机生成的起始和结束节点，其最短路径可以使用广度优先搜索算法找到。

文档内容不多，因此如果有人可以提供任何帮助，我们将不胜感激。

Answer 1

Richard，QuickGraph 不会为您执行任何操作，它只会提供您可以订阅的事件。通过订阅这些事件，您可以做出相应的回应。来自公认缺乏深度优先搜索的 QuickGraph 文档（是的，我知道你正在执行 BFS 而不是 DFS，但如何订阅事件的概念是相同的）：

1. InitializeVertex，在开始计算之前在每个顶点上调用，
2. DiscoverVertex ，在第一次遇到顶点时调用，
3. ExamineEdge，在发现顶点后在每个顶点的每个出边上调用，
4. TreeEdge，在每条边成为形成搜索树的边的成员时调用。
5. FinishVertex，在顶点的所有出边已添加到搜索树并且已发现所有相邻顶点（但在检查其出边之前）后在顶点上调用。

顺便说一下，打开 Reflector 并查看 QuickGraph.Algorithms.Observers。使用与 BFS 不同的方法，您的最短路径要求会更容易。

Answer 2

目前还没有该算法的文档；但还有下一个最好的事情（或者甚至更好的事情）：单元测试！

如果您下载 QuickGraph 源代码，并找到 BreadthFirstAlgorithmSearchTest.BreadthFirstSearchAll()，您将看到该算法的示例用法，该算法在测试项目中的所有有向图上运行 BFS。

Answer 3

Github 上有一个简短的帖子，其中有一个有用的基本示例，说明如何设置 BFS 并从中获取一些结果。

特定于您的应用程序的其他详细信息（创建随机图等）显然不属于此示例的一部分。

来源：
https://github.com/YaccConstructor/QuickGraph/issues/189#issuecomment- 487493207

这是一个完整的示例：

UndirectedGraph<字符串，边<字符串>>> g = new UndirectedGraph>();

g.AddVerticesAndEdge(new Edge("0", "1"));
g.AddVerticesAndEdge(new Edge("0", "2"));
g.AddVerticesAndEdge(new Edge("2", "3"));

var algo = new UndirectedBreadthFirstSearchAlgorithm<字符串，Edge<字符串>>(g);

var Observer = new UndirectedVertexPredecessorRecorderObserver>();

var rootVertex =“0”；
使用 (observer.Attach(algo))
{
    算法.Compute(rootVertex);
}

var 目标顶点 = "3";
bool findPath = Observer.TryGetPath(targetVertex, out IEnumerable> path);

路径将包含两条边：

[0]: "0"->"2"
[1]：“2”->“3”