問題タブ [graph-traversal]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
1 に答える
86 参照

c# - このシナリオに適したグラフ トラバーサル アルゴリズムはどれですか

次の種類のグラフをトラバースするのに問題があります。

トラバースするグラフ

  • 各ノードには、複数の入力と出力が存在する可能性があります。
  • 各出力は複数の入力に直接接続できます (たとえば、A の 3 番目の出力は C と D に送られます)。
  • 各ノードでは、入力で提供された値に基づいていくつかの計算が行われます。出力の結果は、他のノードの入力に提供されます。
  • あるノードから次のノードにトラバースするには、すべての入力の値を知る必要があります。

このトラバーサルが思い浮かびます:

  • A では、唯一の入力を使用してすべての出力を計算します。
  • A の最初の出力を使用して A から C に移動します。
  • C では、他の入力がわからないので、A に戻ります。
  • A で、2 番目の出力を使用して B に到達します。
  • B ではすべての入力がないため、A に戻ります。
  • A で 3 番目の出力を取り、B に到達します。
  • B には、出力を計算するためのすべての入力があります。
  • B で、最初の出力を経由して C に到達します。
  • C では、すべての入力があるので、計算を行い、E に到達します。
  • 等々

では、このシナリオで最適に機能すると思われるトラバーサル アルゴリズムはどれでしょうか。私の場合、ノードに到達したときにすべての入力がわからず、バックトラッキングができないため、BFS はおそらく機能しません。

これを C# で実装する必要があります。

0 投票する
0 に答える
402 参照

java - インドア ナビゲーションと経路探索におけるグラフ トラバーサルとフィルタリング

次のオプションのうち、(屋内) ナビゲーション システムのグラフ トラバーサル アルゴリズムで処理時間が短く/コストがかからないのはどれですか?

  1. 出発点と目的地 (グラフ上のノード) の間のすべての可能なパスを生成するには、フィルタリング メカニズムを適用して、ナビゲーション ユーザーの機能と好みに一致させます (グラフ上のすべてのパスを見つけて、車椅子ユーザーの階段を除外するなど)、または

  2. ユーザーのプロファイルがシステムで利用可能になるとすぐに、グラフをフィルタリングし、このユーザーが通過できないパスを除外してから、最短パス アルゴリズムを実行しますか?

0 投票する
1 に答える
141 参照

algorithm - 頂点とエッジに直接アクセスできるのに、なぜ BFS や DFS が必要なのですか?

グラフを使用して都市間マップを実装しています。無向なので、Graph クラスで頂点のベクトルと「辺の配列へのポインター」のベクトルを使用する上三角隣接行列を使用しました。

そのようなグラフをトラバースする必要があります。頂点には情報があり、エッジには重みが付けられています。

直接アクセスによってすべての頂点とエッジの情報を既に持っているのに、なぜこのようなトラバーサルで BFS や DFS が必要になるのでしょうか?

0 投票する
1 に答える
217 参照

graph - 深さ優先検索を理解しようとしています。私が正しいかどうかわからない

http://i.stack.imgur.com/sEJKz.png

画像はグラフです。これは正しい深さ優先トラバーサルですか? それとも、私はその考えを完全に間違っていますか?dfs についての私の理解は出発点として与えられ、隣接するすべてのノードを調べます。次に、任意に 1 つを選択し、そのノードを再帰的に「訪問」します。v から始めて、ノード 2 を選択して次に進みます。1 から 8 までの数字はパスを示します。

編集: 数字の 2 と 3 を混同しているようです! それらを交換する必要があります。

画像 2: http://i.stack.imgur.com/KdWl6.png

0 投票する
1 に答える
115 参照

java - これら 2 つの Cypher クエリを Traversal Framework に変換するのに助けが必要です

1 つ目は次のとおりです。パスを指定する一連のプロパティを指定すると、終了ノードを返す必要があります。すなわち

2 つ目はその逆です。ノードの識別子 (簡単にするために、ノードの ID と仮定します) を指定nameすると、ルートからノードへのパス (プロパティのシーケンス) を返します (一意であることが保証されます)。今のところ、私は次のものを使用していshortestPathます:

クエリは組み込みデータベースから実行され、速度に満足できないため、クエリを TraversalDescriptions に変換したいのですが、動的に変更する必要があり、これを行う方法がよくわかりません。

それとも、これらのクエリが最適ではないのでしょうか? <= 1shortestPathミリ秒実行されるものと、可変長のものは単一のクエリごとに 10 ミリ秒実行されます (これは受け入れられません)。多分あなたは私のためのいくつかのパフォーマンスのヒントを持っていますか?

0 投票する
1 に答える
811 参照

java - どのトラバーサルを使用する必要があるNeo4j?

現在、Neo4J Koan Tutorialを試しています。紹介されているKoan06で本当に混乱していTraversalます。メソッドNode.traversalは推奨されていませんTraversal.traverse。試してみると、Traversalクラス全体も非推奨になっていることがわかりました。ドキュメントを読んで、何を使用することになっているのかを調べましたが、何も見つかりません。ドキュメントでは、それTraversalが非推奨であることについても言及していませんでした (もちろん、トラバーサル メソッドも同様traversedescription明確化せずに非推奨です)。

簡単な質問: をビルドするには何を使用すればよいTraversalDescriptionですか?