5

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

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

文档不多，所以如果有人能提供任何帮助，将不胜感激。

4

3 回答 3

2

Richard，QuickGraph 不会为您做任何这些，它只会提供您可以订阅的事件。通过订阅这些事件，您可以做出相应的响应。从公认缺乏关于深度优先搜索的 QuickGraph 文档（是的，我意识到您正在做 BFS 而不是 DFS，但如何订阅事件的概念是相同的）：

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

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

于 2011-06-14T14:27:04.743 回答
1

还没有这个算法的文档；但是还有下一个最好的东西（或者甚至是更好的东西）：单元测试！

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

于 2010-08-02T20:42:19.050 回答
1

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

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

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

这是一个完整的例子：

UndirectedGraph<string, Edge<string>> g = new UndirectedGraph<string, Edge<string>>();

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

var algo = new UndirectedBreadthFirstSearchAlgorithm<string, Edge<string>>(g);

var observer = new UndirectedVertexPredecessorRecorderObserver<string, Edge<string>>();

var rootVertex = "0";
using (observer.Attach(algo))
{
    algo.Compute(rootVertex);
}

var targetVertex = "3";
bool foundPath = observer.TryGetPath(targetVertex, out IEnumerable<Edge<string>> path);

path 然后将包含两条边：

[0]: "0"->"2"
[1]: "2"->"3"
于 2020-01-24T17:41:58.483 回答