Обход взвешенного неориентированного графа - 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();

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.714 из 5
Похожие ответы