Grafer — adjacency-liste/matrix, BFS, DFS

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Grafer — adjacency-liste/matrix, BFS, DFS

Graf (Graph): abstrakt datastruktur bestående af noder (vertices) og kanter (edges).

Urettet graf: kanter er symmetriske (A-B = B-A).

Rettet graf (digraph): kanter har retning (A→B ≠ B→A).

Vægtet graf: kanter har tal-værdier (distancer, omkostninger).

Repræsentation: Adjacency matrix (n×n-matrix): hurtig edge-lookup O(1), men O(n²) pladsforbrug. God til tætte grafer.

Adjacency list (dict/list): O(E) pladsforbrug. God til sparsomme grafer.

Traverseringsalgoritmer: BFS (Breadth-First Search): bruger kø, udforsker lag for lag. Finder korteste vej i uvægtede grafer. O(V+E).

DFS (Depth-First Search): bruger stak (rekursiv), udforsker dybt ad én sti. O(V+E). Bruges til topologisk sortering, findet komponenter.

Dijkstras algoritme: korteste vej i vægtede grafer (kun positive vægte). O((V+E) log V) med min-heap. *A\-algoritme**: heuristisk søgning — bruges i navigationssystemer og spil-AI.

Topologisk sortering: lineær ordning af DAG-noder. Bruges til opgaverækkefølge-problemer.

Anvendelser

sociale netværk, GPS-navigation, compiler-afhængigheder, ML-grafer (computational graphs).

Læringsmål

• Repræsentere en graf som adjacency-liste eller -matrix
• Implementere bredde-først-søgning (BFS) og dybde-først-søgning (DFS)
• Vælge mellem BFS og DFS ud fra en given problemstilling

Sådan kan du arbejde med emnet

• Repræsentér en given graf som en adjacency-liste og en adjacency-matrix og sammenlign pladsforbrug
• Implementér BFS og DFS på en graf og brug dem til at finde alle noder tilgængelige fra en startnode
• Diskutér, hvornår BFS er bedre end DFS til at løse et problem

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.