Cycle detection
Në shqip: Gjetja e cikleve
ShpjegimiSQ
A ka një cikël? Në një listë të lidhur e gjen me dy tregues (njëri ecën 1 hap, tjetri 2 — „breshka dhe lepuri“). Në graf përdor DFS dhe ngjyra (e pavizituar, në proces, e mbaruar).
EnglishEN
Is there a cycle? In a linked list you find it with two pointers (one moves 1 step, the other 2 — “tortoise and hare”). In a graph you use DFS with colours (unvisited, in progress, done).
Si ta mendosh
Si të kuptosh që po ecën në rreth në pyll sepse po sheh të njëjtën pemë.
Lexoje në anglisht
Like realising you're walking in circles in a forest because you keep seeing the same tree.
Shembull kodipython
def ka_cikel(koka):
ngadale = shpejt = koka
while shpejt and shpejt.tjetri:
ngadale, shpejt = ngadale.tjetri, shpejt.tjetri.tjetri
if ngadale is shpejt: return True