Графтар 2. Графтар теориясының негізгі анықтамалары

12.5–сурет – Қарапайым бағытталмаған граф 
Ары қарай k төбесі «тұрақты» болып жарияланады (ол үшінші массивте 
орындалады). Графтың келесі төбесін іздеу алгоритмі жаңа «тұрақты» төбеге 
қатысты қайталанады.
Бірінші төбенің нөмері 0-ге тең деп жорамалдайық. Онда post[…]-бірінші 
массив нөлдерден тұрады. Екінші массивте, яғни ең қысқа қышықтықтар 
массивінде сыбайлас матрицаның нөлінші жолының мәндері жазылады: 
0 1 2 3 4 5 6 7 8
d[min] –
0 3 1000 4 1000 1000 1000 1000 1000 
Үшінші масссив, яғни таңдап алынған (выбранный) төбелер массивінің 
мәндері true болады, тек нөлінші элементте ғана t[0]=false;. 
0-ші төбеден басқа бір төбеге дейінгі ең қысқа аралықты таңдаймыз. Біздің 
жағдайымызда ол 1-ші төбе болады, оған дейінгі қашықтық 3-ке тең болады. Таңдап 
алынған төбе k деп аталсын. Флойд алгоритмін қолданып, алғашқы төбеден “k” 
төбесі арқылы өтетін қалған басқа төбелерге дейінгі барлық ең қысқа маршруттарды 
табамыз. 
for (j=0;j<9;j++) 
if ((t[j]==true)&&(d[j]>d[k]+a[k,j])) 

{ 
d[j]=d[k]+a[k,j]; 
post[j]=k; 
}
нәтижесінде d және post массивтерінің жаңа мәнін аламыз: 
0 1 2 3 4 5 6 7 8 
d[min] – 0 3 7 4 1000 1000 1000 10 1000 
0 1 2 3 4 5 6 7 8 
post[…] – 0 0 1 0 0 0 0 1 0
Бұл 0-2 төбелерінің арасындағы ең қысқа арақашықтық 7-ге тең болатынын 
білдіреді. 
Таңдап алынған k төбесін t[k]=false «тұрақтысымен» жариялаймыз 
және осы төбеге қатысты процесс қайталанып отырады.
Бағдарлама коды: 
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
namespace ConsoleApplication1 
{ 
class Program 
{ 
public static int[,] a = new int[9, 9] 
{{ 0, 3,1000, 4,1000,1000,1000,1000,1000}, 
{ 3, 0, 4,1000,1000,1000,1000, 7,1000}, 
{1000, 4, 0, 5, 2, 4, 4, 6, 9}, 
{ 4,1000, 5, 0, 6,1000,1000,1000,1000}, 
{1000,1000, 2, 6, 0, 5,1000,1000,1000}, 
{1000,1000, 4,1000, 5, 0, 3,1000, 4}, 
{1000,1000, 4,1000,1000, 3, 0,1000, 4}, 
{1000, 7, 6,1000,1000,1000,1000, 0, 8}, 
{1000,1000, 9,1000,1000, 4, 4, 8, 0}}; 
public static int[] d = new int[10]; 
public static int[] post = new int[10]; 
public static bool[] t = new bool[10]; 
public static int i, j, p, k, minras; 
public static void poisk() 
{ 
//алғышарттар 
minras = 0; 
for (i = 0; i < 9; i++) 
{ 
post[i] = 0; 
t[i] = true; 
d[i] = a[0, i]; 
} 

t[0] = false; 
post[0] = 0; 
for (i = 0; i < 8; i++) 
{ 
// k төбесін іздеу 
minras = 1000; 
for (j = 0; j < 9; j++) 
if ((t[j] == true) && (minras > d[j])) 
{ 
minras = d[j]; k = j; 
} 
// k төбесі аркылы маршруттарды іздеу және минимальді 
қашықтықты табу 
t[k] = false; 
for (j = 0; j < 9; j++) 
if ((t[j] == true) && (d[j] > d[k] + a[k, j])) 
{ 
d[j] = d[k] + a[k, j]; 
post[j] = k; 
} 
} 
} 
public static void print() 
{ 
// сыбайлас матрицаны шығару 
Console.WriteLine("Sibailas matrisani shigary: "); 
for (i = 0; i < 9; i++) 
{ 
for (j = 0; j < 9; j++) 
Console.Write("\t" + a[i, j]); 
Console.WriteLine(); 
} 
Console.WriteLine(); 
// минимальді қашықтықтарды сақтайтын массивті шығару 
for (i = 0; i < 9; i++) Console.Write("\t" + i); 
Console.WriteLine(); 
for (i = 0; i < 9; i++) Console.Write("\t" + d[i]); 
Console.WriteLine(); 
//маршруттар массивін шығару 
for (i = 0; i < 9; i++) Console.Write("\t" + post[i]); 
Console.WriteLine(); 
// графтың 0-і төбесінен бастап 8-і төбесіне дейін 
маршрутты шығару
p = 8;
Console.Write("Songi tobe = 8 "); 

do 
{ 
p = post[p]; 
Console.Write("\t" + p); 
} 
while (p != 0);
Console.WriteLine();
Console.WriteLine("Bastapki tobe = 0 "); 
} 
static void Main(string[] args) 
{ 
poisk(); 
print(); 
Console.ReadLine(); 
} 
} 
} 
Бағдарлама жұмысы: 
Sibailas matrisani shigary: 
0 3 1000 4 1000 1000 1000 1000 1000 
3 0 4 1000 1000 1000 1000 7 1000 
1000 4 0 5 2 4 4 6 9 
4 1000 5 0 6 1000 1000 1000 1000 
1000 1000 2 6 0 5 1000 1000 1000 
1000 1000 4 1000 5 0 3 1000 4 
1000 1000 4 1000 1000 3 0 1000 4 
1000 7 6 1000 1000 1000 1000 0 8 
1000 1000 9 1000 1000 4 4 8 0 
0 1 2 3 4 5 6 7 8 
0 3 7 4 9 11 11 10 15 
0 0 1 0 2 2 2 1 5 
Songi tobe = 8 5 2 1 0
Bastapki tobe = 0 
Бағдарлама жұмысының нәтижесі – екі массивті шығару, яғни графтың 
берілген төбесінен қалған төбелеріне дейінгі ең қысқа аралықтар мен ең қысқа 
маршруттардың массивтері. Мысал ретінде графтың 0-ші төбесінен 8-ші төбесіне 
дейінгі ең қысқа маршрут қарастырылады 8-ші мен 0-ші төбелерінің арасындағы ең 
қысқа аралық 15-ке тең. Орын ауыстыру маршруты: 8 – 5 – 2 – 1 – 0. 

жүктеу/скачать 332.21 Kb.

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