Kapittel 20 - Elementary Graph Algorithms

Dette kapittelet presenterer metoder for å representere og søke i en graf. Søking betyr å følge kantene i grafen for å besøke noder.

---

Traversering av grafer

Denne delen av kapittelet tar for seg ulike grafsøk.

Graf

Noder og kanter: En graf $G=(V,E)$ består av en mengde noder (vertices) $V$, og kanter (edges) $E$. Vi skriver en kant mellom node 1 og 2 som $(1,2)\in E$.

Sti: En sekvens av noder slik at det eksisterer en kant mellom påfølgende noder.

Rettet graf: En graf der kantene har en retning, indikert med piler.

Urettet graf: Implisitt indikerer at $(u,v)=(v,u)$, og er som regel ikke merket med piler

Syklisk graf: En graf som inneholder minst en sykel, altså en sti fra en node tilbake til seg selv igjen uten å gå samme vei. #FFF3A3A6;">Et tre er en urettet graf hvor det kun eksisterer en sti mellom hvert nodepar (ikke syklisk).

Link to original

Undertemaer

Grafrepresentasjon Bredde-først søk (BFS) Dybde-først søk (DFS) Topologisk sortering

Link to original