Построить маршрут в графе - 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;
        }
    }
}

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


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

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

11   голосов , оценка 4 из 5