Depth-first search (DFS)
Në shqip: Kërkimi në thellësi
ShpjegimiSQ
DFS ecën sa më thellë në një degë të grafit para se të kthehet prapa dhe të provojë degën tjetër — me rekursion ose me një stack. Përdoret për labirinte, për të gjetur cikle dhe për renditje topologjike.
EnglishEN
DFS goes as deep as possible down one branch of the graph before backing up and trying the next — using recursion or a stack. It's used for mazes, finding cycles and topological sorting.
Si ta mendosh
Si të eksplorosh një shpellë: shkon deri në fund të një tuneli, pastaj kthehesh dhe provon tjetrin.
Lexoje në anglisht
Like exploring a cave: go to the end of one tunnel, then come back and try the next.
Shembull kodipython
def dfs(graf, nyje, pare=None):
pare = pare or set(); pare.add(nyje)
for f in graf[nyje]:
if f not in pare: dfs(graf, f, pare)
return pare