深さ優先探索と幅優先探索の入力と使い方について


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

  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]




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

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

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

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

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

[他の質問](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)




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

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

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

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

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

[他の質問](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)

