.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;
        }

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


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

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

9   голосов , оценка 4.778 из 5