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

深さ優先探索 (Depth First Search)

概要

深さ優先探索(DFS)はグラフにおける探索方法の一種で、初期node(木の場合はroot)から分岐ごとに可能な限り深く探索していく手法です。幅優先探索(BFS)ではキューを用いるのに対し、DFSはスタックまたは再帰を使って実装することができます。以下にPythonによる実装の一例を示します。

実装

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
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