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

幅優先探索 (Breadth First Search)

概要

幅優先探索(BFS)はグラフにおける探索方法の一種で、初期node(木の場合はroot)から近いnodeを順に探索していきます。深さ優先探索(DFS)ではスタックを用いるのに対し、BFSはキューを使って実装することができます。以下に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
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