Анализ на търсене по широчина

Колко време отнема обхождането в широчина на граф с $V$‍ върха и $E$‍ ребра? Отговорът е $O(V+E)$‍.

Да видим какво означава времето $O(V+E)$‍. Засега нека приемем, че $|E|\ge |V|$‍, което е валидно за повечето графи, особено за тези, за които изпълняваме обхождане в ширина. Тогава $|V|+|E|\le |E|+|E|=2\cdot |E|$‍. Тъй като игнорираме константите в асимптотичната нотация, виждаме, че, когато $|E|\ge |V|$‍, $O(V+E)$‍ означава $O(E)$‍. Ако обаче имаме $|E|<|V|$‍, тогава $|V|+|E|\le |V|+|V|=2\cdot |V|$‍, и така $O(V+E)$‍ означава $O(V)$‍. Можем да съберем двата случая, като кажем, че $O(V+E)$‍ означава $O(max(V,E))$‍. Като цяло, ако имаме параметрите $x$‍ и $y$‍, то $O(x+y)$‍ означава $O(max(x,y))$‍.

(Забележи, че графът е свързан, ако има път от всеки връх към всички останали върхове. Минималният брой ребра, които може да има един граф и да бъде свързан, е $|V|-1$‍. А граф, в който $|E|=|V|-1$‍ се нарича свободно дърво.)

Как така обхождането в ширина се изпълнява за време $O(V+E)$‍? Инициализирането на разстоянието и предшественика на всеки връх отнема време $O(V)$‍ (всъщност време $\mathrm{\Theta }(V)$‍). Всеки връх се посещава най-много веднъж, защото само първият път, когато е достъпен, е неговото разстояние null, и така всеки връх се обхожда поне веднъж. Тъй като разглеждаме ребрата, съседни на един връх, само когато го посещаваме, всяко ребро се разглежда най-много два пъти – по веднъж за всеки връх, който свързва. Така посещаването на върховете при обхождането в ширина отнема $O(V+E)$‍.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.