5

C# の QuickGraph を使用して無向加重グラフの新しいインスタンスを作成する方法を理解しようとしています。

私の目標は、ランダムな数のノードと、幅優先探索アルゴリズムを使用して最短経路を見つけることができるランダムに生成された開始ノードと終了ノードが入力された無向加重グラフを作成することです。

ドキュメンテーションにはあまりないので、誰かが助けてくれれば幸いです。

4

3 に答える 3

2

リチャード、QuickGraph はあなたに代わってこれを行うわけではありません。あなたが購読できるイベントを利用できるようにするだけです。これらのイベントをサブスクライブすることで、それに応じて対応できます。確かに、Depth First Search に関する QuickGraph ドキュメントが不足していることから (はい、DFS ではなく BFS を実行していることは認識していますが、イベントをサブスクライブする方法の概念は同じです):

  1. 計算を開始する前に各頂点で呼び出される InitializeVertex
  2. 頂点が初めて検出されたときに呼び出される DiscoverVertex
  3. ExamineEdge は、検出された後、各頂点のすべてのアウトエッジで呼び出されます。
  4. 検索ツリーを形成するエッジのメンバーになると、各エッジで呼び出されます。
  5. FinishVertex は、頂点のすべてのアウト エッジが検索ツリーに追加され、すべての隣接する頂点が検出された後 (ただし、アウト エッジが検査される前) に呼び出されます。

ところで、Reflector を開いて QuickGraph.Algorithms.Observers を見てみましょう。また、最短パスの要件は、BFS とは異なる方法で簡単になります。

于 2011-06-14T14:27:04.743 に答える
1

このアルゴリズムのドキュメントはまだありません。しかし、次善の策 (または、さらに優れたもの) があります: 単体テストです!

QuickGraph ソースをダウンロードして を見つけるとBreadthFirstAlgorithmSearchTest.BreadthFirstSearchAll()、テスト プロジェクト内のすべての有向グラフで BFS を実行するアルゴリズムの使用例が表示されます。

于 2010-08-02T20:42:19.050 に答える