Обход взвешенного неориентированного графа - C#
Формулировка задачи:
Всем привет. Стоит задача обойти и начальной вершины все вершины графа и вернуться в исходную. Граф неориентированный, взвешенный, каждая вершина связана с другими. Нужно найти оптимальный обход по весам. Сделал следующее. Для каждой вершины ищу наименьший вес среди смежных с ним вершин и иду по этому ребру (код не тестировал, но с виду должен работать)
Как изменить код, чтобы находился минимальный из возможных вариантов?
public int[] SearchOptimalWay(int[,] grafMatrix) { List<int> way = new List<int>(); way.Add(0); for (int i = 0; i < grafMatrix.GetLength(0); i++) { int min = int.MaxValue; int minIndex = -1; //search minimum for (int j = 0; j < grafMatrix.GetLength(1); j++) { if (!Dublicated(way, j) && grafMatrix[i, j] <= min && i != j) { min = grafMatrix[i, j]; minIndex = j; } } way.Add(minIndex); } return way.ToArray(); } private bool Dublicated(List<int> way, int j) { for (int i = 0; i < way.Count; i++) { if (j == way[i]) return true; } return false; }
Решение задачи: «Обход взвешенного неориентированного графа»
textual
Листинг программы
int min = array.Min();
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д