深度优先遍历

1import java.util.LinkedList;
2
3/**
4 * 采用邻接表的方式表示图
5 */
6class Graph {
7
8    /**
9     * 顶点的边
10     */
11    private final LinkedList<Integer>[] adjLists;
12    /**
13     * 顶点是否已经访问过
14     */
15    private final boolean[] visited;
16
17    /**
18     * @param vertices 顶点数量
19     */
20    @SuppressWarnings("unchecked")
21    public Graph(int vertices) {
22        adjLists = new LinkedList[vertices];
23        visited = new boolean[vertices];
24
25        for (int i = 0; i < vertices; i++) {
26            adjLists[i] = new LinkedList<>();
27        }
28    }
29
30    /**
31     * 添加一条边，因为是无向图，所以v1到v2和v2到v1都加上
32     *
33     * @param v1 顶点1
34     * @param v2 顶点2
35     */
36    void addEdge(int v1, int v2) {
37        adjLists[v1].add(v2);
38        adjLists[v2].add(v1);
39    }
40
41    /**
42     * 深度优先遍历
43     *
44     * @param vertex 顶点
45     */
46    void dfs(int vertex) {
47        /**
48         * 访问当前顶点
49         */
50        visited[vertex] = true;
51        System.out.println(vertex);
52
53        /**
54         * 遍历相邻的顶点
55         */
56        for (int adj : adjLists[vertex]) {
57            if (!visited[adj]) {
58                dfs(adj);
59            }
60        }
61    }
62}
63
64public class Main {
65
66    public static void main(String[] args) {
67        Graph g = new Graph(5);
68        g.addEdge(0, 1);
69        g.addEdge(1, 3);
70        g.addEdge(3, 4);
71        g.addEdge(0, 2);
72        /**
73         * 从顶点0开始遍历
74         */
75        g.dfs(0);
76    }
77}