Java实现图的深度优先搜索

简介

图的深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索图数据结构的算法。在图中，深度优先搜索从起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续，然后回溯到上一个节点，继续探索其他未访问的路径。Java 作为一种广泛使用的编程语言，提供了丰富的工具和数据结构来实现图的深度优先搜索。本文将详细介绍 Java 实现图的深度优先搜索的基础概念、使用方法、常见实践以及最佳实践。

目录

1. 基础概念
   • 图的表示
   • 深度优先搜索算法原理
2. 使用方法
   • 邻接表实现图
   • 递归实现深度优先搜索
   • 非递归（使用栈）实现深度优先搜索
3. 常见实践
   • 检测图中的环
   • 拓扑排序
4. 最佳实践
   • 优化内存使用
   • 提高算法效率
5. 小结
6. 参考资料

基础概念

图的表示

在 Java 中，图通常有两种常见的表示方法：邻接矩阵和邻接表。

• 邻接矩阵：使用一个二维数组 adjMatrix 来表示图，其中 adjMatrix[i][j] 表示顶点 i 和顶点 j 之间是否有边。如果 adjMatrix[i][j] == 1，则表示有边；否则表示无边。这种表示方法简单直观，但对于稀疏图会浪费大量内存。
• 邻接表：使用链表或动态数组来存储每个顶点的邻接顶点。对于每个顶点，都有一个链表或数组来存储与其相连的顶点。这种表示方法更适合稀疏图，内存利用率更高。

深度优先搜索算法原理

深度优先搜索从起始顶点开始，标记该顶点为已访问，然后递归地访问其所有未访问的邻接顶点。如果在访问过程中遇到一个已访问的顶点，则跳过它。当所有可达顶点都被访问后，算法结束。

使用方法

邻接表实现图

import java.util.ArrayList;
import java.util.List;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    public List<List<Integer>> getAdjList() {
        return adjList;
    }
}

递归实现深度优先搜索

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    public List<List<Integer>> getAdjList() {
        return adjList;
    }
}

class DFSRecursive {
    private boolean[] visited;

    public DFSRecursive(int vertices) {
        visited = new boolean[vertices];
    }

