Begreper

01 Grunnlag

Problem og instans #: Et problem er relasjonen mellom input og output. En instans er én bestemt input. Problemstørrelsen $n$ er plassen en instans trenger, som regel antall elementer.
RAM-modellen #: Random-access machine: en idealisert maskin der aritmetikk, sammenligning, hopp og oppslag i én celle koster én tidsenhet hver, og instruksjonene utføres etter hverandre. Heltallene er om lag $c \lg n$ bits brede.
Asymptotisk notasjon #: Et språk for vekst som ser bort fra konstantfaktorer og lavere ordens ledd. Oppfører seg som sammenligning av tall: $O$ er $\le$ , $\Omega$ er $\ge$ , $\Theta$ er $=$ , $o$ er $<$ og $\omega$ er $>$ . De to siste krever ulikheten for enhver konstant $c > 0$ , ikke bare for én.
Beste, verste og gjennomsnittlige tilfelle #: Tre funksjoner av $n$ : kjøretiden for den billigste instansen av størrelse $n$ , for den dyreste, og den forventede kostnaden når instansen trekkes tilfeldig. Hvilket tilfelle det gjelder er uavhengig av hvilken asymptotisk operator som brukes på det.
Løkkeinvariant #: En påstand om tilstanden som holder ved starten av hver iterasjon. Vises med initialisering, vedlikehold og terminering, og er induksjonsbeviset for at løkka er korrekt.
Insertion-Sort #: Sorterer ved å holde $A[0 .. i - 1]$ sortert og sette $A[i]$ inn på rett plass i det utsnittet. Bruker $\Theta(n)$ i beste tilfelle og $\Theta(n^2)$ i verste, og sorterer på plass.

02 Datastrukturer

Stakk #: Sist inn, først ut (LIFO). Alt skjer på toppen: Push legger på og Pop tar av, begge i konstant tid. Implementeres med en tabell og en toppindeks.
Kø #: Først inn, først ut (FIFO). Enqueue legger til bakerst og Dequeue tar ut forrest, begge i konstant tid. Implementeres gjerne som ringbuffer: en tabell der indeksene head og tail rykker fremover og går rundt til starten når de passerer enden.
Lenket liste #: Noder som peker på neste node, og i en dobbeltlenket liste også på forrige. Innsetting og sletting koster konstant tid når du står ved noden; søk følger pekerne og koster lineær tid.
Dynamisk mengde #: Funksjonalitet, ikke en bestemt struktur: hold en mengde elementer med nøkler, og støtt Search, Insert og Delete, for ordnede nøkler også Minimum, Maximum, Successor og Predecessor. Finnes ikke svaret, returneres NIL.
Hashtabell #: Oppslagstabell der en hashfunksjon regner indeksen ut fra nøkkelen, for eksempel $h(k) = k \bmod m$ . To nøkler kan få samme indeks, en kollisjon; med kjeding får hver plass en lenket liste som tar imot alle sine nøkler.
Belastningsfaktor #: $\alpha = n/m$ : antall elementer delt på antall plasser i hashtabellen. Med kjeding og jevn fordeling er forventet søketid $\Theta(1 + \alpha)$ , så tabellen bør vokse i takt med datamengden.
Perfekt hashing #: For en statisk nøkkelmengde: nøklene hashes først inn i $m = n$ plasser, og plass $j$ med $n_j$ nøkler får en sekundærtabell med $n_j^2$ plasser og en hashfunksjon uten kollisjoner der. Søk tar konstant tid selv i verste fall, og plassen er $O(n)$ .
Amortisert analyse #: Snitt per operasjon over en hel operasjonsfølge, i verste fall. Aggregert analyse: regn ut totalt arbeid og del på antall operasjoner. Ingen sannsynlighet er involvert, i motsetning til gjennomsnittstilfellet, som er et snitt over instanser.
Tabelldobling #: Når tabellen er full, eller for en hashtabell når $\alpha$ har nådd en fast grense: alloker en dobbelt så stor, kopier (eller hash på nytt) alt over og fortsett. Én innsetting kan koste lineær tid, men $n$ innsettinger koster totalt under $3n$ operasjoner, og nøyaktig $2n - 1$ når $n$ er en toerpotens. Det er amortisert konstant per innsetting.

03 Problemer og reduksjoner

