Деревья и графы — самые мощные структуры данных в программировании. Файловая система — дерево. Социальная сеть — граф. GPS-навигация — поиск кратчайшего пути в графе. Освоив эти структуры, вы сможете решать широкий класс задач.
Бинарное дерево поиска (BST)
# bst.py
class TreeNode: def __init__(self, val): self.val = val self.left = self.right = None class BST: def insert(self, root, val): if not root: return TreeNode(val) if val < root.val: root.left = self.insert(root.left, val) else: root.right = self.insert(root.right, val) return root
DFS: обход в глубину
# dfs.py
def dfs_tree(root): if not root: return print(root.val) # preorder: корень первым dfs_tree(root.left) dfs_tree(root.right) # DFS для графа (итеративно) def dfs_graph(graph, start): visited = set()
stack = [start] while stack: node = stack.pop() if node not in visited: visited.add(node) stack.extend(graph[node] - visited) return visited
// DFS vs BFS: когда что
DFS — поиск пути в лабиринте, топологическая сортировка, поиск циклов. BFS — кратчайший путь в невзвешенном графе, поиск ближайших соседей. BFS гарантирует нахождение кратчайшего пути, DFS — нет.
BFS: обход в ширину
# bfs.py
from collections import deque def bfs(graph, start, target): queue = deque([(start, [start])]) visited = {start} while queue: node, path = queue.popleft() if node == target: return path # нашли путь for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor])) return None # путь не найден