    public void dfs(Graph graph, int startVertex) {
        visited[startVertex] = true;
        System.out.print(startVertex + " ");

        List<Integer> adjVertices = graph.getAdjList().get(startVertex);
        for (int adjVertex : adjVertices) {
            if (!visited[adjVertex]) {
                dfs(graph, adjVertex);
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点数:");
        int vertices = scanner.nextInt();
        Graph graph = new Graph(vertices);

        System.out.println("请输入边数:");
        int edges = scanner.nextInt();
        for (int i = 0; i < edges; i++) {
            System.out.println("请输入第 " + (i + 1) + " 条边的起点和终点:");
            int source = scanner.nextInt();
            int destination = scanner.nextInt();
            graph.addEdge(source, destination);
        }

        DFSRecursive dfsRecursive = new DFSRecursive(vertices);
        System.out.println("深度优先搜索结果:");
        dfsRecursive.dfs(graph, 0);
    }
}

非递归（使用栈）实现深度优先搜索

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Scanner;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    public List<List<Integer>> getAdjList() {
        return adjList;
    }
}

class DFSNonRecursive {
    public void dfs(Graph graph, int startVertex) {
        boolean[] visited = new boolean[graph.vertices];
        Stack<Integer> stack = new Stack<>();

        stack.push(startVertex);

        while (!stack.isEmpty()) {
            int currentVertex = stack.pop();
            if (!visited[currentVertex]) {
                visited[currentVertex] = true;
                System.out.print(currentVertex + " ");

                List<Integer> adjVertices = graph.getAdjList().get(currentVertex);
                for (int i = adjVertices.size() - 1; i >= 0; i--) {
                    int adjVertex = adjVertices.get(i);
                    if (!visited[adjVertex]) {
                        stack.push(adjVertex);
                    }
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点数:");
        int vertices = scanner.nextInt();
        Graph graph = new Graph(vertices);

        System.out.println("请输入边数:");
        int edges = scanner.nextInt();
        for (int i = 0; i < edges; i++) {
            System.out.println("请输入第 " + (i + 1) + " 条边的起点和终点:");
            int source = scanner.nextInt();
            int destination = scanner.nextInt();
            graph.addEdge(source, destination);
        }

        DFSNonRecursive dfsNonRecursive = new DFSNonRecursive();
        System.out.println("深度优先搜索结果:");
        dfsNonRecursive.dfs(graph, 0);
    }
}

常见实践

检测图中的环

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    public List<List<Integer>> getAdjList() {
        return adjList;
    }
}

class CycleDetection {
    private boolean[] visited;
    private boolean[] recursionStack;

    public CycleDetection(int vertices) {
        visited = new boolean[vertices];
        recursionStack = new boolean[vertices];
    }

    public boolean isCyclic(Graph graph, int vertex) {
        visited[vertex] = true;
        recursionStack[vertex] = true;

        List<Integer> adjVertices = graph.getAdjList().get(vertex);
        for (int adjVertex : adjVertices) {
            if (!visited[adjVertex] && isCyclic(graph, adjVertex)) {
                return true;
            } else if (recursionStack[adjVertex]) {
                return true;
            }
        }

        recursionStack[vertex] = false;
        return false;
    }

    public boolean hasCycle(Graph graph) {
        for (int i = 0; i < graph.vertices; i++) {
            if (!visited[i] && isCyclic(graph, i)) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点数:");
        int vertices = scanner.nextInt();
        Graph graph = new Graph(vertices);

        System.out.println("请输入边数:");
        int edges = scanner.nextInt();
        for (int i = 0; i < edges; i++) {
            System.out.println("请输入第 " + (i + 1) + " 条边的起点和终点:");
            int source = scanner.nextInt();
            int destination = scanner.nextInt();
            graph.addEdge(source, destination);
        }

        CycleDetection cycleDetection = new CycleDetection(vertices);
        if (cycleDetection.hasCycle(graph)) {
            System.out.println("图中存在环");
        } else {
            System.out.println("图中不存在环");
        }
    }
}

拓扑排序

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Scanner;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    public List<List<Integer>> getAdjList() {
        return adjList;
    }
}

class TopologicalSort {
    private boolean[] visited;
    private Stack<Integer> stack;

    public TopologicalSort(int vertices) {
        visited = new boolean[vertices];
        stack = new Stack<>();
    }

    public void dfs(Graph graph, int vertex) {
        visited[vertex] = true;

        List<Integer> adjVertices = graph.getAdjList().get(vertex);
        for (int adjVertex : adjVertices) {
            if (!visited[adjVertex]) {
                dfs(graph, adjVertex);
            }
        }

        stack.push(vertex);
    }

    public void topologicalSort(Graph graph) {
        for (int i = 0; i < graph.vertices; i++) {
            if (!visited[i]) {
                dfs(graph, i);
            }
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点数:");
        int vertices = scanner.nextInt();
        Graph graph = new Graph(vertices);

        System.out.println("请输入边数:");
        int edges = scanner.nextInt();
        for (int i = 0; i < edges; i++) {
            System.out.println("请输入第 " + (i + 1) + " 条边的起点和终点:");
            int source = scanner.nextInt();
            int destination = scanner.nextInt();
            graph.addEdge(source, destination);
        }

        TopologicalSort topologicalSort = new TopologicalSort(vertices);
        System.out.println("拓扑排序结果:");
        topologicalSort.topologicalSort(graph);
    }
}

最佳实践

优化内存使用

• 使用合适的图表示方法：对于稀疏图，优先选择邻接表；对于稠密图，可以考虑邻接矩阵。
• 及时释放不再使用的内存：例如，在图遍历结束后，释放相关的辅助数据结构（如访问标记数组、栈等）。

提高算法效率

• 减少不必要的计算：在检测环或进行拓扑排序时，利用已经计算的结果，避免重复计算。
• 并行化处理：对于大规模图，可以考虑使用多线程或并行计算框架来加速深度优先搜索。

小结

本文详细介绍了 Java 实现图的深度优先搜索的相关知识，包括基础概念、使用方法、常见实践以及最佳实践。通过递归和非递归的实现方式，读者可以更好地理解深度优先搜索的原理和应用。在实际应用中，根据具体需求选择合适的图表示方法和优化策略，能够提高算法的效率和性能。

参考资料

• 《算法导论》
• Oracle Java 官方文档
• 各种在线算法教程和技术论坛