Graf

En ikke-lineær datastruktur bestående af knuder (vertices) forbundet med kanter (edges).

Kompleksitet

Operation	Tidskompleksitet
Access	`O(V + E)`
Search	`O(V + E)`
Insertion	`O(1)`
Deletion	`O(V + E)`

Beskrivelse

En graf er en kraftfuld datastruktur der består af knuder (vertices) og kanter (edges) der forbinder disse knuder. Grafer kan være rettede (retningsbestemte kanter som envejsgader) eller urettede (tovejsforbindelser), vægtede (kanter med vægt/omkostning) eller uvægtede, og cykliske eller acykliske. Grafer repræsenteres typisk via nabolister (hver knude har liste af naboer) eller nabomatricer (2D array af forbindelser). De er fundamentale for at modellere relationer og netværk - fra sociale netværk til transportsystemer. Klassiske grafalgoritmer inkluderer Dijkstras korteste vej, bredde-først-søgning (BFS), dybde-først-søgning (DFS), og minimum udspændende træer. Grafer er essentielle i moderne computing for routing, planlægning, afhængighedsopløsning og meget mere.

Kode Eksempel

// JavaScript Graph implementation (naboliste)
class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  // Tilføj knude
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  // Tilføj kant
  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1); // Urettet
  }

  // Fjern kant
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1]
      .filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2]
      .filter(v => v !== vertex1);
  }

  // Bredde-først-søgning
  bfs(start) {
    const queue = [start];
    const visited = new Set([start]);
    const result = [];

    while (queue.length) {
      const vertex = queue.shift();
      result.push(vertex);

      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      });
    }
    return result;
  }

  // Dybde-først-søgning
  dfs(start, visited = new Set(), result = []) {
    visited.add(start);
    result.push(start);

    this.adjacencyList[start].forEach(neighbor => {
      if (!visited.has(neighbor)) {
        this.dfs(neighbor, visited, result);
      }
    });
    return result;
  }
}

Anvendelsesområder

•Sociale netværk (venner, følgere)
•Navigation og GPS-routing
•Afhængighedsopløsning i pakkehåndtering
•Netværkstopologi og routingprotokoller
•Anbefalingssystemer

Fordele

✓Modellerer komplekse relationer naturligt
✓Fleksibel til mange domæner
✓Kraftfulde traverseringsalgoritmer
✓Understøtter vægtede og rettede forbindelser
✓Skalerer til meget store netværk

Ulemper

✗Kompleks at implementere korrekt
✗Kan være hukommelseskrævende
✗Nogle algoritmer har høj tidskompleksitet
✗Svær at visualisere ved store grafer
✗Cyklusdetektion kan være kompleks

Eksempler fra den virkelige verden

•Facebook vennenetværk
•Google Maps vejnetværk
•LinkedIn professionelle forbindelser
•Flyruteplan mellem byer
•Internet-routing mellem servere

Relaterede strukturer

Directed GraphWeighted GraphTreeDAGNetwork Flow