Help us understand the problem. What is going on with this article?

これができたら中級者?探索アルゴリズム

More than 1 year has passed since last update.

プログラミング中級者への道

プログラミングを勉強し、ある程度コーディングができるようになったけれどもなかなか自分の成長を感じることができないあなたに

幅優先探索と深さ優先探索

深さ優先探索とは

深さ優先探索(ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
from wikipedia

はい。わかりませんね。
細けぇこたぁいいんだよ!
実践あるのみ!

今回使うデータ(構造)はこれだ!

"幅優先探索"の場合には1, 2, 3, 4, 5...というように番号順にノードを処理していきます。
"深さ優先探索"では、1, 2, 4, 7, 8...という順番になります。

前置きはここまで

実際にコードを紹介していきましょう。

まずはデータを用意します。

s10 = {"content": 10, "children": None}
s9 = {"content": 9, "children": None}
s8 = {"content": 8, "children": None}
s7 = {"content": 7, "children": None}
s6 = {"content": 6, "children": [s10]}
s5 = {"content": 5, "children": [s9]}
s4 = {"content": 4, "children": [s7, s8]}
s3 = {"content": 3, "children": [s6]}
s2 = {"content": 2, "children": [s4, s5]}
s1 = {"content": 1, "children": [s2, s3]}
root = {"content": None, "children": [s1]}

print(root)
# {'content': None, 'children': [{'content': 1, 'children': [{'content': 2, 'children': [{'content': 4, 'children': [{'content': 7, 'children': None}, {'content': 8, 'children': None}]}, {'content': 5, 'children': [{'content': 9, 'children': None}]}]}, {'content': 3, 'children': [{'content': 6, 'children': [{'content': 10, 'children': None}]}]}]}]}

深さ優先探索

深さ優先のアルゴリズムではループにおける一時変数にスタックを使います。
なお、今回スタック変数とキュー変数では同じdequeを使用します。
dequeとはDouble ended queueというデータ構造でスタックとキューの両方の性質を持つデータ構造です。
スタックとして使いたい場合popメソッド、キューとして使いたい場合popleftメソッドを使います。

from collections import deque
# 上記の変数rootをそのまま使います。
result = []
stack = deque()
stack.extend(root.get("children"))
while stack:
  tmp = stack.pop()# スタックとして扱うためpop()
  content = tmp.get("content")
  children = tmp.get("children")
  result.append(content)
  if children:
    stack.extend(children[::-1])

print(result)
# [1, 2, 4, 7, 8, 5, 9, 3, 6, 10]

幅優先探索

幅優先探索の場合のアルゴリズムはどうなるのでしょう?
簡単です。深さ優先探索の処理のループ一時変数をスタックからキューに変えるだけ!

from collections import deque
result = []
queue = deque()
queue.extend(root.get("children"))
while queue:
  tmp = queue.popleft()# キューのためpopleft()
  content = tmp.get("content")
  children = tmp.get("children")
  result.append(content)
  if children:
    queue.extend(children)

print(result)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

これで君も中級者?ちょっと待って!

中級者への道は再起表現をマスターすることで開かれます。
再起表現はプログラムのメモリ空間のスタック領域をそのまま使いループ処理を実行するもの。

わざわざスタック変数を定義せずに直感的に書くことができるのが利点
言語仕様でtail recursionという機能をサポートしていないと処理の規模によってスタックオーバーフローを引き起こしてしまうのが欠点

再起表現(深さ優先探索)

def recursive(tmp, acc=[]):
  content = tmp.get("content")
  children = tmp.get("children")
  acc.append(content)
  if children is not None:
    for c in children:
      recursive(c, acc)
  return acc

result = recursive(root.get("children")[0])
print(result)
# [1, 2, 4, 7, 8, 5, 9, 3, 6, 10]

後日更新予定

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away