Søkeproblem #: Gitt en instans $x$ : finn en løsning $y$ slik at $(x, y) \in R$ . Finnes ingen, feiler søket.
Beslutningsproblem #: Gitt en instans $x$ : avgjør om det finnes en løsning $y$ med $(x, y) \in R$ . Svaret er ja eller nei, og problemet kan ses som mengden av ja-instanser.
Optimeringsproblem #: Blant de akseptable løsningene til en instans: finn en som er best mulig etter et gitt mål, for eksempel størst, kortest eller billigst.
Sertifikat #: En påstått løsning som verifiseres: gitt $x$ og sertifikatet $y$ , sjekk om $(x, y) \in R$ . Å verifisere er ofte langt billigere enn å finne løsningen selv.
Orakel #: En hypotetisk subrutine som antas å løse et gitt problem. Reduksjoner beskrives med orakler: det som gjenstår etter omformingen av instansen, overlates til oraklet.
Reduksjon #: Å løse problem $X$ ved å omforme instansen og bruke et orakel for problem $Y$ . Cook-reduksjoner tillater mange orakelkall, Levin-reduksjoner ett kall med oversettelse av løsningen tilbake, og Karp-reduksjoner ett kall der ja/nei-svaret går uendret gjennom. En billig reduksjon fra $X$ til $Y$ viser at $Y$ er minst like vanskelig som $X$ .

04 Splitt og hersk

Splitt og hersk #: Designmetode: løs grunntilfellet direkte, ellers del instansen i uavhengige delinstanser, løs dem rekursivt og kombiner delsvarene. Arbeidet ligger som regel i enten delingen eller kombinasjonen. Korrektheten vises ved sterk induksjon over problemstørrelsen.
Rekurrens #: En ligning som definerer en funksjon ved hjelp av seg selv på mindre argumenter, for eksempel $T(n) = 2T(n/2) + n$ . Kjøretiden til en rekursiv algoritme har denne formen. En algoritmisk rekurrens har konstant grunntilfelle for små $n$ og terminerer, og det antas når ikke annet er sagt.
Iterasjonsmetoden #: Løser en rekurrens ved å ekspandere den rekursive forekomsten gjentatte ganger til et mønster viser seg, velge antall ekspansjoner slik at argumentet treffer grunntilfellet, og summere.
Rekursjonstre #: Iterasjonsmetoden tegnet som et tre: rota er $f(n)$ , nivå $i$ har $a^i$ noder av størrelse $n/b^i$ , og kjøretiden er summen av nivåkostnadene. Antall løvnoder er $a^{\log_b n} = n^{\log_b a}$ .
Substitusjonsmetoden #: Verifiserer en gjettet eller funnet løsning med induksjon: anta at løsningen holder for mindre argumenter, sett inn i rekurrensen og vis at den holder for $n$ . Sjekk grunntilfellet. Påstanden må være nøyaktig den samme før og etter, konstanten inkludert; $O(1)$ i hypotesen og $O(1)$ i konklusjonen kan skjule to ulike konstanter.
Masterteoremet #: Løser $T(n) = aT(n/b) + f(n)$ ved å sammenligne den drivende funksjonen $f(n)$ med vannskillefunksjonen $n^{\log_b a}$ . Er $f$ polynomisk mindre, dominerer løvnodene: $\Theta(n^{\log_b a})$ . Er $f = \Theta(n^{\log_b a} \lg^k n)$ for en konstant $k \ge 0$ , er løsningen $\Theta(n^{\log_b a} \lg^{k+1} n)$ . En logaritmisk faktor under vannskillefunksjonen, som $n/\lg n$ , dekkes ikke. Er $f$ polynomisk større og regulær, dominerer rota: $\Theta(f(n))$ .
Binærsøk #: Søk i en sortert tabell ved å sammenligne med midtelementet og søke rekursivt i den halvdelen verdien må ligge i. $T(n) = T(n/2) + 1$ , altså $\Theta(\lg n)$ . Det rekursive kallet er det siste i prosedyren, så algoritmen skrives like gjerne som en løkke.
Merge-Sort #: Del på midten, sorter halvdelene rekursivt og flett dem. Flettingen kopierer halvdelene til $L$ og $R$ med en vaktpost $\infty$ bakerst og flytter det minste forreste elementet til neste ledige plass, i $\Theta(n)$ tid. $T(n) = 2T(n/2) + n = \Theta(n \lg n)$ i alle tilfeller.
Quicksort #: Partition velger siste element som pivot og ordner resten med små elementer til venstre og store til høyre, i $\Theta(n)$ tid; pivoten havner på sin endelige plass. Delene sorteres rekursivt. $\Theta(n \lg n)$ ved jevn deling og i snitt over alle rekkefølger, $\Theta(n^2)$ når pivoten står alene, som på sortert input. Randomized-Quicksort bytter et tilfeldig element inn som pivot. Da er hvert element med i $O(\lg n)$ delinger i forventning, så forventet kjøretid er $\Theta(n \lg n)$ for enhver input.
Forventet kjøretid #: Snitt over algoritmens egne tilfeldige valg, for én fast instans. Skiller seg fra gjennomsnittstilfellet, som er et snitt over instanser, og fra amortisert kjøretid, som er et snitt over operasjonene i en følge.

