Ені бойынша іздеуді талдау

$V$V шыңдар жиынтығы және $E$E жиектер жиынтығы бар график үшін ені бойынша іздеу қанша уақытты алады? Жауап - $O (V+E)$O, left parenthesis, V, plus, E, right parenthesis уақыт.

$O(V+E)$O, left parenthesis, V, plus, E, right parenthesisуақыты нені білдіретінін көрейік. Қазіргі уақытта $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar деп есептейік, бұл көптеген графиктерге қатысты, әсіресе біз ені бойынша іздейміз. Содан кейін $|V| + |E| \leq |E| + |E| = 2 \cdot |e|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, e, vertical bar. Біз асимптотикалық белгілеудегі тұрақты факторларды елемейтіндіктен, $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis шынымен $O(E)$O, left parenthesis, E, right parenthesisдегенді білдіреді. Алайда, егер бізде $|E| < |V|$vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar болса, онда $|V| + |E / \leq / V / + / V / = 2 \cdot| V/$vertical bar, V, vertical bar, plus, vertical bar, E, slash, is less than or equal to, slash, V, slash, plus, slash, V, slash, equals, 2, dot, vertical bar, V, slash, сондықтан $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis шынымен $O(V)$O, left parenthesis, V, right parenthesisдегенді білдіреді. $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis шынымен $O(\max(V, E))$O, left parenthesis, \max, left parenthesis, V, comma, E, right parenthesis, right parenthesisдегенді білдіретін екі жағдайды да біріктіре аламыз. Жалпы, егер бізде $x$x және $y$y параметрлері болса, онда $O (x + y)$O, left parenthesis, x, plus, y, right parenthesis шынымен $O(\max(x,y))$O, left parenthesis, \max, left parenthesis, x, comma, y, right parenthesis, right parenthesisдегенді білдіреді.

(Ескерту, егер әр шыңнан басқа шыңдарға апаратын жол болса, графқа байланысты екенін ескеріңіз. Графикте болуы мүмкін және әлі де қосыла алатын жиектердің ең аз саны - $|V|-1$vertical bar, V, vertical bar, minus, 1. $|E| = |V|-1$vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1 болатын График еркін ағаш деп аталады.)

Ені бойынша іздеу $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis уақыт аралығында қалай жасалады? Қашықтықты және ісшарасын (предшественникті) инициализациялау үшін әр шыңға $O(V)$O, left parenthesis, V, right parenthesis уақыт қажет (іс жүзінде $\Theta(V)$\Theta, left parenthesis, V, right parenthesis уақыт). Әр шыңға бір реттен көп емес барады, өйткені бірінші рет жеткенде ғана оның қашықтығы нөлге тең болады, сондықтан әр шың кезекке бір реттен артық қойылмайды. Біз шыңға құлаған жиектерді тек біз кірген кезде зерттейтіндіктен, әр шеті екі реттен көп емес, әр шыңы үшін бір рет зерттеледі. Осылайша, ені бойынша іздеу ең алдымен шыңдарға бару үшін $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis жұмсайды.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.