Графтар 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.

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