Tiefensuche (DFS)

1def dfs(graph, node, visited):2    visited.add(node)3    order = [node]4    for neighbor in graph[node]:5        if neighbor not in visited:6            order.extend(dfs(graph, neighbor, visited))7    return order8
9
10graph = {11    "A": ["B", "C"],12    "B": ["D", "E"],13    "C": ["F"],14    "D": [],15    "E": ["F"],16    "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))

1const graph = {2    A: ["B", "C"],3    B: ["D", "E"],4    C: ["F"],5    D: [],6    E: ["F"],7    F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11    if (visited.has(node)) return order;12    visited.add(node);13    order.push(node);14    for (const next of graph[node]) {15        dfs(next, visited, order);16    }17    return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));

1import java.util.List;2
3public class Main {4    static List<List<Integer>> adj = List.of(5        List.of(1, 2),    // neighbors of 06        List.of(0, 3, 4), // neighbors of 17        List.of(0, 5),    // neighbors of 28        List.of(1),9        List.of(1, 5),10        List.of(2, 4)11    );12    static boolean[] visited = new boolean[6];13
14    static void dfs(int node) {15        visited[node] = true;16        System.out.print(" " + node);17        for (int next : adj.get(node)) {18            if (!visited[next]) dfs(next);19        }20    }21
22    public static void main(String[] args) {23        System.out.print("DFS from 0:");24        dfs(0);25        System.out.println();26    }27}

1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5         std::vector<bool>& visited) {6    visited[node] = true;7    std::cout << node << " ";8    // Recurse into every unvisited neighbor9    for (int next : adj[node]) {10        if (!visited[next]) dfs(next, adj, visited);11    }12}13
14int main() {15    // 6-node undirected graph as an adjacency list16    std::vector<std::vector<int>> adj = {17        {1, 2},     // 018        {0, 3, 4},  // 119        {0, 5},     // 220        {1},        // 321        {1, 5},     // 422        {2, 4},     // 523    };24    std::vector<bool> visited(adj.size(), false);25    std::cout << "DFS from node 0: ";26    dfs(0, adj, visited);27    std::cout << "\n";28    return 0;29}

1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8    {0, 1, 1, 0, 0, 0},9    {1, 0, 0, 1, 1, 0},10    {1, 0, 0, 0, 0, 1},11    {0, 1, 0, 0, 0, 0},12    {0, 1, 0, 0, 0, 1},13    {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18    visited[node] = true;19    printf("%d ", node);20    // Recurse into every unvisited neighbor21    for (int next = 0; next < N; next++) {22        if (adj[node][next] && !visited[next]) dfs(next);23    }24}25
26int main(void) {27    printf("DFS from node 0: ");28    dfs(0);29    printf("\n");30    return 0;31}