Tole je rešitev tekoče domače naloge.
def stevilo_unikatov(s):
videno = []
for e in s:
if e not in videno:
videno.append(e)
return len(e)
Vendar to ne šteje, ker uporablja not in. Zakaj je prepovedan? To je ena od stvari, ki jih morate na tej točki predmeta vedeti.
Doslej smo uporabljali sezname in še te zgolj z indeksiranjem in dodajanjem (append) ter dolžino (len). Zakaj ta omejitev, upam, vemo: to so "osnovne operacije", ki jih ima računalnik. To je tisto, kar dobimo "zastonj" (če bi programirali v Cju, bi to bolj občutili, vendar --- nočete tega). To je tisto, kar vzame procesorju, ki v resnici dela vse, kar dela računalnik, "eno časovno enoto" (kar je sicer precej nejasen in raztegljiv pojem). To je tisto, česar ni bilo potrebno sprogramirati. (Spet, ni res, ker smo v Pythonu, ki je nekaj nivojev višje. Ampak to je operacija, ki jo v resnici podpira "gol" računalnik, brez kakršnegakoli programskega jezika, razen tistega, ki ga govori sam procesor.)
Imenitnejše stvari, kot so insert, in, count, index ... sem vam prepovedal. Od danes bodo praviloma dovoljene, vendar se bomo zavedali, koliko časa jemljejo: če uporabimo katero od njih, nismo naredili ene same operacije, temveč smo jih naredili toliko, kolikor je dolg seznam. V splošnem: n.
Prav tako so bili prepovedani slovarji in množice. Tudi ti bodo poslej dovoljeni, ker od predprejšnjič vemo, kako so narejeni: kot razpršene tabele. Vemo, da operacije na njih trajajo eno časovno enoto.
Vse operacije na seznamih, zraven pa še slovarji in množice, bodo dovoljene tudi zato, ker bi vse to znali samo sprogramirati - vsaj načelno - iz osnovnih operacij s seznami. Slovarje smo tako ali tako naredili, prav tako bi, če nam je dovoljen append, znali narediti svoj insert. In če bi znali narediti, nam bo to dovoljšen izgovor, da bomo uporabljali, kot da bi bili naredili - čeprav nismo.
Kje je Helga?¶
Tule smo se spet šli igro: študentke so dobile imena in (skrivni) seznam svojih "znank". Nekdo mora najti pot od Ane do Berte.
Je to podobno rodbini, drevesom? Ne: v drevesu se ne more zgoditi, da bi imela Ana hči Berto, Berta Cilko, Cilka pa Ano - namreč isto Ano, ki je Bertina mati in njena babica. Relacija "znanka" ustreza grafu.
Ko smo preiskovali drevo, smo lepo pregledovali naslednike in reč se je prej ko slej ustavila. Tu se lahko zaciklamo.
Kako bi se torej sprogramiralo to reč?
Programiranje 1¶
Najprej se moramo dogovoriti, kako bomo graf pravzaprav predstavili. Vsaj danes bomo uporabljali predstavitev, ki je zelo potratna: naredili bomo slovar, katerega ključi so vozlišča, vrednosti pa vozlišča, do katerih vodijo povezave iz pripadajočega ključa. Takole:
znanci = {
"Ana": {"Cilka", "Dani", "Micka"},
"Berta": {"Ema", "Nina", "Helga"},
"Cilka": {"Ana", "Micka", "Klara"},
"Dani": {"Ana", "Greta"},
"Ema": {"Nina", "Berta"},
"Fanči": {"Greta", "Liza"},
"Greta": {"Dani", "Fanči"},
"Helga": {"Berta", "Iva"},
"Iva": {"Nina", "Helga"},
"Jana": {"Klara", "Liza"},
"Klara": {"Cilka", "Liza", "Jana"},
"Liza": {"Micka", "Fanči", "Jana"},
"Micka": {"Ana", "Cilka", "Liza"},
"Nina": {"Ema", "Berta", "Iva"}
}
Zdaj sprogramirajmo funkcijo, ki pove, ali je določena pot dovoljena (natančno to smo pred dvema tednoma počeli pri Programiranju 1 :).
def preveri_pot(pot):
for i in range(1, len(pot)):
if oseba2 not in znanci[oseba1]:
return False
return True
Celo pri Programiranju 1 smo to sprogramirali učinkoviteje (z zip), vi bi morali znati uporabiti tudi generatorje in all, vendar bomo tule uporabili takšnole različico; malo zato, da boste razumeli tudi tisti, ki ste programiranje že malo pozabili, predvsem pa zato, da bomo kasneje lažje razmišljali, kaj se dogaja.
Zdaj bomo odkrili, ali obstaja pot, preprosto tako, da bomo sestavili vse poti. Pomagala nam bo funkcija permutations iz modula itertools, ki ji podamo kakšne reči in vrne vse permutacije teh reči. Če poleg tega podamo še kako številko k, bo vračala permutacije po k reči. Sestavili bomo množico vseh oseb razen oseba1 in oseba2 ter nato iz njih delali permutacije z 0, 1, 2, 3, ... osebami. S funkcijo preveri_pot bomo nato preskušali, ali takšno zaporedje oseb vodi od prve do druge. Če najdemo kakšno takšno permutacijo, vrnemo True, sicer False.
from itertools import permutations
def obstaja_pot(oseba1, oseba2):
vmesni = set(znanci) - {oseba1, oseba2}
for k in range(len(vmesni)):
for pot in permutations(vmesni, k):
if preveri_pot([oseba1] + list(pot) + [oseba2]):
return True
return False
Funkcijo bomo pognali ... vendar je ne bomo. Zakaj, bo jasno čez nekaj trenutkov.
Poskusili bomo nekaj drugega. Vemo, da poti med Ano in Berto ni, torej je vseeno, če poskušamo z malo manjšim grafom. Sestavljali bomo grafe, v katerih bosta samo Ana in Berta, osebe od Ane do Cilke, od Ane do Dani in tako naprej. Funkcijo bomo poganjali na vsakem od teh grafov in beležili, koliko časa potrebuje za izračun. Najprej pripravimo podgrafe.
graf = znanci
podgrafi = []
for do in "BCDEFGHIJKLMN":
podgrafi.append({oseba1: {oseba2 for oseba2 in graf[oseba1] if oseba2 <= do} for oseba1 in graf if oseba1 <= do})
print(podgrafi[4])
Štoparico ukrademo iz zapiskov prvih predavanj.
import time
class Stoparica:
def __init__(self):
self.zacetek = time.time()
def cas(self):
return time.time() - self.zacetek
Akcija!
casi = []
for i, znanci in enumerate(podgrafi[:-1]):
s = Stoparica()
for j in range(3):
obstaja_pot("Ana", "Helga")
cas = s.cas() / 3
casi.append(cas)
print(i + 1, cas)
Računali smo do predzadnjega podgrafa. Prvi časi so tako majhni, da jih nima smisla opazovati. Če pogledamo ostale, pa opazimo, da kar hitro naraščajo. Delimo vsak čas s predhodnim časom.
for i in range(1, len(casi)):
print(casi[i] / casi[i - 1])
Grdo, a? Enajsti čas je desetkrat večji od desetega. Deseti devetkrat od devetega. Ta osemkrat od osmega...
%matplotlib inline
from pylab import plot
plot(range(len(casi)), casi, "b*-")
Kakšno časovno zahtevnost ima ta reč?
Za začetek: koliko časa potrebuje funkcija preveri_pot, če ji podamo pot dolžine k? Spomnimo se:
def preveri_pot(pot):
for i in range(1, len(pot)):
if oseba2 not in znanci[oseba1]:
return False
return True
Vprašajmo se takole: kolikokrat se zgodi if? Največ tolikokrat, kolikorkrat se obrne zanka, to je len(pot) - 1-krat. Če je pot dolga k, je to k - 1. Koliko časa porabi if? Ker je znanci slovar, bo znanci[oseba] zahteval le eno časovno enoto (zdaj namreč že vemo, kako delujejo slovarji -- razpršene tabele!). Ker je znanci[oseba] množica, bo tudi operator not in zahteval le eno časovno enoto (zdaj namreč že vemo, kako delujejo množice -- razpršene tabele, slovarji brez vrednosti).
Funkcija preveri_pot ima torej linearno časovno zahtevnost: dvakrat daljša pot, dvakrat večje število korakov. Če pozabimo tisto nepomembno enico, lahko rečemo, da za pot dolžine k potrebuje k korakov.
Zdaj, ko to vemo, lahko razmišljamo o obstaja_pot. Recimo, da imamo graf z n točkami.
from itertools import permutations
def obstaja_pot(oseba1, oseba2):
vmesni = set(znanci) - {oseba1, oseba2}
for k in range(len(vmesni)):
for pot in permutations(vmesni, k):
if preveri_pot([oseba1] + list(pot) + [oseba2]):
return True
return False
Analizirajmo jo od znotraj navzven. Sestavljanje argumentov za preveri_pot ... si lahko predstavljamo, kot da k seznamu [oseba1] enega in po enega "appendamo" vse elemente pot in nato še [oseba2]. To zahteva toliko korakov, kolikor je dolga pot in še enega zraven. Torej k (tistega enega zraven pa damo za šenk). To seštevanje se nam sicer skrije v Pythonu ... in niti ni tako zelo pomembno, lahko bi ga celo pozabili).
S tem seznamom, ki je dolg k + 2 pokličemo funkcijo preveri_pot. Ta bo, vemo, potrebovala k korakov (zanemarili smo dvojko, tako kot smo pravzaprav tudi v funkciji enico in tako naprej).
Torej: tisto, kar je znotraj zanke for pot in zahteva \(2\times k\) korakov. Ker nas zanimajo le "relativne" časovne zahtevnosti, bomo rekli, da je to pravzaprav k korakov.
Kolikokrat pa izvedemo to, kar je znotraj te zanke? I, no, tolikokrat, kolikorkrat se obrne ta zanka. Zanka poišče vse permutacije dolžine k znotraj n-2 točk grafa (vse točke razen, recimo, Ane in Berte). To so variacije brez ponavljanja. Če imamo za seboj dovolj kombinatorike, vemo, da je odgovoror \((n - 2)! / (n - 2 - k)!\). Odlično. Če \((n - 2)! / (n - 2 - k)!\)-krat ponovimo nekaj, kar traja \(k\) časa, bomo za vse ponovitve skupaj potrebovali \((n - 2)! / (n - 2 - k)! \times k\) časa.
Vendar še nismo končali. Vse to je še znotraj ene zanke, ki spreminja k: k gre od 0 do n - 2. Torej celotna funkcija obstaja_pot vzame \(\sum_{k=0}^{n - 2} \frac{(n - 2)!}{(n - 2 - k)!}k!k\) časa.
Slaba in dobra novica.
Slaba: tega niti slučajno ne znam sešteti. Mogoče se, da, vendar povejmo še dobro novico.
Dobra: tega niti ni potrebno sešteti. Delajmo se, da je n zelo velik. (To smo počeli že večkrat in zdaj zdaj bo prišlo še matematično opravičilo za to. Za zdaj: pač, zanima nas, kaj se dogaja, ko je n dovolj velik.) Poglejmo zadnja dva člena te vsote, torej tista dva, ko je k enak n - 2 in ko je enak n - 2. Pri \(k=n-2\) imamo \(\frac{(n - 2)!}{(n - 2 - k)!}k = \frac{(n - 2)!}{(n - 2 - (n - 2))!}(n - 2)!(n - 2) = (n - 2)! (n - 2)!(n - 2)\). Pri \(k = n - 3\) pa imamo \(\frac{(n - 2)!}{(n - 2 - k)!}k = \frac{(n - 2)!}{(n - 2 - (n - 3))!}(n - 3) = \frac{(n - 2)!}{1!} (n - 3)!(n - 3) = \frac{(n - 2)!} (n - 3)!(n - 3)\). Delimo zadnji člen s predzadnjim, da bomo izvedeli, kolikokrat večji je. Dobimo, očitno: \(\frac{(n - 2)! (n - 2)}{(n - 3)!(n - 3)} = (n - 2) \frac{n-2}{n-3}\). Če je \(n\) res velik, je \(\frac{n-2}{n-3}\) približno 1, torej je zadnji člen \(n-2\)-krat večji od predzadnjega. Če je, kot že večkrat rečeno, \(n\) res velik, je zadnji člen toliko večji od predzadnjega, da vsote pravzaprav sploh ne potrebujemo: mirno se lahko delamo, da funkcija porabi toliko časa, koliko ga porabi zadnji člen, saj so vsi ostali (začenši s predzadnjim) v primerjavi z njim zanemarljivi.
Kakšen je bil zadnji člen? \((n-2)!(n-2)\). Brez pretiravanja se lahko delamo, da je to \((n-1)!\). Če rečemo, da ima naš graf n+1 vozlišč, bomo zapisali, da ima naša funkcija časovno zahtevnost \(n!\).
Zdaj se spomnimo še Stirlingove aproksimacije, \(n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\). Ker nas drobnarije ne zanimajo, bomo rekli kar \(n! = n^n\). Kot bomo izvedeli, je to najhujše, kar je možno.
Pametnejši način in zahtevnejša analiza (ali pa tudi ne)¶
Več kot očitno se da ta problem rešiti tudi boljše. Vsaj prejle, ko smo se to igrali v živo, nam je uspelo.
Kakšen algoritem smo uporabili? Preprosto: začeli smo pri prvi osebi. Vprašali smo jo, koga pozna. Potem smo vprašali - po eno in eno - njene znanke, koga poznajo. Dodali smo jih na spisek teh, ki jih moramo vprašati koga poznajo... In tako naprej, dokler se spisek ljudi, ki jih moramo še vprašati, ni spraznil. Obenem smo pazili, da nikogar nismo vprašali večkrat. Če bi namreč dodajali na spisek tudi ljudi, ki smo jih že vprašali, se stvar ne bi nikoli iztekla. Torej tako.
def obstaja_pot(oseba1, oseba2):
pregledati = [oseba1]
pregledano = set()
while pregledati:
pregledovana = pregledati.pop()
if pregledovana in pregledano:
continue
if pregledovana == oseba2:
return True
pregledati += znanci[pregledovana]
pregledano.add(pregledovana)
return False
pregledati je spisek (seznam) teh, ki jih nameravamo še pregledati, pregledano pa množica teh, ki smo jih že. Dokler se seznam ne sprazni, z njega jemljemo osebe, ki jih bomo pregledali (trenutno pregledovana oseba je pregledovana).
Če smo pregledovano osebo pravzaprav že pregledali, s continue skočimo nazaj na while in vzamemo naslednjo osebo. Če je to prav oseba, ki jo iščemo (oseba2), vrnemo True. Sicer pa v seznam teh, ki jih je potrebno še pregledati, dodamo vse znance te osebe, to osebo pa označimo kot pregledano.
Stvar ima nekaj variacij in tale ni nujno najboljša, izbrali pa smo jo, ker jo je najlažje razumeti in analizirati.
Funkcija, jasno, dela bliskovito. Vprašanje je le, kako bliskovito.
pregledati.pop() in pregledano.add zahtevata en sam korak. Prav tako in, saj gre za množice. Tudi enačaj je hiter, saj gre za nize (če bi primerjali, recimo, dva seznama, to lahko traja toliko časa, kolikor je dolg krajši od seznamov!)
Ostane še pregledati += znanci[pregledovana], torej seštevanje množic. To traja toliko časa, kolikor bi ga potrebovali, da dodamo vsak element posebej. Vsakega dodamo v konstantnem času (torej, času neodvisnem od velikosti množice; se pravi, da se lahko obnašamo, kot da gre za eno operacijo). Če ima oseba k znancev, bo vrstica pregledati += znanci[pregledovana] trajala k korakov.
Kolikokrat se bo zavrtela zanka? Tolikokrat, kolikor oseb bomo dodali v pregledati. Za lažje razmišljanje (in zaokrožanje v lastno škodo) si predstavljajmo, da bo vsaka oseba dodana tolikokrat, kolikorkrat jo bodo dodali njeni znanci. Torej je vsaka oseba dodana tolikokrat, kolikor znancev ima. Vseh dodanih oseb je, ha, toliko, kolikor je povezav v grafu!
Recimo, da ima najbolj "znana" točka d znancev. V lastno škodo predpostavimo, da imajo vse točke toliko, namreč največ, d znancev. Če ima graf e povezav, se zanka while zavrti e-krat in znotraj zanke imamo seštevanje množic, ki traja d korakov. Skupno trajanje algoritma je torej sorazmerno \(d\times e\) - številu povezav v grafu, pomnoženemu z najvišjo stopnjo točke.
Pravzaprav lahko naredimo še nekoliko boljšo oceno. Takole lahko razmišljamo: pozabimo na zanko while. Če bomo pregledali vse točke, v pregledati pri vsaki dodali toliko znancev, kolikor ima pač povezav. Pri Ani tri, pri Dani 2, pri Lizi 4. Skupno število vseh operacij v onem prištevanju je torej enako dvakratniku števila povezav. Ker konstante pri tem predmetu zanemarjamo, lahko rečemo, da bo ona vrstica pregledati += ... potrebovala čas, sorazmeren številu povezav. Za ostale vrstice pa vemo, da se izvršijo tolikokrat, kolikorkrat se zavrti zanka while - kar pa je ravno tako e-krat. Čas izvajanja našega algoritma je torej sorazmeren številu povezav.
Iskanje poti¶
Opogumljeni s tem uspehom si zastavimo težjo nalogo. Zdaj nas ne zanima le, ali pot obstaja, temveč bi, kadar obstaja, radi vedeli tudi, kakšna je: prek koga gremo od Ane do Klare?
[[Spet poskusimo v živo. Brez goljufanja: ne smemo risati grafov ali česa drugega, kar ljudje vidimo takoj, računalnik pa ne.]]
Rešitev je pravzaprav enaka kot prej, le da si moramo pri vsaki osebi, do katere pridemo, zapomniti tudi, kako smo prišli do nje. To bo zahtevalo le malenkostno spremembo programa. Recimo takole.
def poisci_pot(oseba1, oseba2):
pregledati = {oseba1: None}
pregledano = {}
while pregledati:
pregledovana, od_kod = pregledati.popitem()
if pregledovana in pregledano:
continue
pregledano[pregledovana] = od_kod
if pregledovana == oseba2:
break
for znanec in znanci[pregledovana]:
pregledati[znanec] = pregledovana
nazaj = []
while oseba2:
nazaj.append(oseba2)
oseba2 = pregledano[oseba2]
return list(reversed(nazaj))
Namesto množice teh, ki jih je potrebno pregledati, imamo zdaj slovar; ključ je ime osebe, ki jo moramo pregledati, pripadajoča vrednost pa ime osebe, prek katere smo do te osebe prišli. Enako bo s pregledanimi: za vsako osebo bomo vedeli, kako smo prišli do nje.
Zaradi tega se spremenijo tri stvari. Namesto pregledati.pop() imamo pregledati.popitem(), ki vrne nek naključen element slovarja - kot par (ključ, vrednost). Da je naključen, je nepomembno in očitno hkrati, saj slovarji nimajo določenega vrstnega reda. Ključ je, kot smo pravkar povedali, pregledovana, vrednost pa, od_kod smo do te osebe prišli.
Namesto pregledano.add(pregledovana) imamo pregledano[pregledovana] = od_kod.
Končno, namesto preprostega seštevanja množic dodajamo v slovar - da je potrebno pregledati nekega znanca trenutno pregledovane osebe, zabeležimo tako, da v pregledati ustvarimo element s ključem znanec, kot vrednost pa zapišemo, da smo do njega prišli od osebe pregledovana.
Za začetek bomo, tako kot prej, zapisali, da je potrebno pregledati oseba1, do nje pa smo prišli iz None.
Vse se odvrti tako kot prej, le da namesto množic uporabljamo slovarje. Ko naletimo na iskano oseba2 pa ne vrnemo True, temveč le prekinemo zanko. Zdaj sestavimo seznam, ki bo predstavljal pot. Začnemo pri oseba2, vprašamo se, kako smo prišli do nje - oseba2 = pregledano[oseba2] - kar ponavljamo, dokler ne pridemo do None. To pa se zgodi natančno takrat, ko smo v seznam dodali še oseba1.
Seznam je po tem obrnjen narobe (od oseba2 do oseba1), zato ga z reversed obrnemo. Ker reversed vrača nekaj čudnega, to spremenimo nazaj v seznam.
Obračanju bi se lahko izognili, če bi v gornji zanki iskali pot od oseba2 do oseba1. To deluje, dokler je graf neusmerjen; lahko pa bi imeli usmerjen graf in povezave zapisane v obratni smeri ... a pustimo, tu to, kot se bo izkazalo, ni tako pomembno.
Koliko časa se izvaja ta funkcija?
Zgornji del je enak kot prej: čas izvajanja je sorazmeren številu povezav. Množice in slovarji se vedejo enako.
Pa spodnji del? append in indeksiranje imata konstantno zahtevnost ("en korak"). Zanka se odvrti tolikokrat, kolikor je dolga pot od oseba1 do oseba2.
Kaj pa list in reversed. Tole lahko razrešimo na dva načina. Lahko mi verjamete na besedo. Funkcija reversed v resnici ne naredi ničesar, kar bi jemalo čas (samo nekaj "napne" čez seznam ... ni pomembno). Funkcija list v resnici zloži elemente v nov seznam - čisto, kot da bi to počela z append, kar očitno spet vzame toliko časa, kolikor je dolga pot.
Spodnji del torej vzame dvakrat toliko časa, kolikor je dolga pot. Ker nas konstante ne zanimajo, je to toliko časa, kolikor je dolga pot in konec.
Zgornji del vzame toliko časa, kolikor je povezav, spodnji toliko, kolikor je dolga pot. Ker pot ne more biti daljša, kolikor je povezav (saj po nobeni ne gremo več kot enkrat), bomo v lastno škodo rekli, da spodnji del traja toliko časa, kolikor je povezav.
Če gornji in spodnji del trajata toliko časa, kolikor je povezav, vse skupaj traja dvakrat toliko časa, kolikor je povezav. Torej toliko časa, kolikor je povezav.
Joj, saj res: našega programa sploh še nismo preskusili! Poiščimo pot od Ane do Cilke.
znanci = {
"Ana": {"Cilka", "Dani", "Micka"},
"Berta": {"Ema", "Nina", "Helga"},
"Cilka": {"Ana", "Micka", "Klara"},
"Dani": {"Ana", "Greta"},
"Ema": {"Nina", "Berta"},
"Fanči": {"Greta", "Liza"},
"Greta": {"Dani", "Fanči"},
"Helga": {"Berta", "Iva"},
"Iva": {"Nina", "Helga"},
"Jana": {"Klara", "Liza"},
"Klara": {"Cilka", "Liza", "Jana"},
"Liza": {"Micka", "Fanči", "Jana"},
"Micka": {"Ana", "Cilka", "Liza"},
"Nina": {"Ema", "Berta", "Iva"}
}
poisci_pot("Ana", "Cilka")
Ups. Nastavili smo si past in se ujeli vanjo. Na nek način. Ana pozna Cilko. Pot od Ane do Cilke pa je, po mnenju našega programa ['Ana', 'Micka', 'Cilka']. To ni narobe. Najbolj prav pa tudi ne.
Najkrajša pot¶
Tu se naše življenje zaplete. Zdaj bi radi poiskali najkrajšo pot med dvema osebama.
Na prvi pogled je rešitev preprosta: če bi Ana takoj preverila, ali pozna Cilko (oziroma oseba1 ali pozna oseba2), do tega ne bi prišlo. A ni tako preprosto.
poisci_pot("Ana", "Liza")
Od Ane do Lize se da priti po poti ['Ana', 'Micka', 'Liza']. Prav, bi bilo to mogoče rešiti tako, da pri vsaki osebi (ne le pri oseba1 preverimo, ali pozna oseba2.
poisci_pot("Ana", "Greta")
Grozno. Obstaja pot ['Ana', 'Dani', Greta']. Funkcija pa zabluzi okrog Micke in poišče najdaljšo možno pot do Grete!
Kako rešiti tole? Spet se zatecimo k zdravi pameti. Poskusimo v živo.
def poisci_pot(oseba1, oseba2):
pregledati = [(oseba1, None)]
pregledano = {}
while pregledati:
print(pregledati)
pregledovana, od_kod = pregledati.pop(0)
if pregledovana in pregledano:
continue
pregledano[pregledovana] = od_kod
if pregledovana == oseba2:
break
pregledati += [(znanec, pregledovana) for znanec in znanci[pregledovana]]
nazaj = []
while oseba2:
nazaj.append(oseba2)
oseba2 = pregledano[oseba2]
return list(reversed(nazaj))
Sprememba niti ni velika.
Doslej nam je bilo vseeno, v kakšnem vrstnem redu pregledujemo osebe (ne čisto, ne čisto - kot se bo vsak čas izkazalo!). V začetku smo uporabljali seznam, nato slovar.
S slovarjem je bil vrstni red pregledovanja naključen.
Kaj pa s seznamom? Uporabljali smo append (oziroma +=, kar je le kup appendov) in pop. Koga smo pregledali prej? Tistega, ki smo ga dodali prvega ali zadnjega? Prvi pride prvi melje ali zadnji pride prvi melje?
pop je s seznama pobral tistega, ki smo ga dodali nazadnje. Pri drevesih je to pomenilo preiskovanje v globino - najprej smo iskali pot od najnazadnejše dodanega potomca. Pri grafih je podobno - saj preiskovanje grafov pravzaprav ni tako zelo različno od preiskovanja dreves, le da moramo popaziti še na to, kje smo že bili. Rinemo torej dalj in dalj in dalj. Kot od Ane zarinemo proti Micki, nimamo nobenih možnosti, da odkrijemo, da se do Grete hitreje pride prek Dani. Če bi imeli slučajno srečo, da bi šli od Ane najprej proti Dani, pa bomo tudi od Ane do Micke hodili prek Dani.
Tule smo to napako popravili s tem, da smo ponovno uporabili seznam (vrstni red je pomemben), vendar pop() zamenjali s pop(0). Tako pridejo prej na vrsto tisti, ki smo jih dodali prej - torej tisti, do katerih je pot najkrajša. Tako najprej obdelamo Anine znance, nato znance Aninih znancev, potem znance znancev Aninih znancev. Vsaka "generacija" se mora lepo postaviti na konec vrste in počakati.
O čem se danes sprašujemo še bolj pridno kot sicer sprašujemo? O časovnih zahtevnostih.
Tozadevno smo zdaj precej na slabšem kot prej. pop(0) zahteva čas sorazmeren dolžini seznama točk, ki jih je potrebno še pregledati. Ta je, vemo, lahko dolg toliko, kolikor je povezav. Če se zanka while odvrti tolikokrat, kolikor je povezav, znotraj nje pa je pop, ki traja toliko časa, kolikor je povezav, bo trajanje cele funkcije sorazmerno kvadratu števila povezav.
Naš algoritem je preskočil iz linearnega h kvadratnim. Tega ne maramo.