Бағдарламалу технологиясы


ГРАФТАРҒА АРНАЛҒАН АЛГОРИТМДЕР



жүктеу 1,63 Mb.
бет68/73
Дата03.02.2022
өлшемі1,63 Mb.
#35497
түріОқулық
1   ...   65   66   67   68   69   70   71   72   73
Ба?дарламалу технологиясы

13 ГРАФТАРҒА АРНАЛҒАН АЛГОРИТМДЕР




13.1 Графтарды жүріп өту алгоритмдері

Графтың барлық төбелерін «қарап шығуды» қажет ететін көлік есептерінің тобы бар. Сонымен қатар әрбір төбе бір рет қана «қаралуы» керек.

Графтар теориясында граф төбелерін жүріп өтудің екі негізгі алгоритмі белгілі: графты «тереңдігі» бойынша және «көлденеңі» бойынша жүріп өту.

Бірінші жағдайда алгоритмде стек типіндегі құрылым, ал екінші жағдайда – кезек типіндегі құрылым қолданылады.

«Алгоритмдеу» тұрғысынан бірінші жағдайға көп мән беруге болады, өйткені онда күрделі құрылымдарда қолданылатын «қайтару» алгоритмі жазылады.

Графты «тереңдігі» бойынша жүріп өту алгоритмінің жұмысын 13.1-суретте көрсетілген, күрделілігі орташа мысалда қарастырайық.


13.1-сурет – Күрделілігі орташа граф


Графты «тереңдігі» бойынша жүріп өту алгоритмі графтың «жаңа» төбелері, яғни «қаралмаған» төбелері ұғымын қолданады. Оның жұмысын қарастырайық:

– графтың барлық төбелері «жаңа» деп жарияланады (Дейкстр алгоритмінде «уақытша» термині қолданылады). Графты қарап өтуді белгілі бір төбеден бастаймыз, мысалы 0-ші төбеден оны қарап өткеннен кейін оны «жаңа емес» деп белгілейміз;

– берілген төбемен қосылған бүкіл жаңа сыбайлас тізімнен нөмірі ең төмен төбені таңдаймыз. Қарастырылған мысалда ол 1-төбе;

– оны алғашқы деп жариялаймыз, оны қарап шыққаннан кейін оны «жаңа емес» деп белгілейміз;

– егер қарап өтілген төбенің жаңа сыбайлас төбелері болмаса, онда алдыңғы төбеге қайта ораламыз (стек жұмысы);

– процесс «жаңа» төбелер бар болғанша қайталанады.

13.1-суретте көрсетілген графқа қарастырылған алгоритмді қолданып төбелерді қарап шығу тізбегін аламыз:.

0 – 1 – 3 – 4 – 5 – 7 – 8 – 6 – 2 – 12 – 11 – 9 – 10.

Графты «көлденеңі» бойынша қарастырғанда да графтың «жаңа» төбелері деген ұғымды қолданады. Оның жұмысын қарастырайық:

– графтың барлық төбелері «жаңа» деп жарияланады. Графты жүріп өтуді белгілі бір алғашқы төбеден бастайық, мысалы, 0-төбеден. Ол төбені қарап шыққаннан (төбе нөмерін басамыз) кейін оны «жаңа емес» деп белгілейміз;

– қарап шыққан төбемен байланысты барлық жаңа сыбайлас төбелер тізімі өсу ретімен кезекке тұрғызамыз: 1 – 3 – 11;

– кезектен төбені таңдаймыз (осы мысалды ол 1-төбе), оны қарап өтеміз, «жаңа емес» деп белгілейміз. Қаралып өткен тізіммен байланысы бар сыбайлас төбелердің бүкіл тізімі өсу ретімен кезекке тұрғызамыз: 3 – 11;

– процесс графта төбелер бар болғанша қайталанады.

Графтың қаралған төбелерінің:

0 – 1 – 3 – 11 – 4 – 6 – 9 – 10 – 5 – 8 – 12 – 2 – 7.

13.1-суретінде көрсетілген граф мысалында Графты «тереңдігі» бойынша жүріп өту алгоритмінің бағдарламалақ орындалуын қарастырайық.

Бағдарлама коды:

using System;

using System.Collections;

using System.Text;

namespace ConsoleApplication1

