Месяц: Август 2024

Алгоритм поиска в ширину (Breadth-First Search, BFS) используется для поиска или обхода узлов в графе или дереве. BFS начинает с корневого узла и исследует соседние узлы на каждом уровне, прежде чем переходить к узлам следующего уровня.

Ниже приведен простой пример реализации алгоритма BFS на C#. В этом примере мы будем использовать неориентированный граф, представленный в виде списка смежности.

Пример реализации BFS на C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Создаем граф как словарь списков смежности
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            {0, new List<int> {1, 2}},
            {1, new List<int> {0, 3, 4}},
            {2, new List<int> {0, 5, 6}},
            {3, new List<int> {1}},
            {4, new List<int> {1}},
            {5, new List<int> {2}},
            {6, new List<int> {2}}
        };

        // Вызываем BFS начиная с узла 0
        BFS(graph, 0);
    }

    static void BFS(Dictionary<int, List<int>> graph, int startNode)
    {
        // Очередь для хранения узлов, которые нужно посетить
        Queue<int> queue = new Queue<int>();
        // Хэш-набор для отслеживания посещенных узлов
        HashSet<int> visited = new HashSet<int>();

        // Начинаем с добавления начального узла в очередь и помечаем его как посещенный
        queue.Enqueue(startNode);
        visited.Add(startNode);

        while (queue.Count > 0)
        {
            // Извлекаем узел из очереди
            int currentNode = queue.Dequeue();
            Console.WriteLine("Посещаем узел: " + currentNode);

            // Проходим по всем соседям текущего узла
            foreach (int neighbor in graph[currentNode])
            {
                if (!visited.Contains(neighbor))
                {
                    // Если сосед не был посещен, добавляем его в очередь и помечаем как посещенный
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }
}

Объяснение кода

1. Граф как словарь списков смежности: Граф представлен как словарь, где ключом является узел, а значением — список соседних узлов. Например, узел 0 имеет соседей 1 и 2.

2. Функция BFS:

• Принимает граф и начальный узел.
• Использует очередь (Queue<int>) для хранения узлов, которые нужно посетить, и множество (HashSet<int>) для отслеживания посещенных узлов.
• Начинает с добавления начального узла в очередь и помечает его как посещенный.
• Пока очередь не пуста, узел извлекается из очереди, и его соседи проверяются. Если соседний узел еще не был посещен, он добавляется в очередь и помечается как посещенный.

3. Запуск программы:

• Программа начинает обход графа с узла 0 и посещает все узлы в графе в порядке BFS.

Результат выполнения программы

Посещаем узел: 0
Посещаем узел: 1
Посещаем узел: 2
Посещаем узел: 3
Посещаем узел: 4
Посещаем узел: 5
Посещаем узел: 6