78 lines
3.6 KiB
Markdown
78 lines
3.6 KiB
Markdown
#алгоритмы #поиск
|
||
|
||
![[0_HN6Tr71sgf1qR70n.gif]]
|
||
|
||
Эффективность $O(n) = n$
|
||
|
||
> Поиск в ширину работает с графами, позволяет найти кратчайшее расстояние между двумя объектами. Поиск в ширину является алгоритмом обхода; это значит, что он посещает каждый узел дерева («обходит» его). Этот алгоритм находит путь с минимальным количеством сегментов.
|
||
>
|
||
> Отвечает на вопросы 2 типов:
|
||
> - существует ли путь от узла А к узлу В?
|
||
> - как выглядит кратчайший путь от узла А к узлу В?
|
||
|
||
|
||
Связи первого уровня предпочтительнее связей второго уровня, связи второго уровня предпочтительнее связей третьего уровня и т.д. Отсюда следует, что поиск по узлам второго уровня не должен производиться, пока вы не будете полностью уверены в том, что среди связей первого уровня нет ни подходящего элемента.
|
||
Также можно объяснить это иначе: связи первого уровня добавляются в [[Очередь (Queue)]] поиска раньше связей второго уровня.
|
||
|
||
|
||
### Эффективность
|
||
|
||
Если поиск искомого был выполнен по всей сети, значит, вы прошли
|
||
по каждому ребру. Таким образом, время выполнения составляет как минимум $О(количество\_ребер)$.
|
||
Также в программе должна храниться очередь поиска. Добавление одного
|
||
элемента в очередь выполняется за постоянное время: $О(1)$ . Выполнение
|
||
операции для каждого человека потребует суммарного времени $О(количество\_элементов)$.
|
||
Поиск в ширину выполняется за время $О(количество\_элементов+количество\_ребер)$, что обычно записывается в форме $O(V+E)$, где ($V$-количество вершин , $Е$ - количество ребер).
|
||
|
||
|
||
```javascript
|
||
const breadthFirstSearch = (graph, start, end) => {
|
||
const queue = graph[start];
|
||
const checked = [];
|
||
|
||
let lastLevelElement = queue[queue.length - 1];
|
||
let level = 1;
|
||
|
||
|
||
while (queue.length) {
|
||
const candidate = queue.shift();
|
||
|
||
if (candidate === end) {
|
||
return level;
|
||
}
|
||
|
||
if (checked.includes(candidate)) {
|
||
continue;
|
||
}
|
||
|
||
queue.push(...(graph[candidate] || []));
|
||
if (candidate === lastLevelElement) {
|
||
lastLevelElement = queue[queue.length - 1];
|
||
level += 1;
|
||
}
|
||
}
|
||
|
||
return -1;
|
||
}
|
||
|
||
const graph = {
|
||
a: ['b', 'c', 'd'],
|
||
b: ['e', 'f'],
|
||
d: ['e', 'g'],
|
||
c: ['j', 'k']
|
||
}
|
||
|
||
breadthFirstSearch(graph, 'a', 'g'); // 2
|
||
breadthFirstSearch(graph, 'a', 'm'); // -1
|
||
```
|
||
|
||
|
||
![[Pasted image 20250113103049.png]]
|
||
|
||
Связаные темы:
|
||
- [[Граф (Graph)]]
|
||
- [[Очередь (Queue)]]
|
||
- [[Поиск в глубину (Deep-first search)]]
|
||
|
||
Источники:
|
||
- [[Адитья Бхаргава - Грокаем Алгоритмы]] |