Поиск в ширину, глубину в графе - C#

Узнай цену своей работы

Формулировка задачи:

Есть ли у кого программка для поиска в ширину/в глубину на графах с использованием матрицы смежности? (С#)

Решение задачи: «Поиск в ширину, глубину в графе»

textual
Листинг программы
  1. using System;
  2. using System.Collections;
  3. using System.Text;
  4.  
  5. namespace ConsoleApplication1
  6. {
  7.     class Program
  8.     {
  9.         public static int i, j, k, n, kol;
  10.         //алгоритмді алдыТЈТ“ы Т›алпына «Т›айтаруды» орындау ТҐшін стекттерді Т›олданады, графты  жТҐріп У›ткен кезде
  11.        //tizimge jana elementti kosu adisi
  12.         static void vkl(Stack vst, int n)
  13.         { vst.Push(n); }
  14.         //tizimnen elementti joyu
  15.         static void iskl(Stack vst)
  16.         {
  17.             if (vst == null)//eger tizim sonina barsa
  18.                 Console.WriteLine("Stek bos!");
  19.             else n = (int)vst.Pop();
  20.         }
  21.         //Bagdarlama basi
  22.         //
  23.         public static void Main()
  24.         {
  25.             Stack vstek = new Stack();//Stack kurilimin kurdik
  26.             //int i, j, k, n;  
  27.             bool[] nov = new bool[16];//16 tobe simvoldar turinde
  28.             int[,] p = new int[16, 16];//p matricasi jol boyinwa tekseru uwin
  29.             int[,] a = new int[16, 16]//a matricasi bagan boyinwaa
  30. //16-16 matrica kurip alasin grafta eger tobeler baylanissa 0 dep alasin, baylanispasa 1000 oz ozine ten bolsa 0
  31.       {{0, 1,1000,1000, 1, 1000, 1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000},//0
  32. {1, 0, 1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000},//1
  33. {1000,1,0,1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000},//2
  34. {1000,1000,1,0,1000,1000,1000,1,1000,1000,1000,1000,1000,1000,1000,1000},//3
  35. {1,1000,1000,1000,0,1,1000,1000,1,1000,1000,1000,1000,1000,1000,1000}, //4
  36. {1000,1000,1000,1000,1,0,1,1000,1000,1000,1000,1000,1000,1000,1000,1000},//5
  37. {1000,1000,1000,1000,1000,1,0,1,1000,1000,1000,1000,1000,1000,1000,1000},//6
  38. {1000,1000,1000,1,1000,1000,1,0,1000,1000,1000,1,1000,1000,1000,1000},//7
  39. {1000,1000,1000,1000,1,1000,1000,1000,0,1,1000,1000,1,1000,1000,1000},//8
  40. {1000,1000,1000,1000,1000,1000,1000,1000,1,0,1,1000,1000,1000,1000,1000},//9
  41. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1,0,1,1000,1000,1000,1000},//10
  42. {1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1,0,1000,1000,1000,1},//11
  43. {1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1000,1000,0,1,1000,1000},//12
  44. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1000,1000,0,1,1000},//13
  45. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1,0,1},//14
  46. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1000,1,0}};//15
  47.             //Sibailas tobelerdi kuru algoritmi
  48.             for (i = 0; i < 16; i++)
  49.             {
  50.                 p[i, 0] = i; k = 1;//birinwi turgan tobelerden
  51.                 for (j = 0; j < 16; j++)
  52.                     if ((a[i, j] != 1000) && (a[i, j] != 0))//eger tobeler baylanispagan jane oz ozine ten bolsa
  53.                     { p[i, k] = j; k++; }// Sibaylaskan tobelerdi tabadi
  54.                 p[i, k] = 1000;
  55.             }
  56.             //Olardi ekranga wigaradi
  57.             for (i = 0; i < 16; i++)
  58.             {
  59.                 k = 0; while (p[i, k] != 1000)//p matricasindagi 1000 baska barlik tobelerdi wigaru
  60.                 { Console.Write(" {0}", p[i, k]); k++; }
  61.                 Console.WriteLine();
  62.             }
  63.             Console.WriteLine();
  64.             // Graftin  Gamiltondi jurip otuine terendigi boyinwa jurip otu algoritmin koldandik
  65.             Console.WriteLine(" Graftin Gamilton cikli boinsha jurip otui:");
  66.             bool b;
  67.             // БастапТ›ы шарттарды беру  
  68.             for (i = 0; i < 16; i++)
  69.                 nov[i] = true;//jana tobe karaladi
  70.             vkl(vstek, p[0, 0]); kol = 1;//tizimge jana tobe kosiladi
  71.             Console.Write(" {0}", p[0, 0]);
  72.             nov[0] = false;//birinwi tobe karalmaydi
  73.             // графты «тереТЈдігі» бойынша жyріп 0ту цикл
  74.             while (kol != 0)
  75.             {
  76.                 i = (int)vstek.Peek();//Graftin elementin kaytaradi
  77.                 if (p[i, 0] == 1000) b = false;//eger 1000 ten bolsa tobe karalmaydi
  78.                 else b = !nov[p[i, 0]];//onda b jana tobesi tabilmaydi
  79.                 // графтыТЈ жаТЈа тoбесін іздеу
  80.                 k = 0; while (b == true)//b tobe kkaralatin bolsa
  81.                 {
  82.                     k++; if (p[i, k] == 1000)//eger 1000 ten bolsa
  83.                //onda b tobesi karalmaydi
  84.                         b = false;
  85.                         //onda
  86.                     else
  87.                     {
  88.                         //onda b jana tobesi tabilmaydi
  89.                         b = !nov[p[i, k]];
  90.                         //eger jana tobe sibaylas tobeler tiziminde bolsa
  91.                         if (nov[p[i, k]])
  92.                             //  jana tobe tabiladi
  93.                         { vkl(vstek, p[i, k]); kol++; }
  94.                     }
  95.                 }
  96.                 if (p[i, k] != 1000)   // егер графтыТЈ жаТЈа тoбесі табылса  
  97.                 {
  98.                     i = p[i, k];
  99.  
  100.                     Console.Write(" {0} ", i); nov[i] = false;
  101.                 }
  102.  
  103.  
  104.                 else  // тізімде жаТЈа тoбе жоТ› болса, алдынТ“ы тУ›беге оралу керек  
  105.                 { iskl(vstek); i = n; kol--; }
  106.             } Console.WriteLine();
  107.             Console.WriteLine("Enter pernesin basiniz ");
  108.             Console.ReadLine();
  109.         }
  110.     }
  111. }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4.143 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы