27
14

More than 3 years have passed since last update.

幅優先探索(BFS)と深さ優先探索(DFS)

Last updated at Posted at 2019-09-13

概要

グラフや木の探索に用いられる幅優先探索と深さ優先探索について、Pythonでの実装を用いながら紹介します。

実装

BFS
``````# Make tree as follows:
#     1
#    / \
#   2   3
#  / \ / \
# 4  5 6  7

from collections import deque

class Node:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

node1 = Node(1) # Root node
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

# キューを作成して初期ノード(root)を入れる
q = deque()
q.append(node1)

# キューが空になるまで繰り返す
while len(q) > 0:
# キューの先頭（左端）からnodeを取り出す
node = q.popleft()

if node is not None:
print(node.val)
# nodeの子要素をキューの末尾（右端）に入れる
q.append(node.left)
q.append(node.right)
``````

出力結果

``````1
2
3
4
5
6
7
``````

深さ優先探索 (Depth First Search: DFS)

実装

DFS
``````# Make tree as follows:
#     1
#    / \
#   2   5
#  / \ / \
# 3  4 6  7

class Node:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)

node1.left = node2
node1.right = node5
node2.left = node3
node2.right = node4
node5.left = node6
node5.right = node7

def traverse(node):
if node is not None:
print(node.val)
# 子要素に対して再帰的に呼び出していく
traverse(node.left)
traverse(node.right)

traverse(node1)
``````

出力結果

``````1
2
3
4
5
6
7
``````

補足

27
14
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
27
14