Connected Components: DFS, BFS und Union-Find

Eine Connected Component ist eine maximale Gruppe von Knoten in einem ungerichteten Graphen, in der zwischen jedem Knotenpaar ein Pfad existiert.

Grundidee

Für jeden noch nicht besuchten Knoten:

1. DFS oder BFS starten.
2. Alle erreichten Knoten bilden eine Komponente.
3. Mit dem nächsten unbesuchten Knoten wiederholen.

JavaScript

function components(graph) {
  const visited = new Set();
  const result = [];

  for (const start of Object.keys(graph)) {
    if (visited.has(start)) continue;

    const stack = [start];
    const component = [];

    visited.add(start);

    while (stack.length) {
      const node = stack.pop();
      component.push(node);

      for (const next of graph[node] ?? []) {
        if (!visited.has(next)) {
          visited.add(next);
          stack.push(next);
        }
      }
    }

    result.push(component);
  }

  return result;
}

Unterschied zu SCC

Connected Components beziehen sich normalerweise auf ungerichtete Graphen.

Bei gerichteten Graphen unterscheidet man Weakly Connected und Strongly Connected Components.

Union-Find

Bei dynamischen Kanten ist Disjoint Set Union eine effiziente Alternative, um Komponenten zu verwalten und Connectivity Queries zu beantworten.

Anwendungen

• soziale Netzwerke
• Number of Islands
• Netzwerkpartitionen
• Connected Component Labeling
• Infrastrukturnetze

Komplexität

Mit Adjazenzlisten:

O(V + E)

Fazit

Jede neue DFS/BFS-Suche von einem unbesuchten Knoten entdeckt genau eine Connected Component.