PythonでBFS（幅優先探索）を使って木構造のノードを表示するプログラム

木構造のノードを幅優先探索（BFS：Breadth First Search）で表示したい場合、専用のクラスを作成し、その中にルートノードの設定、要素の追加、特定要素の検索、BFSトラバーサルの実行といったメソッドを実装します。作成したクラスのインスタンスを生成すれば、これらのメソッドを自由に呼び出して利用できます。

本記事では、対話型のメニュー形式で動作するサンプルプログラムを通じて、その実装方法を詳しく解説します。

サンプルコード

class Tree_struct:
    def __init__(self, data=None):
        self.key = data
        self.children = []

    def set_root(self, data):
        self.key = data

    def add_node(self, node):
        self.children.append(node)

    def search_node(self, key):
        if self.key == key:
            return self
        for child in self.children:
            temp = child.search_node(key)
            if temp is not None:
                return temp
        return None

    def bfs_operation(self):
        queue = [self]
        while queue != []:
            popped = queue.pop(0)
            for child in popped.children:
                queue.append(child)
            print(popped.key, end=' ')

my_instance = None

print('Menu (assume no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('bfs')
print('quit')

while True:
    my_input = input('What operation would you do ? ').split()

    operation = my_input[0].strip().lower()
    if operation == 'add':
        data = int(my_input[1])
        new_node = Tree_struct(data)
        suboperation = my_input[2].strip().lower()
        if suboperation == 'at':
            my_instance = new_node
        elif suboperation == 'below':
            position = my_input[3].strip().lower()
            key = int(position)
            ref_node = None
            if my_instance is not None:
                ref_node = my_instance.search_node(key)
            if ref_node is None:
                print('No such key')
                continue
            ref_node.add_node(new_node)

    elif operation == 'bfs':
        if my_instance is None:
            print('The tree is empty')
        else:
            print('Breadth First Search traversal is : ', end='')
            my_instance.bfs_operation()
            print()

    elif operation == 'quit':
        break

実行結果

Menu (assume no duplicate keys)
add <data> at root
add <data> below <data>
bfs
quit
What operation would you do ? add 6 at root
What operation would you do ? add 4 below 6
What operation would you do ? add 9 below 4
What operation would you do ? bfs
Breadth First Search traversal is : 6 4 9
What operation would you do ? quit

プログラムの解説

• 必要な属性を持つ「Tree_struct」クラスを定義しています。

• コンストラクタ「__init__」では、データを格納する変数と、子ノードを管理するための空リストを初期化します。

• 「set_root」メソッドは、木のルート値を設定するために用意されています。

• 「add_node」メソッドは、指定したノードの子として新しい要素を追加します。

• 「search_node」メソッドは、再帰的に子ノードをたどりながら、指定されたキーを持つノードを検索します。見つからなければNoneを返します。

• 「bfs_operation」メソッドは、キュー（FIFO）を利用して幅優先探索を実行します。ノードを取り出す順番に、上の階層から順にキーの値を出力していきます。

• インスタンス変数「my_instance」は最初にNoneで初期化され、木がまだ存在しない状態を表現しています。

• whileループの中でユーザーからの入力を受け付け、実行したい操作を選択できる対話型の設計になっています。

• ユーザーの選択内容に応じて、ノードの追加・BFSトラバーサル・終了のいずれかの処理が実行されます。

• 処理結果は随時コンソールに出力され、木の状態を確認できます。

BFSのポイント

幅優先探索では、リストの先頭から要素を取り出し（pop(0)）、その子ノードを末尾に追加していくことで、木を上の階層から順番に走査できます。このサンプルでは、ルート「6」→子「4」→孫「9」の順に出力されており、深さ方向ではなく横方向に探索が進んでいることが確認できます。