05 Rangering i lineær tid

Sammenligningsbasert sortering #: Sortering som bare får informasjon om elementene gjennom parvise tester $a_i \le a_j$ . Insertion-Sort, Merge-Sort og Quicksort er sammenligningsbaserte; Counting-Sort, Radix-Sort og Bucket-Sort er det ikke.
Beslutningstre #: Modell for en sammenligningsbasert algoritme på $n$ elementer: hver indre node er en sammenligning med to utfall, hver løvnode en ferdig rekkefølge, og én kjøring er en sti fra rota. Sortering krever minst $n!$ løvnoder, så høyden, antall sammenligninger i verste tilfelle, er minst $\lg n! = \Omega(n \lg n)$ .
Sorteringsgrensen #: Enhver sammenligningsbasert sorteringsalgoritme bruker $\Omega(n \lg n)$ sammenligninger i verste tilfelle. Grensen sier ingenting om beste tilfelle, som kan være $\Theta(n)$ . Den smitter over på et annet problem bare gjennom en reduksjon fra sortering med kjøretid $o(n \lg n)$ .
Rang #: Det $i$ -ende minste elementet i en tabell har rang $i$ . Rang 1 er minimum, rang $n$ maksimum, og medianen har rang $\lfloor (n+1)/2 \rfloor$ , den nederste av de to midterste når $n$ er partall.
Randomized-Select #: Finner elementet med rang $i$ som Quicksort med ett rekursivt kall: Randomized-Partition setter pivoten på plass $q$ med rang $k = q - p + 1$ i segmentet. Er $i = k$ , er pivoten svaret; er $i < k$ , søkes rang $i$ blant de små, ellers rang $i - k$ blant de store. Forventet $\Theta(n)$ for enhver input, $\Theta(n^2)$ i verste tilfelle.
Select #: Rangering i garantert $\Theta(n)$ . Pivoten er medianen av medianene til grupper på fem, funnet med et rekursivt kall, og minst $3n/10$ elementer havner på hver side av den. $T(n) \le T(n/5) + T(7n/10) + \Theta(n) = \Theta(n)$ . Gir også de $k$ minste elementene i lineær tid: finn rang $k$ og del rundt det.
Stabil sortering #: En sorteringsalgoritme er stabil når like nøkler står i samme innbyrdes rekkefølge i output som i input. Insertion-Sort, Merge-Sort og Counting-Sort er stabile; Quicksort er det ikke. Radix-Sort krever en stabil subrutine.
Counting-Sort #: Sorterer $n$ heltall i området $0 .. k$ uten sammenligninger: tell forekomstene av hver verdi i $C$ , gjør $C$ kumulativ slik at $C[v]$ er antall elementer $\le v$ , og gå baklengs gjennom $A$ : trekk én fra $C[A[j]]$ og legg $A[j]$ på den plassen i $B$ . Baklengs gjør den stabil. $\Theta(n + k)$ .
Radix-Sort #: Sorterer $d$ -sifrede tall stabilt på ett siffer om gangen, det minst signifikante først, med Counting-Sort som subrutine. Etter $i$ pass er tallene sortert på de $i$ siste sifrene; stabiliteten er induksjonssteget. $\Theta(d(n + k))$ når hvert siffer har $k + 1$ verdier.
Bucket-Sort #: Antar input uniformt fordelt i $[0, 1)$ . Legg $A[j]$ i bøtte $\lfloor n \cdot A[j] \rfloor$ av $n$ , sorter hver bøtte med Insertion-Sort, og sett bøttene etter hverandre. Forventet $\Theta(n)$ som et snitt over inputer, $\Theta(n^2)$ i verste tilfelle.

