поиск в ширину

Also known as BFS, breadth first search

метод обхода графа и поиска пути в графе

Key facts

Class: Search algorithm
Data structure: Graph
Worst case performance: O ( | V | + | E | ) {\displaystyle O(|V|+|E|)}
Worst case space complexity: O ( | V | ) {\displaystyle O(|V|)}
Optimal: Yes (always finds shortest paths)

via Wikipedia infobox

Wikidata facts

Subclass of: graph traversal
Image: Breadth-first-tree.svg

Show 7 more facts

time of discovery or invention: 1945-00-00
Commons category: Breadth-first search
Stack Exchange tag: stackoverflow.com/tags/breadth-first-search
uses: FIFO
discoverer or inventor: Konrad Zuse
short name: BFS
described at URL: www.javatpoint.com/ai-uninformed-search-algorithms

Sources (6)

via Wikidata · CC0

Article · Русский

Поиск в ширину (англ. breadth-first search, BFS) — один из методов обхода графа. Пусть задан граф и выделена исходная вершина . Алгоритм поиска в ширину систематически обходит все ребра для «открытия» всех вершин, достижимых из , вычисляя при этом расстояние (минимальное количество рёбер) от до каждой достижимой из вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов. Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии , выполняется обход вершин на расстоянии . Поиск в ширину является одним из неинформированных алгоритмов поиска.

Abstract from DBpedia / Wikipedia · CC BY-SA