Een diepte - eerst zoeken is een algoritme dat procedureel zoekt een grafiek of boomstructuur door het reizen zo ver beneden de boom als het kan voor een back-up . De tijd dat het algoritme te voltooien hangt af van het aantal knooppunten in de grafiek . In het ergste geval , dient het algoritme elk knooppunt in de grafiek bezoeken . Boom Grafieken
In het kader van grafieken , een boom is een grafiek waarin elke knoop , behalve de oorsprong "root " knooppunt heeft een enkele bovenliggende knooppunt wiens afstamming gaat terug naar de root node. De grafiek vormt een soortgelijke structuur als die van een kerstboom , geleidelijk uitbreiden en toevoegen van nieuwe knooppunten en kinderen op elk niveau . In een boom , het aantal kinderen dat ieder knooppunt is de boom " branching factor . " Het aantal generaties in de boom is de boom "diepte . "
Depth - First Search
een diepte - eerst zoeken is een methode voor het zoeken door middel van een boom , waarbij het algoritme loopt onderaan de boom tot hij het doelwit knooppunt . Vanaf de wortel knooppunt , het algoritme loopt door naar het volgende kind en vervolgens kleinkind van dat kind , het proces herhalen totdat er een kinderloos " blad " knooppunt . Na het vindt dat knooppunt , het loopt terug tot hij een niet onderzocht knooppunt . Als er geen meer onderzocht nodes , stopt het.
Algoritme Tijd Complexiteit
De tijd om een boom doorkruisen via diepte - eerst zoeken is afhankelijk van het aantal hoekpunten in de grafiek en randen daartussen . In het slechtste geval moet het algoritme reizen door elk hoekpunt en langs elke rand, zodat de tijd die nodig is het aantal hoekpunten en het aantal randen of " V + E" voor een boom , het aantal randen is gelijk aan de knooppunten min een , dus de totale tijd " 2V - . 1 " als elk knooppunt in de grafiek heeft hetzelfde aantal kinderen - een constante vertakkingsfactor - dan dit is gelijk aan dat factor . tot de macht van de diepte van de boom
Andere overwegingen
bij de uitvoering van een algoritme , de snelheid van het algoritme is afhankelijk van twee factoren : het aantal berekeningen het moet te maken en de tijd die nodig is om toegang te krijgen tot de middelen die het nodig heeft om te draaien - meestal geheugen . Hoe meer geheugen een programma vereist , hoe langer het duurt om te draaien . Een diepte - eerst zoeken moeten niet vergeten de vorige nodes het bezoek , zodat het ergste geval hoeveelheid geheugen die het nodig heeft , is gelijk aan het aantal knooppunten in de boom .
|
