“parcourslargeur (noeud)” — это французский термин, который переводится как “поиск в ширину (узел)” на английском языке. Поиск в ширину – это алгоритм обхода графа, который исследует все вершины графа в порядке ширины, посещая всех соседей вершины, прежде чем перейти к следующему уровню вершин.

В этой статье блога я объясню алгоритм поиска в ширину и приведу примеры кода на разных языках программирования. Давайте погрузимся!

Алгоритм поиска в ширину:
Поиск в ширину начинается с заданного узла (или вершины) графа и исследует всех его соседей, прежде чем перейти к следующему уровню вершин. Он использует структуру данных очереди для отслеживания посещаемых вершин. Алгоритм работает следующим образом:

1. Создайте пустую очередь и поставьте в нее начальный узел.
2. Создайте набор или массив для отслеживания посещенных узлов.
3. Пока очередь не пуста, выполните следующие действия:
   a. Удалить вершину из очереди.
   b. Отметьте вершину как посещенную.
   c. Обработать вершину (например, распечатать ее или выполнить любую другую желаемую операцию).
   d. Поставьте в очередь всех непосещенных соседей вершины.
4. Повторяйте шаги 3, пока очередь не станет пустой.

Теперь давайте посмотрим на реализацию алгоритма поиска в ширину на разных языках программирования:

1. Python:

   from collections import deque
   def breadth_first_search(graph, start_node):
   visited = set()
   queue = deque([start_node])
   while queue:
       node = queue.popleft()
       if node not in visited:
           visited.add(node)
           print(node)  # Process the node here
           for neighbor in graph[node]:
               if neighbor not in visited:
                   queue.append(neighbor)
   # Example usage
   graph = {
   'A': ['B', 'C'],
   'B': ['D'],
   'C': ['E'],
   'D': [],
   'E': []
   }
   start_node = 'A'
   breadth_first_search(graph, start_node)

2. Java:

   import java.util.*;
   class BreadthFirstSearch {
   public void breadthFirstSearch(Map<Integer, List<Integer>> graph, int startNode) {
       Set<Integer> visited = new HashSet<>();
       Queue<Integer> queue = new LinkedList<>();
       queue.add(startNode);
       while (!queue.isEmpty()) {
           int node = queue.remove();
           if (!visited.contains(node)) {
               visited.add(node);
               System.out.println(node);  // Process the node here
               for (int neighbor : graph.get(node)) {
                   if (!visited.contains(neighbor)) {
                       queue.add(neighbor);
                   }
               }
           }
       }
   }
   public static void main(String[] args) {
       Map<Integer, List<Integer>> graph = new HashMap<>();
       graph.put(1, Arrays.asList(2, 3));
       graph.put(2, Arrays.asList(4));
       graph.put(3, Arrays.asList(5));
       graph.put(4, new ArrayList<>());
       graph.put(5, new ArrayList<>());
       int startNode = 1;
       BreadthFirstSearch bfs = new BreadthFirstSearch();
       bfs.breadthFirstSearch(graph, startNode);
   }
   }

3. JavaScript:

   function breadthFirstSearch(graph, startNode) {
   const visited = new Set();
   const queue = [startNode];
   while (queue.length > 0) {
       const node = queue.shift();
       if (!visited.has(node)) {
           visited.add(node);
           console.log(node);  // Process the node here
           for (const neighbor of graph[node]) {
               if (!visited.has(neighbor)) {
                   queue.push(neighbor);
               }
           }
       }
   }
   }
   // Example usage
   const graph = {
   'A': ['B', 'C'],
   'B': ['D'],
   'C': ['E'],
   'D': [],
   'E': []
   };
   const startNode = 'A';
   breadthFirstSearch(graph, startNode);

Это всего лишь несколько примеров реализации алгоритма поиска в ширину на разных языках программирования. Вы можете настроить код в соответствии со своими требованиями.