Алгоритм поиска в ширину (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
