Граф (математика): Разлика между версии

<nowiki>[url=https://bg.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B6%D0%B4%D0%B0%D0%BD%D0%B5_%D0%B2_%D0%B4%D1%8A%D0%BB%D0%B1%D0%BE%D1%87%D0%B8%D0%BD%D0%B0]Обхождане в дълбочина[/url] - За разлика от обхождането в ширина, което е неудобно поради това, че е необходимо да се помнят всички обходени върхове (или поне върховете от последното обходено ниво), за да може да се построи следващото ниво. За обхождането в дълбочина са достатъчни само върховете, разположени на пътя от началния до текущия връх. Затова при ограничена компютърна памет за предпочитане са алгоритмите, построени по схемата в дълбочина. От друга страна, ако обхождането се прави с цел да се намери връх със зададени свойства и той се окаже на ниво с по-малък номер, тогава алгоритъмът в ширина ще го намери много по-бързо. Търсенето в дълбочина ще работи непредсказуемо дълго, защото може да се окаже, че върхът е измежду последните обходени (дори и да е на сравнително ниско ниво)</nowiki>

=== Обхождането в широчинаширина ===

<nowiki>[url=https://bg.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B6%D0%B4%D0%B0%D0%BD%D0%B5_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D0%B0]Обхождане в ширина[/url] - съществено за тази алгоритмична схема е понятието ниво на обхождане, което представлява подмножество на множеството от върховете на графа, което в резултат на обхождането в ширина, се разбива на нива. Дърво се нарича краен свързан ацикличен граф имащ поне два върха. Ако даден граф е дърво, то той има един скелет (покриващо дърво), който съвпада с него. Само свързаните графи притежават скелет. В общия случай скелетът на графа не е определен еднозначно. Под обхождане на връх разбираме присъединяването му към дървото, съставено от по-рано обходени върхове. И така, даден е свързан граф, без всякакви ограничения определен връх се избира за корен на бъдещото покриващо дърво на графа, построяването на което е крайния резултат от алгоритмичната схема обхождане в ширина.</nowiki>