深度優先ナビゲーション

1958 ワード
アルゴリズム#アルゴリズム# テキストリンク
インフラでは、Kim Tawonの「Pythonアルゴリズム解題」講座を聴いています.
再符号化サイトと「Pythonアルゴリズムインタビュー」を同時に読むと、これまでの基礎段階の必要性を意識して授業を受けている.

深度優先ナビゲーションvs幅優先ナビゲーション


深さ優先探索は1四半期が終わるまで掘ってから調査する.
幅優先検索は、ノードの最も隣接するノードから開始します.

ツリー内のDFSのナビゲーション順序


順序:1>2>4>2>5>2>1>3>6>3>7

DFSには前列、中列、後列の巡回方式がある。


電位巡回検出出力(左右):1>2>4>5>3>6>7
中尉巡り出力(左):4>2>5>1>6>3>7
後列サイクル出力(左右):4>5>2>6>7>3>1
*富は親、左右は子供の左右
3つの方法はいずれもデフォルトのナビゲーション順序に従いますが、出力の順序は異なります.
電位はまず出力され、次のターゲットを探します.
中尉左ナビゲーション後出力、親出力後再度右ナビゲーション
後列は左、右、親順です.

コードビュー


木から見ると左が부모*2、右が부모*2+1です.
再帰関数なので、必ず終了点を設定します.
def DFS(n):
  if n > 7:
    return
  else:
    print(n) # 처리할 문(여기서는 print)이 여기 있으면 전위, 가운데 있으면 중위, 끝에 있으면 후위
    DFS(n*2)
    DFS(n*2 + 1)
ダブルポインタとスライドウィンドウ
1. folk , clone, pull,push