b"\n_START_ARTICLE_\nS\xc3\xbcgavuti otsing\n_START_SECTION_\nOmadused\n_START_PARAGRAPH_\nS\xc3\xbcgavuti otsingu ajaline ja ruumi keerukus oleneb selle kasutuse alast. Teoreetilises arvutiteaduses kasutatakse s\xc3\xbcgavuti otsingut tavaliselt terve graafi l\xc3\xa4bimiseks ning selle keerukus on O(|V|+|E|). Sellistes tingimustes on algoritmi ruumi keerukus halvemal juhul O(|V|), sest tuleb meeles pidada tippude magasini ja l\xc3\xa4bitud tippude hulka. Sellisel juhul on ajaline ja ruumi keerukus laiuti ja s\xc3\xbcgavuti otsingutel sama ning valik kahe algoritmi vahel p\xc3\xb5hineb tippude j\xc3\xa4rjestusest graafis ja mitte algoritmide keerukusest._NEWLINE_Teistes valdkondades nagu tehisintellekt, graaf v\xc3\xb5ib olla liiga mahukas selleks, et seda t\xc3\xa4ielikult l\xc3\xa4bida v\xc3\xb5i isegi l\xc3\xb5pmatu. Sellistes juhtudes otsingu teostatakse ainult piiratud s\xc3\xbcgavusel, mis on lineaarse ajalise keerukusega ning ruumi keerukus on proportsionaalne s\xc3\xbcgavusele. Sellisel l\xc3\xa4henemisel on ruumi keerukus v\xc3\xa4iksem kui laiuti otsingu ruumi keerukus sarnasel graafil. Suurte andmestruktuuride puhul kasutab s\xc3\xbcgavuti otsing heuristilist l\xc3\xa4henemist suurima t\xc3\xb5en\xc3\xa4osusega haru valimiseks. Juhul, kui vajalik s\xc3\xbcgavus on teadmata, kasutatakse iteratiivse s\xc3\xbcvenemisega s\xc3\xbcgavuti otsingu (ingl iterative deepening depth-first search), mille p\xc3\xb5him\xc3\xb5te on iga iteratsiooniga s\xc3\xbcgavuse suurenemine kuni tulemuseni j\xc3\xb5udmiseni. Tehisintellekti anal\xc3\xbc\xc3\xbcsimise puhul ja haru faktoriga suurem kui 1, iteratiivne s\xc3\xbcvenemine suurendab t\xc3\xb6\xc3\xb6aega ainult p\xc3\xbcsiva faktori v\xc3\xb5rra. Aga seda ainult juhul, kui \xc3\xb5ige s\xc3\xbcgavuspiir on tippude arv tasemete kaupa geomeetrilise kasvu t\xc3\xb5ttu teada._NEWLINE_S\xc3\xbcgavuti otsingu v\xc3\xb5ib kasutada ka tippu j\xc3\xa4rjendi korjamise jaoks.\n_START_SECTION_\nN\xc3\xa4idis\n_START_PARAGRAPH_\nTeostame s\xc3\xbcgavuti otsingu j\xc3\xa4rgmise graafi peal:_NEWLINE_Leppime kokku, et vasak alampuu l\xc3\xa4bitakse enne kui parem alampuu ja peame meeles juba l\xc3\xa4bitud tippude j\xc3\xa4rjendi. Alustame otsingu tipust A ja l\xc3\xa4bime graafi j\xc3\xa4rgmisel j\xc3\xa4rjestusel: A, B, D, F, E, C, G. Kui me ei j\xc3\xa4ta meelde juba l\xc3\xa4bitud tippude hulka, siis otsing j\xc3\xa4\xc3\xa4b ts\xc3\xbckli sisse A, B, D, F, E, A, B, D, F, E\xe2\x80\xa6 ja ei l\xc3\xa4bi kunagi tippe C ja G. Iteratiivne s\xc3\xbcvenemine lubab v\xc3\xa4ltida sellist olukorda.\n_START_SECTION_\nS\xc3\xbcgavuti otsing Pythonis\n_START_PARAGRAPH_\nJ\xc3\xa4rgnevas Pythoni koodis l\xc3\xa4bib meetod dfs graafi G alustades tipust s mitte rekursiivse s\xc3\xbcgavuti otsinguga:_NEWLINE_def dfs(graaf, juur_tipp):_NEWLINE_    magasin = [juur_tipp]_NEWLINE_    kylastatud = set(juur_tipp)_NEWLINE_    while magasin:_NEWLINE_        v = magasin.pop(len(magasin)-1)_NEWLINE_        yield v_NEWLINE_        [(magasin.append(u), kylastatud.add(u)) for u in graaf.get(v, []) if u not in kylastatud]graaf = {'A': ['B', 'C'],_NEWLINE_    'B': ['D', 'E'],_NEWLINE_    'C': ['F', 'G', 'H'],_NEWLINE_    'D': ['I', 'J'],_NEWLINE_    'E': ['K','L', 'M'],_NEWLINE_    'F': ['N'],_NEWLINE_    'H': ['O', 'P']}>>> print(list(dfs(graaf, 'A')))['A', 'C', 'H', 'P', 'O', 'G', 'F', 'N', 'B', 'E', 'M', 'L', 'K', 'D', 'J', 'I']_NEWLINE_Antud algoritmi implementatsioon saab sisendiks graafi graaf ja alguspunkti juur_tipp, mis peab sisalduma graafis. Paneme algus punkti magasini sisse ning \xe2\x80\x9cl\xc3\xa4bitud\xe2\x80\x9d hulka sisse. T\xc3\xa4idame algoritmi nii kaua, kui magasin ei ole t\xc3\xbchi. Ts\xc3\xbckli sees v\xc3\xb5tame magasinist viimasena lisatud tipu, v\xc3\xa4ljastame selle ja otsime sellest tipu k\xc3\xb5ik alamtipud."