

下記のような深さ優先探索の行きがけ順のpython3スクリプトを、Visual Studio 2019(python)で  
デバッグ実行してステップインしてみました。

[code]

    tree = [[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[],[],[],[],[],[],[],[]]
    
    def search(pos):
        print(pos, end=' ')
        for i in tree[pos]:
            search(i)
    search(0)
    
[/code]

1,search(0) posが0,iが1。  
2,search(1) posが1,iが3。  
3,search(3) posが3,iが7。  
4,search(7) posが7,iが空リストのためわからない。  
5,search(7) posが3,iが7。  
6,search(7) posが3,iが8。  
以下続く。

上記の4,search(7)の時、iが空リストを指してどこかに行ってしまったようなのですが、  
そこで再帰でもしたのでしょうか、  
5,search(7) posが3,iが7。になっています。その後も、  
6,search(7) posが3,iが8。になっています。

4,search(7)の時の、iが空リストの時のposが3に戻る理由を教えてください。  
また、6,search(7) posが3,iが8。になる理由を教えてください。


CC BY-SA 4.0
2020-02-19T06:02:20.457
63175
2020-02-20T00:48:43.607
2020-02-19T12:25:22.587
3060
26074
question
python
深さ優先探索の行きがけ順のpython3スクリプト


> 4,search(7)の時の、iが空リストの時のposが3に戻る理由を教えてください。

search(7)はsearch(3)から呼び出されているので、search(7)が終了するとsearch(3)にもどります。

> また、6,search(7) posが3,iが8。になる理由を教えてください。

search(3)がtree[3]である[7,8]の7を処理したあと、8を処理するからです。

調査用のprintを入れた以下のコードを実行すると、

[code]

    tree = [[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[],[],[],[],[],[],[],[]]
    def search(pos):
        print("START pos = ", end=' ')
        print(pos)
        for i in tree[pos]:
            print("i = ", end=' ')
            print(i)
            search(i)
    
        print("END  pos = ", end=' ')
        print(pos)
    search(0)
    
[/code]

以下の結果が得られます。※字下げは手で修正しています。

[code]

    START pos =  0
          i =  1
          START pos =  1
                i =  3
                START pos =  3
                      i =  7
                      START pos =  7
                      END   pos =  7
                      i =  8
                      START pos =  8
                      END   pos =  8
                END   pos =  3
                i =  4
                START pos =  4
                      i =  9
                      START pos =  9
                      END   pos =  9
                      i =  10
                     START pos =  10
                     END   pos =  10
                END  pos =  4
          END  pos =  1
          i =  2
          START pos =  2
                i =  5
                START pos =  5
                      i =  11
                      START pos =  11
                      END   pos =  11
                      i =  12
                      START pos =  12
                      END  pos =  12
                END   pos =  5
               i =  6
               START pos =  6
                     i =  13
                     START pos =  13
                     END   pos =  13
                     i =  14
                     START pos =  14
                     END   pos =  14
               END  pos =  6
          END  pos =  2
    END   pos =  0
    
[/code]


CC BY-SA 4.0
2020-02-19T08:50:11.257
63180
2020-02-20T00:48:43.607
2020-02-20T00:48:43.607
35558
35558
63175
answer