Берілген екі төбе арасындағы барлық маршруттарды іздеу алгоритмі

13.2 Берілген екі төбе арасындағы барлық маршруттарды іздеу алгоритмі

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

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

13.1-есеп. Сыбайлас матрицамен (13.1-кесте) берілген 13.3-суреттегі граф үшін диалог режімінде берілетін екі төбе арасындағы барлық маршрутты табатын бағдарламаны кұру керек.

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

using System;

using System.Collections;

using System.Text;

namespace ConsoleApplication1

{

class Program

public static int i, j, k, kol;

public struct uzel

{

public int nom;

public int kj;

};

public static uzel n = new uzel();

{

vst.Push(n);

static void iskl(Stack vst)

{

if (vst == null) Console.WriteLine("Стек бос !");

}

public static void Main()

Stack vstek = new Stack();

string buf;

int beg, en, x, i1, i2;

uzel y1 = new uzel();

bool[] nov = new bool[10];

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

int[] m = new int[10];

//графтың сыбайлас матрицасы

int[,] a = new int[9, 9]

{{ 0, 6,1000, 4,1000,1000,1000,1000,1000},

{ 6, 0, 5,1000,1000,1000,1000, 4,1000},

{1000, 5, 0, 3, 4,1000, 5, 6,1000},

{ 4,1000, 3, 0, 7,1000,1000,1000,1000},

{1000,1000, 4, 7, 0, 5,1000,1000,1000},

{1000,1000,1000,1000, 5, 0, 4,1000, 9},

{1000,1000, 5,1000,1000, 4, 0,1000, 6},

{1000, 4, 6,1000,1000,1000,1000, 0, 8},

{1000,1000,1000,1000,1000, 9, 6, 8, 0}};

//а матрицасы бойынша сыбайлас төбелер тізімін құру

for (i = 0; i < 9; 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 < 9; i++)

{

k = 0;

{

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

}

Console.WriteLine();

Console.Write("Graftin bastapki tobesin engiziniz? ");

buf = Console.ReadLine();

beg = Convert.ToInt32(buf);

Console.Write("Graftin akirgi tobesin engiziniz? ");

buf = Console.ReadLine();

en = Convert.ToInt32(buf);

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

{

nov[i] = true;

}

nov[9] = false;

m[1] = beg; i1 = 2;

y1.nom = beg; //y1 түйңнінің nom өрісін анықтаймыз

y1.ki = beg; //сыбайлас төбелер тізімінің нөмерін сақтаймыз

y1.kj = 0; // тізімдегі ағымдағы орнын сақтаймыз

vkl(vstek, y1);

kol = 1; //стектегі элементтер саны

nov[beg] = false;

nov[en] = false;

i = beg; j = 0;

// графтағы барлық маршруттарды іздеу циклі

while (kol != 0)

{

do

{

if (p[i, j] == en)

{

Console.Write(" Жол - {0} -", x); x++;

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

Console.WriteLine(" {0}", en);

}

}

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

if (nov[p[i, j]])

{

y1.ki = i;

i = p[i, j];

y1.nom = i;

vkl(vstek, y1);

j = 0;

kol++;

m[i1] = i;

i1++;

};
if (p[i, j] == 1000)

kol--;

{

iskl(vstek);

j = n.kj;

i1--;

m[i1] = 0;

}

};

Console.WriteLine();

Console.WriteLine("Enter pernesin basiniz");

Console.ReadLine();

}

}

}

0 1 3

2 1 3 4 6 7

3 0 2 4

4 2 3 5

6 2 5 8

8 5 6 7

Graftin akirgi tobesin engiziniz? 4

Жол - 1 - 1 0 3 2 4

Жол - 2 - 1 0 3 2 6 5 4

Жол - 3 - 1 0 3 2 6 8 5 4

Жол - 4 - 1 0 3 2 7 8 5 4

Жол - 5 - 1 0 3 2 7 8 6 5 4

Жол - 6 - 1 0 3 4

Жол - 7 - 1 2 3 4

Жол - 8 - 1 2 4

Жол - 9 - 1 2 6 5 4

Жол - 10 - 1 2 6 8 5 4

