үшінші жолындағы қадамдардың толық саны (WG(n) орындаған қадамдарды
ескермегенде), бұл процедураның барлық қатынаулары n ретті болады, m-
қабырғалар саны. Бұл O(n+m) алгоритмінің жалпы күрделілігін береді.
Графтағы алгоритмдерді құруда тереңдікке іздеу үлкен роль
атқаратындықтан, WG процедурасының рекурсивтік емес нұсқасын көрсете
кетейік.
Рекурсиядан құтылудың стандартты әдісі – стекті қолдану болып
табылады. Әрбір қарастырылған шың стекке енгізіледі, ал қолданылғаннан
кейін стектен жойылады.
{WG процедурасының рекурсивтік емес нұсқасы;
Іздеу басында P[u] - әрбір u шыңы үшін ТІЗІМ[u] тізімінің 1-ші
жазбасына сілтеме болсын;
Р, ЖАҢА массивтері- глобалды}
1 PROCEDURE WGl(v);
{v шыңынан бастап графтағы тереңдікке іздеу}
2 BEGIN СТЕК := 0; СТЕК <= v; v қарастыру; ЖАҢА [v] := false;
3 WHILE CTEK ≠ 0 DO
4 BEGIN t := top(CTEK); {t-стектің жоғарғы элементі} {ТІЗІМ [t]
тізімінен бірінші жаңа шыңды табу}
5 IF P[t]= nil THEN b:=false
6 ELSE b := not ЖАҢА [Р[t]^.жол];
7 WHILE b DO BEGIN
8 P[t]:=Р[t]^.келес;
9 IF P[t]=nil THEN b := false
10 ELSE b :=not ЖАҢА ТP[t]^.жол]
11 END;
12 IF P[t]≠nil THEN {жаңа шың табылды}
13 BEGIN t := Р[t]^.жол; СТЕК <=t;
14 t қарастыру; ЖАҢА [t] := false
15 END
16 ELSE {t шыңы қолданылды}
17 t<=CTEK {стектің жоғарғы элементін жою}
18 END
19 END
Ескерту. Дөңгелек жақшада графтың шыңдарын тереңдікке іздеу
процесі кезіндегі қарастырылу реті бойынша номерлейміз.
Әдіс бағытталған графтарға да оңай қолданылады. Бұл жағдайда да
WG(v) және WGl(v) процедураларына қатынауының нәтижесі O(n+m) қадам
ішінде барлық шыңдарды, және v-ден u-ға апаратын жолы да бар шыңдарды
өтетіндігі болып табылады.
Сөйтіп, тереңдікке іздеу кезінде неғұрлым шыңға кештеу барса, ол
шың соғұрлым тезірек қолданылады. Бұл қарастырылған, бірақ
қолданылмаған шыңдар стекте жиналып қалатындығымен байланысты.
Графтағы кеңдікке іздеу
Графтан іздеудің басқа әдісі – кеңдікке іздеуді (breadth first search)
қарастырайық. Бұл әдіс стекті кезекке алмастыруға негізделген. Бұл
жағдайда шыңға неғұрлым ертерек баратын болсақ, ол соғұрлым ертерек
қолданылады (кезектен жойылады). Шыңды қолдану оның көршілес екі
қарастырылмаған шыңын қарастыру арқылы жүзеге асады.
1 PROCEDURE WS(v);
{ v шыңынан басталатын графтан кеңдікке іздеу;
ЖАҢА, ТІЗІМ айнымалылары - глобалды}
2 BEGIN
3 КЕЗЕК := 0; КЕЗЕК <= v; ЖАҢА [v] := false;
4 WHILE КЕЗЕК := 0 DO begin
5 Р<= КЕЗЕК; р-ға бару;
6 FOR u€ ТІЗІМ [р] DO
7 IF ЖАҢА [u] THEN BEGIN
8 КЕЗЕК <= u; ЖАҢА [u]:=false
9
END
10
END
11 END
Тереңдікке іздеуде сияқты WS(v) процедурасына қатынау v шыңы бар
граф байланыстылығы компонентасының барлық шыңдарына баруға әкеледі,
әрбір шың бір рет қана қарастырылады. Алгоритмнің есептелу күрделілігі
m+n ретіне ие, өйткені әрбір шың кезекке орнатылып, кезектен бір рет қана
жойылады, ал цикл итерацияларының 6 саны граф қабырғаларының ретін
білдіреді.
Графтан іздеудің екі әдісі де – тереңдікке және кеңдікке – орнатылған v
және u шыңдарының арасындағы жолды табуда қолданыла алады. Ол үшін
графтан іздеуді v шыңынан бастап, u шыңына дейін жүргізу керек.
Тереңдікке іздеудің артықшылығы: шыңға бару кезінде стекте v
шыңынан бастап u шыңына дейінгі жолды анықтайтын шыңдар тізбегі
орнатылады.
Кемшілігі: осылай алынған жол жалпы жағдайда ең қысқа бола
алмайды.
Бұл
кемшіліктен
арылуға
болады,
егер
кеңдікке
іздеудің
модернизацияланған алгоритмін қолдансақ.
7-9 жолдарды мынаған алмастыра отырып, WS процедурасын
модификациялаймыз
IF ЖАҢА[u] THEN BEGIN
КЕЗЕК <= u; ЖАҢА [u]:= false;
АЛДЫҢҒЫ [u]:=Р
END
Модификацияланған процедураның жұмысы аяқталғанда, АЛДЫҢҒЫ
кестесі әрбір u шыңы үшін құрамында u-ға апаратын АЛДЫҢҒЫ[u] шыңы
болады. Математикалық индукция әдісімен бұл кесте шындығында да әрбір
қарастырылған шыңнан бастапқы v шыңына дейінгі ең қысқа жолды
анықтайтындығын көрсетуге болады. Тік жақшада графтың шыңдарын
кеңдікке іздеу процесі кезіндегі қарастырылу реті бойынша номерлейміз.
Тереңдікке іздеуде сияқты WS процедурасын ТІЗІМ[v], v€V,
инциденттілік тізімдері қандай да бір бағытталған графты анықтағанда да
модификацияларсыз да қолдануға болады. Онда біз іздеуді бастаған шыңнан
сол шыңдарға дейін апаратын жолы бар шыңдар ғана қарастырылады.
Керуші ағаштар
(каркастар)
Ағаш деп ерікті бағытталмаған циклсіз байланысқан графтарды
атайтындығымызды еске алайық. G = ерікті бағытталмаған графы
үшін әрбір ағашы керуші ағаш немесе G графының каркастар деп
аталады, мұндағы Т Е. Мұндай графтың (ағаштың) қабырғаларын бұтақ
деп, ал G графының қалған қабырғаларын хордалар деп атаймыз.
∈
n шыңы бар әрбір ағаштың n-1 бұтағы бар. (Тамырынан басқа барлық
шыңдарға бір ғана қабырға кіреді.
Керуші ағаштарды а) және б) әдістерімен (29-сур.) құруға болатын
граф болсын делік.
Достарыңызбен бөлісу: |
