Föreläsning 11

Grafer

[kapitel 12]
OH-bilder från denna föreläsning

Vad är en graf?
Terminologi, varianter

Hur lagrar man grafer?

Graftraversering
Djupet-först
Bredden-först

Vad är en DAG?
Directed Acyclic Graph
"Nästan" ett träd

Viktade grafer
Grafer där man kan tala om avstånd och väglängd
Intressanta optimeringsproblem

Hur hittar man kortaste vägen?
Dijkstra's algoritm

Hur hittar man det billigaste sättet att koppla ihop en graf?
Minimum-spanning-tree problemet
Kruskal's och Prim-Jarník's algoritmer