深度优先搜索 （Depth-first search）

在深度优先搜索(DFS)中，我们从一个特定的顶点开始，在回溯(backtracking)之前沿着每个分支尽可能地搜索。在DFS中，我们还需要跟踪访问过的顶点。在实现DFS时，我们使用堆栈数据结构来支持回溯。

图3表示对图2中使用的同一个示例图进行DFS遍历的动画。注意它是如何遍历到深度和回溯的。

应用

• 用于查找两个顶点之间的路径。
• 用于检测图中的循环。
• 用于拓扑排序。
• 用于解决只有一个解的谜题(如迷宫)

无权重的框架

import java.util.*;

public class Graph {
    private Map<String, List<String>> map = new HashMap<>();

    // 添加边
    public void addEdge(String source, String destination) {
        if (!map.containsKey(source))
            map.put(source, new LinkedList<String>());

        if (!map.containsKey(destination))
            map.put(destination, new LinkedList<String>());

        map.get(source).add(destination);
    }

    // DFS算法
    public void DFS(String start) {
        Set<String> visited = new HashSet<>();
        DFSUtil(start, visited);
    }

    // 递归辅助函数
    private void DFSUtil(String node, Set<String> visited) {
        // 标记当前节点为已访问
        visited.add(node);
        System.out.println(node);

        // 遍历所有邻接节点
        for (String neighbor : map.get(node)) {
            if (!visited.contains(neighbor)) {
                DFSUtil(neighbor, visited);
            }
        }
    }

    // 主函数，用于测试
    public static void main(String args[]) {
        Graph g = new Graph();

        // 构建图
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "E");
        g.addEdge("C", "F");
        g.addEdge("E", "F");

        // 执行DFS
        g.DFS("A");
    }
}

有权重的框架

import java.util.*;

public class WeightedGraph {
    private Map<String, List<Edge>> map = new HashMap<>();

    static class Edge {
        String destination;
        double weight;

        public Edge(String destination, double weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }

    // 添加有权重的边
    public void addEdge(String source, String destination, double weight) {
        if (!map.containsKey(source))
            map.put(source, new LinkedList<Edge>());

        map.get(source).add(new Edge(destination, weight));

        // 如果是无向图，也可以添加反向边
        // if (!map.containsKey(destination))
        //     map.put(destination, new LinkedList<Edge>());
        // map.get(destination).add(new Edge(source, weight));
    }

    // DFS算法
    public void DFS(String start) {
        Set<String> visited = new HashSet<>();
        DFSUtil(start, visited);
    }

    // 递归辅助函数
    private void DFSUtil(String node, Set<String> visited) {
        visited.add(node);
        System.out.println(node);

        if (map.containsKey(node)) {
            for (Edge edge : map.get(node)) {
                if (!visited.contains(edge.destination)) {
                    System.out.println("Edge: " + node + " -> " + edge.destination + " (Weight: " + edge.weight + ")");
                    DFSUtil(edge.destination, visited);
                }
            }
        }
    }

    // 主函数，用于测试
    public static void main(String args[]) {
        WeightedGraph g = new WeightedGraph();

        // 构建图
        g.addEdge("A", "B", 1.0);
        g.addEdge("A", "C", 2.0);
        g.addEdge("B", "D", 3.0);
        g.addEdge("B", "E", 4.0);
        g.addEdge("C", "F", 5.0);
        g.addEdge("E", "F", 6.0);

        // 执行DFS
        g.DFS("A");
    }
}