Поиск в ширину с помощью списка инцидентности в ориентированном графе - C#
Формулировка задачи:
Здравствуйте, коллеги!
Помогите пожалуйста с реализацией поиска в ширину с помощью списка инцидентности для случая когда граф ориентированный.
Заранее спасибо!
Решение задачи: «Поиск в ширину с помощью списка инцидентности в ориентированном графе»
textual
Листинг программы
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Graf { class Program { static void Main(string[] args) { BFS graf = new BFS(); graf.readgr(); Console.WriteLine("Выберете начальную вершину для поиска в ширину (от 1 до 6)"); try { int key = int.Parse(Console.ReadLine()); graf.bfs(key); } catch (System.Exception ex) { } } } class BFS { const int vert = 6; const int rib = 6; int[,] gr; int[] vstd; public void readgr() { gr = new int[rib, vert]; gr[0, 0] = -1; gr[0, 1] = 0; gr[0, 2] = 0; gr[0, 3] = 0; gr[0, 4] = 0; gr[0, 5] = 1; gr[1, 0] = 0; gr[1, 1] = 0; gr[1, 2] = 0; gr[1, 3] = 0; gr[1, 4] = 1; gr[1, 5] = -1; gr[2, 0] = 0; gr[2, 1] = 0; gr[2, 2] = 0; gr[2, 3] = 1; gr[2, 4] = -1; gr[2, 5] = 0; gr[3, 0] = 0; gr[3, 1] = 0; gr[3, 2] = 1; gr[3, 3] = -1; gr[3, 4] = 0; gr[3, 5] = 0; gr[4, 0] = 0; gr[4, 1] = 1; gr[4, 2] = -1; gr[4, 3] = 0; gr[4, 4] = 0; gr[4, 5] = 0; gr[5, 0] = 1; gr[5, 1] = -1; gr[5, 2] = 0; gr[5, 3] = 0; gr[5, 4] = 0; gr[5, 5] = 0; Console.WriteLine(" v1 v2 v3 v4 v5 v6"); for (int i = 0; i < rib; i++) { Console.Write("rib " + (i + 1).ToString() + " |"); for (int j = 0; j < vert; j++) { if (gr[i, j] == -1) { Console.Write(" " + gr[i, j] + " "); } else Console.Write(" " + gr[i, j] + " "); } Console.Write("|\n"); } vstd = new int[vert]; for (int i = 0; i < vert; i++) //инициализируем массив меток vstd[i] = 0; } public void bfs(int source) { vstd[source--] = 1; bool okflag = true; while (okflag) { for (int i = 0; i < vert; i++) { if (vstd[i] == 2) { for (int j = 0; j < vert; j++) { if (gr[i,j] == -1) if (vstd[j] == 0) { vstd[j] = 1; Console.Write("v" + (j + 1).ToString()); } } vstd[i] = 3; } } for (int i = 0; i < vert; i++) { if (vstd[i] == 1) vstd[i] = 2; } okflag = false; for (int i = 0; i < vert; i++) if (vstd[i] < 2) okflag = true; Console.Write("\n"); } } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д