06 Rotfaste trestrukturer

Rotfast tre #: Et fritt tre, en sammenhengende graf uten sykler, med én node valgt som rot. Rota har ingen forelder, hver annen node har én, og nodene rett under en node er barna dens. En løvnode har ingen barn; de andre er indre noder. Dybden er antall kanter opp til rota, og høyden $h$ er den største dybden. Representeres med pekere til barna, eller med én peker til første barn og én til neste søsken.
Komplett binærtre #: Et binærtre der alle indre noder har to barn og alle løvnodene har samme dybde. Med høyde $h$ har det $2^h$ løvnoder og $2^h - 1$ indre noder, så $n = 2^{h+1} - 1$ noder i alt og $h = \lfloor \lg n \rfloor$ .
Binært søketre #: Et binærtre med nøkler der alt i venstre deltre til en node er mindre enn eller lik noden og alt i høyre deltre større enn eller lik, for hver node. Søk, innsetting, minimum, maksimum, etterfølger og sletting følger én sti og koster $O(h)$ . Høyden er forventet $\Theta(\lg n)$ for tilfeldig innsettingsrekkefølge og $n - 1$ i verste tilfelle; balanserte søketrær garanterer $\Theta(\lg n)$ .
Inorder-Tree-Walk #: Besøker venstre deltre, så noden, så høyre deltre, rekursivt fra rota. I et binært søketre kommer nøklene ut i sortert rekkefølge. $\Theta(n)$ . Preorder og postorder behandler noden før eller etter de to rekursive kallene.
Tree-Insert #: Søker etter den nye nøkkelen til søket treffer nil, med en peker $y$ ett steg bak $x$ , og henger den nye noden på $y$ som venstre eller høyre barn. En ny node blir alltid en løvnode. $O(h)$ .
Etterfølger #: Noden med den minste nøkkelen som er større enn nøkkelen til $x$ , den neste i Inorder-Tree-Walk. Har $x$ et høyre deltre, er etterfølgeren minimum der; ellers er den den nærmeste noden over $x$ som har $x$ i sitt venstre deltre. Tree-Successor følger én sti, $O(h)$ . Forgjengeren finnes symmetrisk.
Haug #: Et binærtre som er komplett ned til nest nederste nivå, med det nederste fylt fra venstre, lagret i en tabell nummerert nivå for nivå: barna til $i$ er $2i$ og $2i + 1$ , forelderen $\lfloor i/2 \rfloor$ . Haugegenskapen for en maks-haug er $A[\text{Parent}(i)] \ge A[i]$ for alle $i$ unntatt rota, så det største elementet står i rota. En min-haug har $\le$ . Høyden er $\lfloor \lg n \rfloor$ .
Max-Heapify #: Reparerer en maks-haug der bare $A[i]$ kan bryte haugegenskapen: bytt $A[i]$ med det største barnet hvis det er større, og fortsett rekursivt der det mindre elementet havnet. Elementet synker høyst $h$ steg, $O(\lg n)$ .
Build-Max-Heap #: Kaller Max-Heapify på de indre nodene fra $\lfloor n/2 \rfloor$ ned til 1, nedenfra og opp, så begge deltrærne alltid er hauger når turen kommer til en node. $\Theta(n)$ , for de fleste nodene står langt nede og synker lite. Ikke det samme som $n$ kall til Max-Heap-Insert, som koster $\Theta(n \lg n)$ i verste tilfelle.
Prioritetskø #: Dynamisk mengde med nøkler som prioriteter, gjerne med duplikater, som støtter Insert, Maximum, Extract-Max og Increase-Key, eller min-variantene. En maks-haug gir Maximum i $\Theta(1)$ og de tre andre i $O(\lg n)$ : Extract-Max flytter det siste elementet opp i rota og lar det synke, Increase-Key lar elementet stige, og Insert er Increase-Key fra $-\infty$ på en ny siste plass.
Heapsort #: Sortering ved utvelgelse med en maks-haug: bygg haugen av hele $A$ , og bytt så $n - 1$ ganger rota med det siste elementet i haugen, minsk haugen og reparer rota med Max-Heapify. Sorterer på plass, $\Theta(n \lg n)$ i verste tilfelle og $\Theta(n)$ i beste, når alle elementene er like.

