53632


スタックを使った「深さ優先探索」とキューを使った「幅優先探索」について、入力と使い方に関してわからないことが２点あります。

  1. 現在のコードを実行するときは、２分探索木（以下の例）を入力としていますが、深さ優先探索と幅優先探索の入力は２分探索木でなければならないのでしょうか。

T = ((((), 111, ()), 11, ((), 112, ())), 1, (((), 121, ()), 12, ((), 122,
())))

  2. 現在のコードで返す結果は探索順序となっていますが、実際に仕事や競技プログラミングなどで使われる時はどのように使用されるアルゴリズムなのでしょうか。  
検索してみましたが、大学等の教育機関の資料が主でした。初心者にもわかりやすい「深さ優先探索」と「幅優先探索」のアルゴリズムが使われているコードがあれば教えていただきたいです。

どちらの探索方法が適しているのか判断の仕方が現在のコードだけだと理解できていません。

結果

[code]

    depth_first_search(T)
    1,12,122,121,11,112,111,
    
    breadth_first_search(T)
    1,11,12,111,112,121,122,
    
[/code]

深さ優先探索

[code]

    from collections import deque
    
    def depth_first_search(T):
        D = deque() #スタック
        if len(T) > 0:
            D.append(T) #show(D)
        while len(D) > 0:
            L, a, R = D.pop()
            print(a, end=',') #show(D)
            if len(L) > 0:
                D.append(L) #show(D)
            if len(R) > 0:
                D.append(R) #show(D)
        print()
    
    def show(D):
        print('[', end='')
        for (L, a, R) in D:
            print(a, end='<-')
        print(']')
    
[/code]

幅優先探索

[code]

    from collections import deque
    
    def breadth_first_search(T):
        D = deque() #キュー
        if len(T) > 0:
            D.append(T) #show(D)
        while len(D)>0:
            L, a, R = D.popleft()
            print(a, end=',') #show(D)
            if len(L)>0:
                D.append(L) #show(D)
            if len(R)>0:
                D.append(R) #show(D)
        print()
    
    
    
    def show(D):
        print('[', end='')
        for (L, a, R) in D:
            print(a, end='<-')
        print(']')
    
[/code]


CC BY-SA 4.0
2019-03-21T10:04:49.403
53618
2019-03-22T02:04:03.257
question
python python3 アルゴリズム データ構造
深さ優先探索と幅優先探索の入力と使い方について


> 現在のコードを実行するときは、２分探索木（以下の例）を入力としていますが、深さ優先探索と幅優先探索の入力は２分探索木でなければならないのでしょうか。

いいえ。一般に、様々な探索問題に対して深さ優先探索や幅優先探索、及びこれらを改善した探索アルゴリズムが使われており、分かりやすい例ではグラフなどのデータ構造に対して用いられています。

> 現在のコードで返す結果は探索順序となっていますが、実際に仕事や競技プログラミングなどで使われる時はどのように使用されるアルゴリズムなのでしょうか。

問題によります。また、下で紹介している本に様々な利用例が掲載されています。

>
> 検索してみましたが、大学等の教育機関の資料が主でした。初心者にもわかりやすい「深さ優先探索」と「幅優先探索」のアルゴリズムが使われているコードがあれば教えていただきたいです。

[他の質問](https://ja.stackoverflow.com/users/32568/nao)を見るに、競技プログラミングなどにご興味がお有りのようですので、まずはその手の本を読むことをおすすめします。様々なサンプルコードやデータ構造などの知識が得られるでしょう。

  * [プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ | 秋葉拓哉, 岩田陽一, 北川宜稔 |本 | 通販 | Amazon](https://www.amazon.co.jp/dp/4839941068)
  * [プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 | 渡部 有隆, Ozy(協力), 秋葉 拓哉(協力) |本 | 通販 | Amazon](https://www.amazon.co.jp/dp/4839952957/ref=asap_bc?ie=UTF8)


CC BY-SA 4.0
2019-03-21T15:14:26.630
53632
2019-03-21T16:29:08.983
2019-03-21T16:29:08.983
3060
29826
53618
answer


深さ優先探索は、今調べているノードの位置の情報だけを記録していれば良いので必要とするメモリ量が少ない（高々、対象とする木構造の最長の枝の長さのスタックで足りる）という長所があります。  
木のノードを上り下りしながら探索していく方法なので、並列化や並行化することが出来ないという短所があります。

それとは対照的に幅優先探索は、今までに調べてノードの位置の情報を全て記録しておかなければならないので(深さ優先探索に比べて)多くのメモリを必要とするという短所があります。  
横並びのノードの探索を同時並行で行うことができるので、プログラムの並列化や並行化によって高速化が可能だという長所があります。

探索対象のデータが木の中で占める位置によって、探索にかかる計算量が変わります。  
事前に探索対処の位置が判っている事はないので、どちらの方法が有利なのかは木の内容次第です。

もし、同じ木に対して(検索条件を変えながら)探索を繰り返すような用途であれば、二分探索木が適しています。  
元のデータから二分探索木を構築する手間がかかりますが、検索が早い（探索にかかる計算量の期待値が小さい）からです。


CC BY-SA 4.0
2019-03-22T02:04:03.257
53637
2019-03-22T02:04:03.257
217
53618
answer