Traversal і priority: BFS, DFS, heap та lazy iteration

Graph contract перед traversal

Graph задається nodes та edges; треба визначити directed/undirected semantics, missing neighbor policy, duplicate edges і deterministic order. Без visited cycle може повторювати nodes без кінця. Для tree visited інколи не потрібен, але загальний graph traversal має його явно.

BFS і DFS відповідають різним питанням

BFS використовує FIFO queue і проходить layers; у неваговому graph він підходить для найкоротшої кількості edges. DFS використовує stack або recursion і заглиблюється в branch; він корисний для повного обходу, component exploration чи backtracking, але recursion depth є runtime boundary.

from collections import deque

queue = deque([start])
visited = {start}
while queue:
    node = queue.popleft()
    for neighbor in sorted(graph.get(node, [])):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

Mark-on-enqueue запобігає дублюванню frontier. Sorting neighbors дає deterministic навчальний output, але додає cost, який треба назвати.

Heap — partial order для priority workload

heapq підтримує heap invariant: найменший item у heap[0]. Для stable priority queue використовуйте tuple (priority, sequence, task); sequence розв’язує ties і не змушує Python порівнювати несумісні task objects. Stale-entry або priority-update policy має бути документована.

Lazy iteration контролює memory

Generator та itertools обробляють items поступово. Це не робить algorithm автоматично швидшим, але може зменшити peak memory і дозволити early stop. Materialization через list(...) повертає full allocation, тому boundary має бути свідомою.

Performance evidence package

Спочатку доведіть correctness і deterministic operation counts на sizes 0, 1, 10, 100. Потім за потреби додайте timeit з окремим setup, кількома repeats, runtime/version та raw vector. Не перетворюйте мікробенчмарк на обіцянку production latency.

• Same result and same validation policy for compared variants.
• Input generation поза measured body.
• Operation count або invariant evidence поруч із timing.
• CPU, I/O і network claims не змішуються.
• Висновок називає range sizes і limitations.
• Regression threshold прив’язаний до contract, а не випадкового best run.

Методичні джерела

• Python docs — heapq
• Python docs — collections.deque
• Python docs — itertools
• Python docs — timeit

Урок, сценарії, пояснення й вправи створені SEOWORK. Посилання ведуть лише на офіційну документацію та Python Wiki.