Skip to content

🚀 Tiefensuchbäume (DFS-Trees) und ihre Anwendung

Da wir gerade über Artikulationspunkte und Brücken gesprochen haben, ist der nächste logische Schritt, den Tiefensuchbaum (DFS-Tree) zu behandeln.
Der DFS-Tree ist die Grundlage für viele Graph-Algorithmen, einschließlich der Erkennung von Artikulationspunkten und Brücken.

📚 1️⃣ Was ist ein Tiefensuchbaum (DFS-Tree)?

  • Ein Tiefensuchbaum ist ein Spanning Tree, der entsteht, wenn man einen Graphen mit der Depth-First Search (DFS) durchläuft.
  • Jeder Knoten wird genau einmal besucht, und die Kanten, die benutzt werden, um den Graphen zu erkunden, bilden den DFS-Tree.

✅ Wichtige Begriffe:

  1. Tree Edge (Baumkante):

    • Kanten, die im DFS verwendet werden, um einen neuen Knoten zu erreichen.
    • Teil des DFS-Trees.

    • Back Edge (Rückkante):

    • Kanten, die einen Knoten mit einem bereits besuchten Vorfahren verbinden.

    • Sie zeigen, dass ein Zyklus im Graphen existiert.

    • Forward Edge (Vorwärtskante):

    • Kanten, die von einem Knoten zu einem bereits besuchten Nachkommen führen (nur in gerichteten Graphen relevant).

    • Cross Edge (Quer-Kante):

    • Verbindet zwei nicht direkt verwandte Knoten im DFS-Tree (z.B. zwei Knoten aus verschiedenen Teilbäumen).

🌍 2️⃣ Beispiel: DFS-Tree mit einem ungerichteten Graphen

Graph:

    A
   / \
  B   C
   \ / \
    D   E
Start bei A.

✅ DFS-Traversierung (A → B → D → C → E):

  1. Baumkanten (Tree Edges):

    • A → B
    • B → D
    • D → C
    • C → E

    • Rückkante (Back Edge):

    • C → A (zurück zu einem Vorfahren)

🌳 DFS-Tree (Spanning Tree):

    A
   /
  B
   \
    D
     \
      C
       \
        E

🚩 3️⃣ Anwendung des DFS-Trees: Artikulationspunkte & Brücken

✅ Artikulationspunkte (Cut Vertices):

  • Regel: Ein Knoten ist ein Artikulationspunkt, wenn das Entfernen des Knotens den Graphen in getrennte Komponenten zerlegt.

  • In unserem Beispiel:

    • B und D sind Artikulationspunkte.

✅ Brücken (Cut Edges):

  • Regel: Eine Kante ist eine Brücke, wenn sie keinen Zyklus bildet.

  • In unserem Beispiel:

    • B-D ist eine Brücke.

4️⃣ Low- und Discovery-Times (für DFS-Algorithmen)

  • Discovery Time (disc[]): Der Zeitpunkt, an dem ein Knoten zum ersten Mal besucht wird.
  • Low-Value (low[]): Der kleinste Discovery-Wert, der von diesem Knoten oder über Rückkanten erreicht werden kann.

✅ Formeln:

  • Für jeden Knoten u: (\(low[u]=min⁡(disc[u],disc[v],low[w])\)\)
    • v = Nachbar von u (falls Rückkante)
    • w = Kind von u im DFS-Tree
#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int time = 0;

void DFS(int u, int graph[MAX][MAX], int n, bool visited[], int parent[]) {
    visited[u] = true;
    printf("Besucht: %d\n", u);

    for (int v = 0; v < n; v++) {
        if (graph[u][v]) {
            if (!visited[v]) {
                parent[v] = u;  // Baumkante
                DFS(v, graph, n, visited, parent);
            } else if (v != parent[u]) {
                // Rückkante gefunden
                printf("Rückkante: %d ↔ %d\n", u, v);
            }
        }
    }
}

void createDFSTree(int graph[MAX][MAX], int n, int start) {
    bool visited[MAX] = {false};
    int parent[MAX];

    for (int i = 0; i < n; i++) {
        parent[i] = -1;
    }

    printf("DFS-Tree:\n");
    DFS(start, graph, n, visited, parent);

    printf("\nBaumkanten:\n");
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            printf("%d - %d\n", parent[i], i);
        }
    }
}

int main() {
    int n = 5;
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 1, 1},
        {0, 1, 1, 0, 1},
        {0, 0, 1, 1, 0}
    };

    createDFSTree(graph, n, 0);  // Startknoten: 0

    return 0;
}

✅ Beispiel-Graph:

    0
   / \
  1   2
   \ / \
    3   4

Ausgabe:

DFS-Tree:
Besucht: 0
Besucht: 1
Besucht: 3
Besucht: 2
Besucht: 4

Baumkanten:
0 - 1
1 - 3
3 - 2
2 - 4

Rückkante: 2 ↔ 0
Rückkante: 2 ↔ 1

🚀 6️⃣ Fazit

  • ✅ DFS-Trees sind die Basis für viele Algorithmen, z.B. zur Erkennung von Artikulationspunkten und Brücken.
  • ✅ Tree Edges und Back Edges sind entscheidend für die Struktur des DFS-Trees.
  • ✅ Low- und Discovery-Times helfen, kritische Knoten und Kanten zu identifizieren.dfs.svgbfs.svg