{

class Program



{

public static int i, j, k, n,kol;

static void vkl(Stack vst, int n)

{

vst.Push(n);



}

static void iskl(Stack vst)

{

if (vst == null) Console.WriteLine("Stek bos!");



else

n = (int)vst.Pop();

}

public static void Main()



{

Stack vstek = new Stack();

//int i, j, k, n;

bool[] nov = new bool[13];

int[,] p = new int[13, 13];

int[,] a = new int[13, 13]

{{0,1,1000,1,1000,1000,1000,1000,1000,1000,1000, 1, 1000 },

{1,0,1000,1,1000,1000,1000,1000,1000,1000,1000,1000, 1000},

{1000,1000,0,1000,1000,1000,1,1000,1000,1000,1000,1000,1000},

{1,1,1000,0,1,1000,1,1000,1000,1000,1000,1,1000},

{1000,1000,1000,1,0,1,1,1000,1,1000,1000,1000, 1},

{1000,1000,1000,1000,1,0,1000,1,1,1000,1000,1000,1000},

{1000,1000,1,1,1,1000, 0,1000,1000,1000,1000,1000,1000},

{1000,1000,1000,1000,1000,1,1000,0,1,1000,1000,1000,1000},

{1000,1000,1000,1000,1,1,1000,1,0,1000,1000,1000,1000},

{1000,1000,1000,1000,1000,1000,1000,1000,1000,0,1,1,1000},

{1000,1000,1000,1000,1000,1000,1000,1000,1000,1,0,1,1000},

{1,1000,1000,1,1000,1000,1000,1000,1000,1,1,0,1000},

{1000,1000,1000,1000,1,1000,1000,1000,1000,1000,1000,1000,0}, };

for (i = 0; i < 13; i++)

{

p[i,0] = i;k=1;



for (j = 0; j < 13; j++)

if ((a[i, j] != 1000) && (a[i, j] != 0))

{

p[i,k]=j;



k++;

}

p[i,k]=1000;



}

for (i = 0; i < 13; i++)

{

k = 0;


while (p[i,k] != 1000)

{

Console.Write(" {0}", p[i,k]);



k++;

}

Console.WriteLine();



}

// графты жүріп өту

bool b;

// Бастапқы шарттарды беру

for (i = 0; i < 13; i++) nov[i] = true;

vkl(vstek,p[0,0]);

kol = 1;

Console.Write(" {0}", p[0, 0]);

nov[0] = false;

// графты «тереңдігі» бойынша жүріп өту циклі

while (kol != 0)

{ i = (int)vstek.Peek();

if (p[i,0] == 1000) b = false;

else b = !nov[p[i,0]];

// графтың жаңа төбесін іздеу

k = 0;


while (b == true)

{

k++;



if (p[i,k] == 1000) b = false;

else


{

b = !nov[p[i,k]];

if (nov[p[i, k]]) { vkl(vstek, p[i, k]); kol++; }

}

}



if (p[i,k] != 1000)

// егер графтың жаңа төбесі табылса

{

i = p[i,k];



Console.Write(" {0}", i);

nov[i] = false;

}

else


// тізімде жаңа төбе жоқ болса, алдынғы төбеге оралу керек

{

iskl(vstek); i = n; kol--;



}

}

Console.WriteLine();



Console.WriteLine("Enter pernesin basiniz ");

Console.ReadLine();

}

}

}



Бағдарлама жұмысы:

0 1 3 11


1 0 3

2 6


3 0 1 4 6 11

4 3 5 6 8 12

5 4 7 8

6 2 3 4


7 5 8

8 4 5 7


9 10 11

10 9 11


11 0 3 9 10

12 4


0 1 3 4 5 7 8 6 2 12 11 9 10

Enter pernesin basiniz


Бағдарлама басында p[13,13] матрицасы құрылады, онда барлық сыбайлас төбелер тізімі жазылады. Осы тізімдердің мәндерін бақылау үшін олар манитор экранынан шығарылады.

Бағдарламада стек қолданылған, онда біріншіден графтың алғашқы төбе тізімінің тақырыбы жазылады. Графты «тереңдігі» бойынша жүріп өту циклі жұмысының барысында стекке графтың ең кіші жаңа сыбайлас төбелерінің тізім тақырыптары жазылады, олар тақырыбы стек төбесінде орналасқан тізімнен таңдап алынады. Егер осы тізімде жаңа сыбайлас төбе жоқ болса, онда сәйкес тізімнің тақырыбы стектен жойылады, стек төбесі алдыңғы тізімге көшеді.

Графтың сыбайлас төбелер тізімдерінің тақырыптары стекте жоқ болса алгоритм жұмысы аяқталады.

Стектің графты «тереңдігі» бойынша жүріп өту жұмысының бастапқы үзіндісі 13.2-суретінде көрсетілген.



13.2-сурет – Графты «тереңдігі» бойынша жүріп өтудегі стектің жұмысы

13.2-суретте графтың сыбайлас төбелерінің бірінші тізімінен 1-төбе, екінші тізімінен 3-төбе, үшінші тізімінен - 4-төбе, т.б. таңдап алынғаны көрсетілген. Стектің толуына қарай таңдап алынған төбелердің мәндері true (t) мәнінен false (f) мәніне ауысады. 8-төбені қарап шыққаннан кейін стектен 8, 7, 5 төбелері (оларда жаңа төбелер жоқ) жойылады. 4-төбенің тізімінде жаңа 6-шы нөмерлі төбе бар, оның тізімінің тақырыбы стекке қосылады, т.б.




жүктеу 1,63 Mb.

Достарыңызбен бөлісу:
1   ...   65   66   67   68   69   70   71   72   73




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау