Көлденең іздеу (BFS): практика

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

Сынып

11-сынып

Пән

Информатика

Тоқсан

2

Сабақ

№ 24

Бөлім

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

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

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

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

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

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

   BFS DFS Краскал алгоритмі Прим алгоритмі
3. 3
   BFS алгоритмінің уақыт күрделілігі қандай (V — төбелер, E — қырлар)?

   \(O(E^{2})\) \(O(V \cdot E)\) \(O(V+E)\) \(O(V^{2})\)