.NET 4.x BFS для ориентированного графа - C#
Формулировка задачи:
Имеется граф такого вида.
Что непонятно:
1)Как добавлять смежные вершины в очередь для их проверки?
2)Как вообще организовать этот граф в коде? Предполагалось что смогу организовать его с помощью списка смежности графа, но как видите вышла полная чушь. Был бы очень рад примерам представления графов.
class Width { static void Main(string[] args) { //искомое число int given_number = 8; List<int>[][] list = new List<int>[7][]; //инициализация подмассивов со списками соседей list[0] = new List<int>[1]; list[1] = new List<int>[3]; list[2] = new List<int>[2]; list[3] = new List<int>[2]; list[4] = new List<int>[1]; list[5] = new List<int>[0]; list[6] = new List<int>[0]; list[7] = new List<int>[0]; list[0][0].Add(1); list[1][1].Add(2);// добавление соседей 1 вершины в коллекцию list[1][2].Add(3); list[1][3].Add(4); list[2][1].Add(5);//2 list[2][2].Add(6); list[3][1].Add(7);//3 list[3][2].Add(8); list[4][1].Add(5);//4 int temp; List<int>[]turn = new List<int>[8]; for (int i = 0;i<=3; i++) { for (int j = 0; j <= 4; j++) { for (int s = 0; s < 8; s++) { turn[s] = list[j][i]; // как сравнить значение в коллекции с искомым? if (turn[s] == given_number) Console.WriteLine("Поиск окончен, длин пути равна" + s); else temp = j; //как добавить смежные вершины в очередь?? for (int q = 0; q < temp; q++) turn[s] = list[temp][i]; } } } } }
Решение задачи: «.NET 4.x BFS для ориентированного графа»
textual
Листинг программы
public static void Main(string[] args) { var graph = new List< List<int>>() { { new List<int> {1, 2, 3}}, { new List<int> {4, 5}}, { new List<int> {6, 7}}, { new List<int> {4}}, { new List<int> { }}, { new List<int> { }}, { new List<int> { }}, { new List<int> { }}, }; var path = BreadthFirstSearch(graph, 0); if (path.Count > 1) Console.WriteLine(String.Join(" ", path)); } static List<int> BreadthFirstSearch(List< List<int>> graph, int start) { var path = new List<int>(); var queue = new Queue<int>(); var visited = new List<bool>(new bool[graph.Count]); queue.Enqueue(start); path.Add(start); while (queue.Count > 0) { int v = queue.Dequeue(); foreach (int ver in graph[v]) if (!visited[ver]) { queue.Enqueue(ver); path.Add(ver); visited[ver] = true; } } return path; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д