Algorithms 101: DFS and BFS

Depth-First Search (DFS) and Breadth-First Search (BFS) are two common traversal methods for trees and graphs

Tree Traversal

Depth-First Search (DFS) is an algorithm that traverses the nodes of a tree by searching the branches as deeply as possible. It traverses the nodes of the tree along its depth, exploring the branches as deeply as possible.

• In the depth-first traversal of a tree, we first visit the root node and then recursively perform a depth-first traversal on each subtree rooted at the root node.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

    def dfs_traversal(self):
        print(self.value)
        for child in self.children:
            child.dfs_traversal()

root = TreeNode('A') # 创建一个简单的树结构
child1 = TreeNode('B')
child2 = TreeNode('C')
child3 = TreeNode('D')
root.add_child(child1)
root.add_child(child2)
child1.add_child(child3)

root.dfs_traversal() # 进行深度优先遍历

Tree dfs_traversal

def dfs_traversal(self):
        print(self.value)
        for child in self.children:
            child.dfs_traversal()

Breadth-First Search (BFS) is an algorithm that traverses the tree by visiting the nodes layer by layer. It starts from the root node, visits all nodes adjacent to the root node, and then traverses down layer by layer.

• In the breadth-first traversal, we first visit the root node and then sequentially visit each node at each level.

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

    def bfs_traversal(self):
        queue = deque([self])  # 使用双端队列来实现 BFS
        while queue:
            node = queue.popleft()  # 从队列左侧取出节点
            print(node.value)
            queue.extend(node.children)  # 将节点的子节点加入队列

root = TreeNode('A') # 创建一个简单的树结构
child1 = TreeNode('B')
child2 = TreeNode('C')
child3 = TreeNode('D')
root.add_child(child1)
root.add_child(child2)
child1.add_child(child3)

root.bfs_traversal() # 进行广度优先遍历

Tree bfs_traversal

 def bfs_traversal(self):
        queue = deque([self])  # 使用双端队列来实现 BFS
        while queue:
            node = queue.popleft()  # 从队列左侧取出节点
            print(node.value)
            queue.extend(node.children)  # 将节点的子节点加入队列

For example, breadth-first search is usually more suitable for finding the shortest path or traversing the entire tree. In some cases, depth-first search may be more appropriate.These two traversal methods have different applications in different scenarios. For example, breadth-first search is usually more suitable for finding the shortest path or traversing the entire tree. In some cases, depth-first search may be more appropriate.

Graph Traversal