Г и сал ға раева ж б ба заева а с ма ха но ва информатика

117
Іздеу алгоритмдері
Те рең нен із деу
(Depth First Search, DFS)
Көлденеңінен із деу
(Breadth First Search, BFS)
4-сыз ба. Із деу ал го ритм де рінің әдістері
Бұл әдіс тер көп жағ дай да ба ғыт тал ған граф тар да қол да ны-
ла ды, алай да қа быр ға ла ры қос ба ғыт ты деп са на ла тын ба ғыт-
тал ма ған граф тар да да қол да ну ға бо ла ды. Те рең нен жә не көл-
де не ңі нен із деу ал го ритм де рі граф ты өң деу дің түр лі есеп те рін 
ше шу ге ар нал ған, мы са лы, бай ла ныс ты тек се ру, тұй ық тал ған 
об лыс ты анық тау, тө бе лер ара сын да ғы қа шық тық ты та бу жә не 
бас қа лар. 
Те рең нен із деу
Те рең нен із деу де ал ды мен, бі рін ші тө бе қа рас ты ры ла ды, 
әрі қа рай граф қа быр ға сы ар қы лы тұй ық тал ған бө лік ке дей ін 
ба ра ды. Егер із деу бар лық көр ші лес тө бе лер ді қа рап шық қан 
бол са, граф тө бе сі тұй ық тал ған деп са на ла ды. 
Із деу тұй ық тал ған бө лік ке түс кен нен кей ін кел ген жо лы мен 
арт қа қа рай қа рал ма ған тө бе ле рі бар тө бе ге ке ле ді, әрі қа рай 
осы ба ғыт пен із деу жұ мы сын жал ғас ты ра ды. 
Үр діс бас тап қы ал ғаш қы тө бе ге кел ген кез де жә не оған көр-
ші лес бар лық тө бе лер ді қа рап шық қан кей ін аяқ тал ған бо лып 
са на ла ды. 
Осы лай ша, те рең нен із деу ал го рит мі нің не гіз гі идея сы –
тө бе ден шы ға тын қа быр ға лар дың бар лық мүм кін тар мақ тал ған 
жол да ры бой ын ша ал ды мен бір тар ма ғын, со сын ке ле сі тар ма-
ғы на өту ар қы лы граф ты то лық зерт теу. 

жүктеу/скачать 5,32 Mb.

Достарыңызбен бөлісу: