Тереңінен іздеу (DFS) алгоритмі

КТЖ бойынша тақырып

Сынып

11-сынып

Пән

Информатика

Тоқсан

2

Сабақ

№ 25

Бөлім

Графтардағы алгоритмдер (Python)

Оқу мақсаттары

• 11.2.2.2BFS және DFS алгоритмдерінің тиімділігін талдау және оңтайлы әдісті таңдау

Сұрақтардан мысал

1. 1
   Тереңінен іздеу (DFS) алгоритмі қандай деректер құрылымына негізделеді?

   Кезек Стек Хэш-кесте Үйінді (heap)
2. 2
   DFS кезінде бір төбені бірнеше рет қарауды болдырмау үшін не қолданылады?

   Келінген төбелер массиві (visited) Көршілестік матрицасы Рекурсия тереңдігінің шегі Қырлардың салмақтары
3. 3
   Көршілестік тізімімен берілген графта DFS-тің уақыт күрделілігі қандай?

   \(O(E \log V)\) \(O(V \cdot E)\) \(O(V+E)\) \(O(V^2)\)