Пошук остовного дерева в ширину і пошук в глибину

Якщо взяти в якості V0 вузол Vb. то можна відвідати вершини в порядку

Зауваження 1. Після відвідин нового вузла можна відвідати сусідів нового вузла в довільному порядку. Тут використовується угоду про те, що при необхідності вибору вузли відвідуються в алфавітному порядку.

Зауваження 2. Якщо позначити дугу, що сполучає відвіданий вузол з раніше відвіданих вузлом, то всі ці помічені дуги утворюють кістяк графа G; якщо ж кожна дуга має довжину 1, то кістяк є деревом найкоротших шляхів з V0 в усі інші вузли G.

Пошук в глибину, DFS. Вибираємо довільно вершину V0. а потім слідуємо по ребру Е01 в вузол Vi. потім слідуємо по ребру e12 в вузол V2, сусідній з V1. Вобщем випадку, після відвідування вузла Vi слідуємо по ребру eij в вузол Vj. якщо Vj раніше ще не було відвідано. Далі застосовуємо рекурсивно цей процес до Vj і вибираємо ребро ejk в вузол Vk. Якщо вершина Vj вже переглянуло, то повертаємося в Vi і вибираємо інше ребро. Якщо все ребра, інцидентні Vi. вже вибрані і не можна знайти жодної нової вершини, то повертаємося з Vj в попередню вершину, за якою йде Vi. і перевіряємо їй інцідентние ребра.

Якщо на рис. 11 почати з вершини Vb. то можна відвідати вузли в наступному порядку (упорядкування визначається не єдиним чином):

Дуги, які прямують у нові вершини, утворюють кістяк. Це дуги: ebc. eca. ecd. ede. eef.

Можна порівняти два способи відвідування вузлів. При BFS потрібно перевірити всі ребра, інцидентні вузлу, перед переходом до нового вузлу. Таким чином, операція послідовно виконується віялом з вузлів. При DFS перехід до нового вузлу здійснюється тільки після того, як знайдений новий вузол, і відбувається проникнення в глибину графа. Тільки тоді, коли всі ребра ведуть в старі вершини, йде повернення до попереднього вузла і з нього знову поновлюється DFS.

Алгоритми BFS і DFS мають однакову складність для самого несприятливий випадку. Складність алгоритму для самого несприятливого випадку - це приблизна міра максимального числа дій, необхідних, щоб виконати алгоритм. Це функція розміру вхідних даних, які безпосередньо в нашому випадку були представлені графом (наприклад, О (n)). Так як алгоритми мають однакову складність, то жоден з них не має переваг перед іншим. Проте, для цілого ряду специфічних графів один алгоритм міг би виробляти дерево покриття ефективніше, ніж інший. Наприклад, пошук «по глибині» ефективніше для графа «колеса», а пошук «ширині» для графа «Мальтійський хрест».