07 Dynamisk programmering

Dynamisk programmering #: Designmetode: rekursiv dekomponering der hvert delsvar lagres første gang det regnes ut og slås opp senere. Gir riktig svar når problemet har optimal delstruktur, og lønner seg når delinstansene overlapper. Løses med memoisering ovenfra og ned, eller iterativt nedenfra og opp i topologisk rekkefølge i delinstansgrafen.
Delinstansgraf #: Én node per forskjellig delinstans, og en kant fra $u$ til $v$ når svaret for $v$ bygger på svaret for $u$ . Må være asyklisk, og hver kjede av avhengigheter må ende i et grunntilfelle. Kalltreet til en rekursiv løsning har én node per sti i grafen som ender i instansen. Kjøretiden til dynamisk programmering er som regel lineær i antall noder og kanter.
Overlappende delinstanser #: Flere instanser bygger på den samme delinstansen, direkte eller indirekte. Skjer det på mange nivåer, blir en rekursiv løsning uten lagring eksponentiell. I splitt og hersk overlapper delinstansene ikke, så der gir lagring ingenting.
Optimal delstruktur #: En optimal løsning består av optimale løsninger på delinstansene. Vises som regel ved å bytte ut en del: var den ikke optimal, kunne den byttes ut og gi en bedre løsning. Korteste vei har egenskapen. Lengste enkle vei har den ikke, for to lengste delveier kan bruke de samme nodene.
Memoisering #: Rekursjon med hukommelse: første kall med et argument regner ut svaret og lagrer det, og senere kall med samme argument slår det opp. Løsningen ovenfra og ned (top-down) i dynamisk programmering. Løser bare delinstansene som faktisk trengs.
Lengste felles delsekvens #: Forkortet LCS. En lengste sekvens som er en delsekvens av både $X$ og $Y$ , der en delsekvens er det som står igjen når null eller flere elementer strykes. LCS-Length fyller $c[i, j]$ for prefiksene $X_i$ og $Y_j$ rad for rad og lagrer en pil i $b$ , og Print-LCS følger pilene bakfra. $\Theta(mn)$ .
Det binære ryggsekkproblemet #: Gjenstander med verdi $v_i$ og vekt $w_i$ , og en kapasitet $W$ : velg gjenstander med størst mulig totalverdi og totalvekt høyst $W$ , der hver gjenstand er med eller ikke med. $K[i, j]$ er det beste med gjenstandene $1, \ldots, i$ og kapasitet $j$ , og er den største av verdien uten gjenstand $i$ og verdien med den. $\Theta(nW)$ , som er pseudopolynomisk.
Pseudopolynomisk kjøretid #: Polynomisk som funksjon av et tall fra inputen, men ikke av inputstørrelsen i bits. Ryggsekkløsningen bruker $\Theta(nW)$ , men $W$ tar bare $m = \lfloor \lg W \rfloor + 1$ bits, så kjøretiden er $\Theta(n 2^m)$ .

08 Grådighet

Grådighet #: Designmetode: gjør det valget som ser best ut her og nå, løs den ene delinstansen som er igjen, og sett valget og delløsningen sammen. Valget tas før noen delinstans er løst. Algoritmen er riktig når problemet har grådighetsegenskapen og optimal delstruktur.
Grådighetsegenskapen #: Det finnes en optimal løsning som tar det første grådige valget. Egenskapen sier bare at det første valget er trygt. At alle de grådige valgene er trygge, følger først sammen med optimal delstruktur, ved induksjon.
Utvekslingsargument #: Bevis for grådighetsegenskapen: ta en vilkårlig optimal løsning, bytt ut ett av valgene med det grådige, og vis at løsningen fortsatt er lovlig og ikke blir dårligere. Da finnes en optimal løsning med det grådige valget.
Det kontinuerlige ryggsekkproblemet #: Som det binære ryggsekkproblemet, men du kan ta med en andel mellom 0 og 1 av hver gjenstand og får samme andel av verdien. Løses grådig: fyll sekken etter synkende kilopris $v_i / w_i$ , så bare den siste gjenstanden blir delt. $O(n \lg n)$ med sorteringen.
Aktivitetsutvalg #: Velg flest mulig aktiviteter $[s_i, f_i)$ der ingen to overlapper. Det grådige valget er aktiviteten som slutter først, og delinstansen som er igjen, er aktivitetene som starter ved sluttiden dens eller senere. Greedy-Activity-Selector bruker $\Theta(n)$ når aktivitetene er sortert etter sluttid.
Prefiksfri kode #: Binær kode der ingen kodeord er et prefiks av et annet, så en kodet tekst kan dekodes ett kodeord om gangen fra starten. Tegnes som et kodetre med tegnene i løvnodene: kodeordet er stien fra rota, med 0 for venstre og 1 for høyre barn, og lengden er dybden.
Huffman-kode #: En optimal prefiksfri kode, laget av Huffmans algoritme. Hvert tegn starter som et tre i en min-prioritetskø på frekvens, og $n - 1$ ganger slås de to trærne med lavest frekvens sammen under en ny node med summen av frekvensene. $O(n \lg n)$ med en binær haug.

