Graphen-Algorithmen

BFS (Breadth-First Search)

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    console.log(node);
    for (const next of graph[node])
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
  }
}

Findet kürzeste Wege in ungewichteten Graphen. O(V + E).

DFS (Depth-First Search)

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);
  for (const next of graph[node])
    dfs(graph, next, visited);
}

Geht erst tief in eine Richtung, dann zurück. Für Topologische Sortierung, Zyklen-Erkennung.

Dijkstra — kürzester Weg im gewichteten Graph

Mit Priority-Queue: O((V+E) log V). Funktioniert nur bei nicht-negativen Gewichten. Für negative Gewichte → Bellman-Ford O(V·E).