問題タブ [depth-first-search]

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 投票する
4 に答える
5509 参照

c# - C# グラフ トラバーサル - 任意の 2 つのノード間のパスの追跡

グラフについて何も知らなくても、2 つのノード間の幅優先トラバーサルを追跡するための適切なアプローチを探しています。対 深さ優先 (パンアウトしない場合はパスを破棄できます) では、トラバーサル中にかなりの数の「開かれた」可能性がある場合があります。

0 投票する
3 に答える
327 参照

language-agnostic - サイトマップ・リストの作り方

サイト マップ/リストを作成する必要がありますが、リンク名も表示する必要があります。

つまり、たとえば、www.google.com が与えられた場合、次のリストを作成する必要があります。

リストは、us.example.com などのドメインにバインドする必要があります。

リンクを解析するためにBeautiful Soupを使用して、pythonスクリプトを使用して深さ優先検索を試みました。これは失敗しました。

彼らがそれをどのように行うかについて誰にもアイデアがありますか?

0 投票する
4 に答える
129144 参照

algorithm - 幅優先と深さ優先

ツリー/グラフをトラバースするとき、幅優先と深さ優先の違いは何ですか? コーディングや疑似コードの例はどれも素晴らしいでしょう。

0 投票する
4 に答える
685 参照

binary-tree - メモリが限られている二分木で最初のnullを見つける

各ノードが値を持つことができる二分木があります。

ツリー内で値がnullで、ルートに最も近いノードを見つけたいと思います。ルートから同じ距離にある2つのノードがある場合は、どちらでもかまいません。二分木への読み取りアクセスの数を最小限に抑える必要があります。作業メモリーがkノードのみに制限されていると想定します。

深さkまでのDFSは網羅的ですが、最初にツリー全体を実行しない限り、最も近いノードは見つかりません。BFSは最も近いものを見つけますが、DFSは同じメモリでより深いヌルを見つけることができるため、失敗する可能性があります。

ツリーへの読み取りアクセスの数を最小限に抑えて、最も近いnullノードを見つけたいと思います。

(最終的にはこれをn-wayツリーにも実装する必要があるため、一般的な解決策が適切です。ツリーへの書き込みアクセスはなく、読み取りのみです。)

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

depth-first-search - 限られたメモリを使用した反復深化深さ優先検索

これは、 Find first null in binary tree with limited memoryのフォローアップです。

ウィキペディアによると、深さ優先検索を繰り返し行うと、最短経路が見つかるとのことです。メモリ内で k ノードに制限され、ツリーへのアクセス回数が最も少ない実装が必要です。

たとえば、私のバイナリ ツリーが次の場合:

また、検索順序よりもメモリの 5 ノードに制限されています。

次の読み取りが 7 の場合、3 を再読み取りする必要があります。しかし、次の読み取りが 14 の場合、まだ 3 を再読み取りする必要はありません。解が 14 の場合、アルゴリズムは少し速くなります!

一般的な解決策を探しています。任意のサイズのメモリとノードあたりのブランチ数で機能するもの。

0 投票する
2 に答える
1775 参照

graph-theory - 総サイクル数とサイクル長を求める

接続された無向グラフのサイクルの総数とサイクルの長さを見つけることに興味があります。DFS を使用できますか? または、DFS は 1 つのサイクルしか検出できませんか? どのコードも間違いなく役に立ちます。

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

java - マトリックス内の隣接する数値の最大領域を見つける

これは宿題ではありません。私はプログラミングの初心者で、これが初めての投稿です。ご容赦ください。

ここに投稿された同様の質問を見つけることができませんでした。

初心者向けの本で、次の問題を見つけました。

http://www.algolist.net/Algorithms/Graph_algorithms/Undirected/Depth-first_searchの DFS 実装を使用した、これまでのコードを次に示します。どこにでも「マジックナンバー」があり、メソッドは「public static」などです。アルゴリズムが機能した後、これらの問題を修正するつもりでした...

数日間デバッグした後、デバッグセッションごとにコードがより複雑になります...助けていただければ幸いです。前もって感謝します。

0 投票する
2 に答える
960 参照

graph - 深さ優先検索

ネットや古い Java の本で見つけた情報に基づいて、c# で深さ優先検索を実装し、msdn サイトの Node と NodeList と Graph を使用しました。DFS または BFS を変更して特定の重量をチェックするにはどうすればよいですか?

0 投票する
4 に答える
9098 参照

java - Javaを使用した深さ優先検索

Javaを使ってDFS(深さ優先探索)とBFSを実装したいです。

Javaには、すぐに使用できる組み込みのツリーデータ構造がありますか? または私が使用できる他のものはありますか?

0 投票する
10 に答える
20000 参照

algorithm - 幅優先検索は何に役立ちますか?

通常、グラフをたどる必要があるときは、空間の複雑さが低いため、常に深さ優先検索を使用してきました。私の経験かなり限られていますが、正直なところ、幅優先検索が必要な状況を見たことがありません。

幅優先検索を使用する意味があるのはいつですか?

更新:ここでの私の答えは、BFSを使用した状況を示していると思います(DFSだと思っていたため)。この場合、なぜそれが役に立ったのか、私はまだ知りたいと思っています。