WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C

Tiefensuche (DFS) in C

Die Tiefensuche (DFS) untersucht den nächsten Zweig eines Graphen, bevor sie zu den übrigen Nachbarn zurückkehrt. Das Beispiel zeigt eine rekursive Traversierung, die Markierung besuchter Knoten und eine deterministische Ausgabereihenfolge.

Version: C23; repository compiler flag, production runtime not attested

Syntax

void dfs(int v);

Die Tiefensuche (depth-first search, DFS) verfolgt den nächsten Zweig, bevor sie zu den übrigen Nachbarn zurückkehrt. Eine rekursive Traversierung (recursive traversal) setzt dieses Muster durch Funktionsaufrufe für unbesuchte Nachbarn um; nach der Rückkehr wird die vorherige Schleife fortgesetzt. DFS selbst legt nicht fest, wann ein Knoten verarbeitet wird; dieses Beispiel gibt ihn beim Entdecken aus.

Im Beispiel steht graph[v][u] für eine gerichtete Kante von v nach u. Die Funktion dfs setzt visited[v], bevor sie weitere Aufrufe ausführt. Daher führt der Zyklus 0 → 1 → 3 → 0 nicht zu einem erneuten Aufruf für 0. Die aufsteigende Reihenfolge von u ergibt 0, 1, 3, 2, 4, jeweils in einer eigenen Zeile. Jeder übergebene Index liegt im Bereich 0–N - 1.

Der Aufruf dfs(0) besucht nur Knoten, die von 0 aus erreichbar sind. Um den gesamten Graphen abzudecken, rufen Sie dfs für jeden noch unbesuchten Knoten auf. Setzen Sie visited zurück, bevor Sie eine unabhängige Traversierung erneut starten.

Bei einer Adjazenzmatrix benötigt eine vollständige Traversierung O(V²) Zeit; eine Adjazenzlisten-Darstellung ermöglicht O(V + E), wobei V und E die Anzahl der Knoten beziehungsweise Kanten bezeichnen. Das Besuchsarray und der Aufrufstapel benötigen O(V) zusätzlichen Speicher. Eine große Rekursionstiefe kann den Aufrufstapel erschöpfen; ein expliziter Stapel ist eine Alternative. Der Repository-Kontext nennt C23 als Compiler-Flag, bestätigt jedoch keine Produktionslaufzeit.

Beispiele

#include <stdio.h>

enum { N = 5 };

static const int graph[N][N] = {
    {0, 1, 1, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 0, 0, 1},
    {1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0}
};
static int visited[N] = {0};

static void dfs(int v)
{
    visited[v] = 1;
    printf("%d\n", v);

    for (int u = 0; u < N; ++u) {
        if (graph[v][u] && !visited[u]) {
            dfs(u);
        }
    }
}

int main(void)
{
    dfs(0);
    return 0;
}

Ergebnis

0
1
3
2
4

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen