問題タブ [graph-traversal]

タイトルにあるように、私の反復的な深さ制限検索は次善のパスを返します。

これは割り当て用ではありません。BFS と比較して IDLS がどのように機能するかに興味がある

明らかに私が見落としているものがありますが、私のコードは最適なパスを返しません。また、設定された制限 (反復なし) で実行すると、最適な値またはそのすぐ上にパスが返されません。

ノードの内容: state、pathCost、ソリューション (パス)

コードは次のとおりです。

BasicBlockLLVM フレームワークで a の前任者を取得する最も簡単な方法は何ですか?

DepthFirstIteratorとを見てみましたidf_iterator<BasicBlock*>が、実際には制御フロー グラフで幅優先検索を行う必要があります。

これは簡単だと思いますが、ドキュメントやオンラインで調べた例からは明らかではありません。

完了した宿題があり、100 点中約 3 点が次の質問に対するものです。

「有向グラフ上に DFS ツリーを構築するとします。その後、バック エッジがないことに気付きます。これはグラフについて何を示しているでしょうか?」

私はこれについていくつか考えましたが、これは、グラフをトポロジー的に横断する特定のパスが 1 つだけ存在するという暗黙の依存関係があることを意味するということだけを推論できます。残念ながら、ウェブ上のどこにもこれに関する情報を見つけることができなかったので、ここに回答を投稿して、誰かがその（不）正確性について検討できるかどうかを確認したいと思いました. この問題の解決に役立つ可能性のある追加の考えや指針があればお知らせください。

本当にありがとう！

有向 networkx グラフを介してランダム トラバーサルをシミュレートしようとしています。擬似コードは次のとおりです

一時的なリストを作成し、訪問済みとしてマークされている場合は要素を削除する以外に、パスを移動済みとしてマークするより効率的な方法はありますか?

編集

このアルゴリズムの目的は、グラフ内のノードをランダムに選択することです。そのノードの後継者/子をランダムに選択します。未訪問の場合は、そこに移動して訪問済みとしてマークします。後続者/子がなくなるか、未訪問の後続者/子がなくなるまで繰り返します。

Data Structures and Algorithms in C++ 4e (By Adam Drozdek) のグラフに関連する資料を読んでいます。彼の Graph Breadth First Search の実装では、疑似コードは次のようになります。

基本的に、グラフの実装では、すべての頂点のセットとすべてのエッジのセットを既に保持しています。BFS では、アルゴリズムは最初に、このセットでアクセスされていないすべての頂点を列挙して、完全なグラフをトラバースします。

私の質問は、すべての頂点を既にセットに格納しているため、BFS アルゴリズムを使用せずにセットをループして特定の頂点を操作できるということです。グラフ走査アルゴリズムが必要な理由と主な用途は何ですか?

neo4j java-rest-binding プロジェクトを使用してトラバーサル フレームワークを実装しています。コードは次のとおりです。

コードでコメントされているように、3 つのタスクを実行する必要があります。

1. ノード番号に関連するすべてのノード ID を出力します。21
2. ノード番号に関連するすべての関係 ID を出力します。21
3. ノード番号に関連するすべてのパスをトラバースします。21

タスク 1 と 2 は正常に動作しています。しかし、3番目のタスクでやろうとするとtraverser.iterator()、次のような例外がスローされます:

なぜこれが起こっているのか、または私が間違っている場合は、それを行う正しい方法は何かを誰でも確認できますか. 前もって感謝します。

次のようなグラフがあります。

開始点（たとえば「B」）を指定すると、開始点に最も近い優先順位でグラフをトラバースするJavaScript関数を作成する必要があります。たとえば、B の場合、子 D、F、ルート、兄弟 B、C、孫 G、B と C の子などを取得します。

アルゴリズムさえあればいい

PS: ダイクストラを使用できることは知っていますが、その方法がわかりません。

特定の基準に基づいて、すべてのノードをトラバースし、すべてのノード (およびその関係と接続されたノード) を削除する必要があります。テスト目的で (トラバース中にノードを削除できることを確認するため)、トラバースの途中で 1 つのノードを削除し、別のトラバーサルを使用してそのノードに接続されているすべてのノードと関係を削除しようとしています。すべてのノードと関係を削除できますが、その後、ループが最初のトラバーサルに戻ったときに IllegalStateException (ノードが削除されました) が発生します。トラバース中にノード/関係を削除することは可能ですか? もしそうなら、すべてのノードをトラバースし、途中でいくつかのノードを削除する効果的な方法は何ですか? 前もって感謝します！