Поиск в ширину – это алгоритм графа, используемый для
- Чтобы проверить, есть ли путь между двумя вершинами/узлами
- Чтобы получить кратчайший путь между двумя узлами
- Выполнить обход всего графа, т.е. посетить каждый узел в данном графе.
Временная сложность
Временная сложность алгоритма поиска в ширину составляет O(v+e). Где v — количество вершин/узлов, а e — количество ребер.
Объяснение
Давайте возьмем пример, предположим, что мы хотим увидеть, существует ли путь между двумя узлами в графе, и в худшем случае узел «b» может быть в конце граф, поэтому мы должны сначала пройти через каждый узел в графе, чтобы добраться до него. И временная сложность для этого будет O(n), где n — количество вершин/узлов в графе, которое мы также можем записать как O(v).
При обходе каждого узла мы должны проверить его «соседские или можно сказать его края». Например, если к узлу «с» прикреплено 3 ребра/соседня, мы должны выполнить 3 операции над узлом «с». И временная сложность для этого снова будет O (n), где n — количество ребер, которые имеет конкретный узел, что мы также можем записать как O (e).
Объединив оба, мы получим общую временную сложность O (V + E)
- (V: потому что в худшем случае мы собираемся посетить каждый узел)
- (E: общее количество ребер в графе, потому что на каждом узле мы также должны посетить/проверить его ребра.
В приведенном ниже примере кода проверяется, существует ли путь между узлом (1) и узлом (2) в ориентированном графе. И если есть, он напечатает путь между этими двумя узлами, и снова этот путь будет кратчайшим возможным путем между этими двумя узлами.
