Графты айналып өту: бекіту тапсырмалары

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

Сынып

11-сынып

Пән

Информатика

Тоқсан

2

Сабақ

№ 29

Бөлім

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

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

• 11.2.2.1қолданбалы есептерде ең қысқа жолды табу үшін графтарды айналып өту алгоритмдерін қолдану
• 11.2.2.2BFS және DFS алгоритмдерінің тиімділігін талдау және оңтайлы әдісті таңдау

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

1. 1
   Салмақсыз графта берілген төбеден қалған барлық төбелерге ең қысқа жолды табу үшін қай алгоритм қолданылады?

   Краскал алгоритмі Прим алгоритмі ені бойынша іздеу (BFS) тереңдік бойынша іздеу (DFS)
2. 2
   BFS алгоритмі төбелерді аралау кезінде қандай деректер құрылымын қолданады?

   кезек (queue) стек (stack) хэш-кесте (hash) үйінді (heap)
3. 3
   DFS алгоритмі әдетте қандай деректер құрылымына сүйенеді?

   кезек (немесе кезектер жиыны) стек (немесе рекурсия) хэш-кесте (немесе сөздік) үйінді (немесе басымдық кезегі)