Жол - 11 - 1 2 7 8 5 4

Жол - 12 - 1 2 7 8 6 5 4

Жол - 13 - 1 7 2 3 4

Жол - 14 - 1 7 2 4

Жол - 15 - 1 7 2 6 5 4

Жол - 16 - 1 7 2 6 8 5 4

Жол - 17 - 1 7 8 5 4

Жол - 18 - 1 7 8 5 6 2 3 4

Жол - 19 - 1 7 8 5 6 2 4

Жол - 20 - 1 7 8 6 2 3 4

Жол - 21 - 1 7 8 6 2 4

Жол - 22 - 1 7 8 6 5 4

0 1 3

2 1 3 4 6 7

3 0 2 4

4 2 3 5

6 2 5 8

8 5 6 7

Graftin akirgi tobesin engiziniz? 6

Жол - 1 - 6 2 1 0 3 4 5 6

Жол - 2 - 6 2 1 0 3 4 5 8 6

Жол - 3 - 6 2 1 7 8 5 6

Жол - 4 - 6 2 1 7 8 6

Жол - 5 - 6 2 3 0 1 7 8 5 6

Жол - 6 - 6 2 3 0 1 7 8 6

Жол - 7 - 6 2 3 4 5 6

Жол - 8 - 6 2 3 4 5 8 6

Жол - 9 - 6 2 4 3 0 1 7 8 5 6

Жол - 10 - 6 2 4 3 0 1 7 8 6

Жол - 11 - 6 2 4 5 6

Жол - 12 - 6 2 4 5 8 6

Жол - 13 - 6 2 6

Жол - 14 - 6 2 7 1 0 3 4 5 6

Жол - 15 - 6 2 7 1 0 3 4 5 8 6

Жол - 16 - 6 2 7 8 5 6

Жол - 17 - 6 2 7 8 6

Жол - 18 - 6 5 4 2 1 7 8 6

Жол - 19 - 6 5 4 2 3 0 1 7 8 6

Жол - 20 - 6 5 4 2 6

Жол - 21 - 6 5 4 2 7 8 6

Жол - 22 - 6 5 4 3 0 1 2 6

Жол - 23 - 6 5 4 3 0 1 2 7 8 6

Жол - 24 - 6 5 4 3 0 1 7 2 6

Жол - 25 - 6 5 4 3 0 1 7 8 6

Жол - 26 - 6 5 4 3 2 1 7 8 6

Жол - 27 - 6 5 4 3 2 6

Жол - 28 - 6 5 4 3 2 7 8 6

Жол - 29 - 6 5 6

Жол - 30 - 6 5 8 6

Жол - 31 - 6 5 8 7 1 0 3 2 6

Жол - 32 - 6 5 8 7 1 0 3 4 2 6

Жол - 33 - 6 5 8 7 1 2 6

Жол - 34 - 6 5 8 7 2 6

Жол - 35 - 6 8 5 4 2 6

Жол - 36 - 6 8 5 4 3 0 1 2 6

Жол - 37 - 6 8 5 4 3 0 1 7 2 6

Жол - 38 - 6 8 5 4 3 2 6

Жол - 39 - 6 8 5 6

Жол - 40 - 6 8 6

Жол - 41 - 6 8 7 1 0 3 2 4 5 6

Жол - 42 - 6 8 7 1 0 3 2 6

Жол - 43 - 6 8 7 1 0 3 4 2 6

Жол - 44 - 6 8 7 1 0 3 4 5 6

Жол - 45 - 6 8 7 1 2 3 4 5 6

Жол - 46 - 6 8 7 1 2 4 5 6

Жол - 47 - 6 8 7 1 2 6

Жол - 48 - 6 8 7 2 1 0 3 4 5 6

Жол - 49 - 6 8 7 2 3 4 5 6

Жол - 50 - 6 8 7 2 4 5 6

Жол - 51 - 6 8 7 2 6
Enter pernesin basiniz
Әдетте барлық маршруттарды іздестірудің while циклінде do_while циклі мен екі if операторы орналасады.

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

Егер графтың табылған төбесі «жаңа» болса, онда бірінші if операторында алгоритм әрекеттері сипатталады.

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