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

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!");

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;

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

{

p[i,k]=j;

}

p[i,k]=1000;

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

{

k = 0;

{

Console.Write(" {0}", p[i,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;

{

k++;

else

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

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

}

}

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

{

i = p[i,k];

nov[i] = false;

}

else

{

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

}

Console.WriteLine();

Console.ReadLine();

}

}

}

0 1 3 11

2 6

4 3 5 6 8 12

5 4 7 8

6 2 3 4

8 4 5 7

10 9 11

12 4

Enter pernesin basiniz

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

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

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

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