广度优先遍历

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