Построить маршрут в графе - C#
Формулировка задачи:
Здравствуйте, необходимо построить маршрут заданной длины из заданной вершины. По факту, вывести в консоль
вершины, через которые проходит этот маршрут. Граф предоставляется матрицей смежности.
Вот я не могу придумать алгоритм, чтобы он это делал.
Граф нарисовал "от балды". Попробовал на нем представить как оно должно работать, но что-то попытки тщетны.
Решение задачи: «Построить маршрут в графе»
textual
Листинг программы
using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication190 { class Program { static void Main(string[] args) { // [url]https://upload.wikimedia.org/wikipedia/commons/thumb/2/28/6n-graph2.svg/375px-6n-graph2.svg.png[/url] var matrix = new int[,] { {1, 1, 0, 0, 1, 0}, {1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 1}, {1, 1, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0} }; var result = FindPath(2, 4, matrix); Console.WriteLine(string.Join(", ", result.Select(i=>i.ToString()).ToArray())); Console.ReadLine(); } static List<int> FindPath(int from, int to, int[,] matrix) { //множество посещенных вершин var was = new HashSet<int>(); var list = new List<int>(); list.Add(from); was.Add(from); var res = FindPath(from, to, matrix, was, list); if (res) return list; else return null; } static bool FindPath(int from, int to, int[,] matrix, HashSet<int> was, List<int> list) { if (from == to) return true; for(int i=0;i<matrix.GetLength(1); i++) if(matrix[from, i] > 0) if(!was.Contains(i)) { list.Add(i); was.Add(i); if (FindPath(i, to, matrix, was, list)) return true; list.RemoveAt(list.Count - 1); } return false; } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д