java 语言实现深度优先搜索（DFS）图算法_java实现dfs

深度优先搜索（DFS）是一种非常强大的图算法，它可以用于解决许多与图相关的问题。深度优先搜索算法的核心思想是递归地探索每个节点的邻居节点，直到到达最深处，然后再回溯到上一个节点，继续探索其他未被访问的节点。

在深度优先搜索中，使用栈数据结构来保存待访问的节点。具体实现中，有两种常用的方法：递归和迭代。

递归实现深度优先搜索：

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

class Graph {
    private int numVertices;  // 图的顶点数
    private List<List<Integer>> adjList;  // 用邻接表表示图

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new ArrayList<>();

        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }
    
    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);  // 若是有向图则不需要这一行
    }

    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int neighbor : adjList.get(vertex)) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    public void dfs(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        dfsUtil(startVertex, visited);
    }
}

public class DFS {
    public static void main(String[] args) {
        int numVertices = 7;
        Graph graph = new Graph(numVertices);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        System.out.println("Depth First Traversal (starting from vertex 0): ");
        graph.dfs(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

在这个示例中，我们定义了一个Graph类来表示图，它使用邻接表来存储边关系。addEdge方法用于添加边。在dfsUtil方法中，我们使用递归来实现深度优先搜索。我们首先将当前节点标记为已访问，并打印节点的值。然后，我们迭代该节点的邻居节点，如果邻居节点尚未被访问，则递归调用dfsUtil方法。

在dfs方法中，我们创建一个visited数组来记录节点是否已访问，并调用dfsUtil方法进行深度优先搜索。

迭代实现深度优先搜索：

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

class Graph {
    private int numVertices;  // 图的顶点数
    private List<List<Integer>> adjList;  // 用邻接表表示图

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new ArrayList<>();

        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);  // 若是有向图则不需要这一行
    }

    public void dfs(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        Stack<Integer> stack = new Stack<>();
        stack.push(startVertex);

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

                for (int neighbor : adjList.get(vertex)) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}

public class DFS {
    public static void main(String[] args) {
        int numVertices = 7;
        Graph graph = new Graph(numVertices);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        System.out.println("Depth First Traversal (starting from vertex 0): ");
        graph.dfs(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

在这个示例中，我们使用了一个栈来保存待访问的节点。我们开始时将起始节点压入栈中，并标记它为已访问。然后，我们进入一个循环，直到栈为空。在每次循环中，我们从栈中弹出一个节点，并将其标记为已访问。然后，我们迭代该节点的邻居节点，如果邻居节点尚未被访问，则将其压入栈中。

在main方法中，我们创建一个示例图，并从节点0开始进行深度优先搜索。

深度优先搜索在解决一些问题时非常有用，例如查找图中的连通分量、检测图中的环、生成图的拓扑排序等。深度优先搜索的时间复杂度为O(V+E)，其中V是顶点数，E是边数。在最坏情况下，需要遍历图中的所有节点和边。