09 Traversering av grafer

Nabolister #: Grafrepresentasjon med én liste per node: $G.\mathit{Adj}[u]$ inneholder ut-naboene til $u$ . Tar $\Theta(V + E)$ plass. Å gå gjennom naboene til $u$ tar tid proporsjonal med antallet, men å sjekke om $(u, v)$ er en kant krever et søk i lista. Standardvalget for traversering.
Nabomatrise #: Grafrepresentasjon som en $|V| \times |V|$ -tabell der $a_{uv} = 1$ når $(u, v)$ er en kant. Tar $\Theta(V^2)$ plass uansett antall kanter, og svarer på om $(u, v)$ er en kant i konstant tid. Symmetrisk for en urettet graf.
Traverseringstre #: Treet som forgjengerkantene $(v.\pi, v)$ danner etter en traversering, med startnoden som rot. BFS gir et bredde-først-tre der stien fra rota er en korteste vei. DFS gir en dybde-først-skog med ett tre per kall fra hovedløkka.
Dybde-først-søk #: Forkortet DFS. Traversering som går videre fra den nyeste noden den har oppdaget: DFS-Visit kaller seg selv på hver hvite nabo med en gang. DFS starter fra hver hvite node etter tur og gir hver node en starttid $u.d$ og en sluttid $u.f$ . $\Theta(V + E)$ .
Parentesteoremet #: I en dybde-først-skog er intervallene $[u.d, u.f]$ og $[v.d, v.f]$ enten disjunkte, eller så ligger det ene inni det andre, og da er den indre noden en etterkommer av den ytre. Skrives «(u» ved $u.d$ og «u)» ved $u.f$ , blir parentesene riktig nøstet.
Hvit-sti-teoremet #: $v$ er en etterkommer av $u$ i en dybde-først-skog hvis og bare hvis det, da $u$ ble oppdaget, fantes en sti fra $u$ til $v$ med bare hvite noder.
Kantklassifisering #: DFS deler kantene i tre-kanter (i dybde-først-skogen), bakoverkanter (til en forfader), foroverkanter (til en etterkommer, utenfor treet) og krysskanter (alle andre). Kanten $(u, v)$ er en tre-kant hvis $v$ er hvit når den undersøkes, en bakoverkant hvis $v$ er grå, og en forover- eller krysskant hvis $v$ er svart. En rettet graf har en sykel hvis og bare hvis DFS finner en bakoverkant.
DAG #: Rettet asyklisk graf: en rettet graf uten sykler. Har en topologisk sortering, og DFS finner ingen bakoverkanter i den.
Topologisk sortering #: En rekkefølge av nodene i en DAG der $u$ kommer før $v$ for hver kant $(u, v)$ . Topological-Sort kjører DFS og setter hver node først i en lenket liste når den blir ferdig, så lista blir sortert etter synkende sluttid. $\Theta(V + E)$ .
Sterke komponenter #: De største mengdene av noder i en rettet graf der hver node kan nå hver annen langs rettede stier. Kollapses hver komponent til én node, blir grafen en DAG. Strongly-Connected-Components kjører DFS på $G$ , og så DFS på $G^{\mathrm T}$ med startnodene etter synkende sluttid: hvert tre er én komponent. $\Theta(V + E)$ .
Bredde-først-søk #: Forkortet BFS. Traversering med en FIFO-kø fra en startnode $s$ : nodene besøkes lag for lag, i stigende avstand. Gir $v.d = \delta(s, v)$ , korteste vei målt i antall kanter, og et bredde-først-tre av forgjengerkanter. $O(V + E)$ .