Поиск в ширину, глубину в графе - C#
Формулировка задачи:
Есть ли у кого программка для поиска в ширину/в глубину на графах с использованием матрицы смежности? (С#)
Решение задачи: «Поиск в ширину, глубину в графе»
textual
Листинг программы
using System; using System.Collections; using System.Text; namespace ConsoleApplication1 { class Program { public static int i, j, k, n, kol; //алгоритмді алдыТЈТ“ы Т›алпына «Т›айтаруды» орындау ТҐшін стекттерді Т›олданады, графты жТҐріп У›ткен кезде //tizimge jana elementti kosu adisi static void vkl(Stack vst, int n) { vst.Push(n); } //tizimnen elementti joyu static void iskl(Stack vst) { if (vst == null)//eger tizim sonina barsa Console.WriteLine("Stek bos!"); else n = (int)vst.Pop(); } //Bagdarlama basi // public static void Main() { Stack vstek = new Stack();//Stack kurilimin kurdik //int i, j, k, n; bool[] nov = new bool[16];//16 tobe simvoldar turinde int[,] p = new int[16, 16];//p matricasi jol boyinwa tekseru uwin int[,] a = new int[16, 16]//a matricasi bagan boyinwaa //16-16 matrica kurip alasin grafta eger tobeler baylanissa 0 dep alasin, baylanispasa 1000 oz ozine ten bolsa 0 {{0, 1,1000,1000, 1, 1000, 1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000},//0 {1, 0, 1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000},//1 {1000,1,0,1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000},//2 {1000,1000,1,0,1000,1000,1000,1,1000,1000,1000,1000,1000,1000,1000,1000},//3 {1,1000,1000,1000,0,1,1000,1000,1,1000,1000,1000,1000,1000,1000,1000}, //4 {1000,1000,1000,1000,1,0,1,1000,1000,1000,1000,1000,1000,1000,1000,1000},//5 {1000,1000,1000,1000,1000,1,0,1,1000,1000,1000,1000,1000,1000,1000,1000},//6 {1000,1000,1000,1,1000,1000,1,0,1000,1000,1000,1,1000,1000,1000,1000},//7 {1000,1000,1000,1000,1,1000,1000,1000,0,1,1000,1000,1,1000,1000,1000},//8 {1000,1000,1000,1000,1000,1000,1000,1000,1,0,1,1000,1000,1000,1000,1000},//9 {1000,1000,1000,1000,1000,1000,1000,1000,1000,1,0,1,1000,1000,1000,1000},//10 {1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1,0,1000,1000,1000,1},//11 {1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1000,1000,0,1,1000,1000},//12 {1000,1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1000,1000,0,1,1000},//13 {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1,0,1},//14 {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1,1000,1000,1,0}};//15 //Sibailas tobelerdi kuru algoritmi for (i = 0; i < 16; i++) { p[i, 0] = i; k = 1;//birinwi turgan tobelerden for (j = 0; j < 16; j++) if ((a[i, j] != 1000) && (a[i, j] != 0))//eger tobeler baylanispagan jane oz ozine ten bolsa { p[i, k] = j; k++; }// Sibaylaskan tobelerdi tabadi p[i, k] = 1000; } //Olardi ekranga wigaradi for (i = 0; i < 16; i++) { k = 0; while (p[i, k] != 1000)//p matricasindagi 1000 baska barlik tobelerdi wigaru { Console.Write(" {0}", p[i, k]); k++; } Console.WriteLine(); } Console.WriteLine(); // Graftin Gamiltondi jurip otuine terendigi boyinwa jurip otu algoritmin koldandik Console.WriteLine(" Graftin Gamilton cikli boinsha jurip otui:"); bool b; // БастапТ›ы шарттарды беру for (i = 0; i < 16; i++) nov[i] = true;//jana tobe karaladi vkl(vstek, p[0, 0]); kol = 1;//tizimge jana tobe kosiladi Console.Write(" {0}", p[0, 0]); nov[0] = false;//birinwi tobe karalmaydi // графты «тереТЈдігі» бойынша жyріп 0ту цикл while (kol != 0) { i = (int)vstek.Peek();//Graftin elementin kaytaradi if (p[i, 0] == 1000) b = false;//eger 1000 ten bolsa tobe karalmaydi else b = !nov[p[i, 0]];//onda b jana tobesi tabilmaydi // графтыТЈ жаТЈа тoбесін іздеу k = 0; while (b == true)//b tobe kkaralatin bolsa { k++; if (p[i, k] == 1000)//eger 1000 ten bolsa //onda b tobesi karalmaydi b = false; //onda else { //onda b jana tobesi tabilmaydi b = !nov[p[i, k]]; //eger jana tobe sibaylas tobeler tiziminde bolsa if (nov[p[i, k]]) // jana tobe tabiladi { vkl(vstek, p[i, k]); kol++; } } } if (p[i, k] != 1000) // егер графтыТЈ жаТЈа тoбесі табылса { i = p[i, k]; Console.Write(" {0} ", i); nov[i] = false; } else // тізімде жаТЈа тoбе жоТ› болса, алдынТ“ы тУ›беге оралу керек { iskl(vstek); i = n; kol--; } } Console.WriteLine(); Console.WriteLine("Enter pernesin basiniz "); Console.ReadLine(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д