Търсене обхваща дърво в ширина и дълбочина и първи търсене

Ако вземем като V0 Vb възел. можете да посетите на върха, за да

Забележка 1. След посещение на новия сайт, можете да посетите съседите на нов възел в случаен ред. Тук използваме споразумение, което, ако е необходимо, изберете възлите са посещавани по азбучен ред.

Забележка 2. Ако маркирате дъга, свързваща възел посетили преди това посети възел, всички тези отбелязани дъги образуват обхващаща дърво на графиката G; ако всяка дъга е с дължина 1, в която обхваща дървото е дърво от най-кратките пътища от V0 по време на всички други възли G.

DFS, DFS. Изборът произволен връх V0. и след това следва ръб Е01 към възела Vi. След това следват от реброто E12 V2 на възел в близост до V1. В общия случай, след посещение възел Vi следват заедно eij ръба в Vj възел. Ако Vj не беше посетили преди. След това рекурсивно прилага този процес да Vj и изберете ръб в EJK Vk възел. Ако връх Vj вече е имал, а след това обратно към Vi и изберете друг край. Ако всичко инцидента с ръбове, за да VI. които вече са избрани и не можете да намерите само един нов връх, а след това се връща от Vj към предишния връх, следвана от Vi. и проверка за инцидента на ребрата й.

Ако на фиг. 11 започне от върха на Vб. възможно е да посетите сайта в следния ред (за поръчки, се определя от повече от един начин):

Arc, следвайки в новите върхове, за да образуват обхващаща дърво. Тази дъга: EBC. ЗЕС. улавяне на електрони. Еде. ФЕЕ.

два начина за посещение на обектите могат да бъдат сравнявани. Когато BFS трябва да проверите всички краища инцидента на възел преди преминаването към новия възел. По този начин, операцията се извършва последователно от възли на вентилатора. Когато DFS преход към нова възлова точка се извършва само след нова възлова точка е намерена, и има дълбочина на проникване в графиката. Само когато всички ръбове са в горната част на старите, се връща към предишния възел и от DFS отново възобновено.

BFS и DFS алгоритми имат една и съща сложността на най-неблагоприятния случай. Сложността на алгоритъма за най-лошия случай - това е груба мярка за максимален брой операции, необходими за извършване на алгоритъма. Тази функция на размера на входните данни директно в този случай бяха представени графика (например, D (п)). Тъй като алгоритмите имат същата сложност, нито един от тях има предимства пред другия. Въпреки това, за някои специфични графики един алгоритъм може да се получи покритие дърво по-добре от друг. Например търсене за "дълбочина", в сила за граф "колела" и търсене на "ширина" за Графа "малтийски кръст".