图的深度和广度遍历--java实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {

    public static void main(String[] args) {
        int vcount = 10;
        int[] vertices = new int[vcount];
        for (int i = 0; i < vcount; i++) {
            vertices[i] = i;
        }
        int[][] edges = new int[vcount][vcount];
        for (int i = 0; i < vcount; i++) {
            for (int j = 0; j < vcount; j++) {
                edges[i][j] = Integer.MAX_VALUE;
            }
        }

        edges[5][7] = 1;
        edges[5][3] = 1;
        edges[7][9] = 1;
        edges[7][1] = 1;
        edges[3][8] = 1;
        edges[1][4] = 1;
        edges[8][4] = 1;
        edges[4][6] = 1;
        edges[4][6] = 1;
        edges[4][2] = 1;
        edges[6][2] = 1;

        Graph graph = new Graph(vertices, edges);
        graph.dfs();
        graph.bfs();

    }

    static class Graph {
        int[] vertices;

        int[][] edges;

        int vcount;

        public Graph(int[] vertices, int[][] edges) {
            this.vertices = vertices;
            this.edges = edges;
            assert edges.length == vertices.length;
            vcount = vertices.length;
        }

        //获取顶点v的第一个邻居
        private int getFirstNeighbor(int v) {
            for (int i = 0; i < vcount; i++) {
                if (i != v && edges[v][i] != Integer.MAX_VALUE) {
                    return i;
                }
            }
            return -1;
        }

        //获取顶点v邻居的neighbor下一个邻居
        private int getNextNeighbor(int v, int neighbor) {
            for (int i = neighbor + 1; i < vcount; i++) {
                if (i != v && edges[v][i] != Integer.MAX_VALUE) {
                    return i;
                }
            }
            return -1;
        }

        //深度优先遍历
        public void dfs() {
            boolean[] visited = new boolean[vcount];
            List<Integer> visitPath = new ArrayList<>();
            for (int i = 0; i < vcount; i++) {
                if (!visited[i]) {
                    dfsInternal(visited, visitPath, i);
                }
            }

            System.out.println("---------dfs------------");
            visitPath.forEach(v -> {
                System.out.print(v + "\t");
            });
            System.out.println();

        }

        private void dfsInternal(boolean[] visited, List<Integer> visitPath, int v) {
            visited[v] = true;
            visitPath.add(vertices[v]);
            int neighbor = getFirstNeighbor(v);
            while (neighbor != -1) {
                if (!visited[neighbor]) {
                    dfsInternal(visited, visitPath, neighbor);
                }
                neighbor = getNextNeighbor(v, neighbor);
            }
        }

        //广度优先遍历
        public void bfs() {
            boolean[] visited = new boolean[vcount];
            List<Integer> visitPath = new ArrayList<>();
            for (int i = 0; i < vcount; i++) {
                if (!visited[i]) {
                    bfsInternal(visited, visitPath, i);
                }
            }
            System.out.println("---------bfs------------");
            visitPath.forEach(v -> {
                System.out.print(v + "\t");
            });
            System.out.println();
        }

        private void bfsInternal(boolean[] visited, List<Integer> visitPath, int firstV) {
            Queue<Integer> queue = new ArrayDeque<>();
            visited[firstV] = true;
            visitPath.add(firstV);
            queue.add(firstV);
            while (!queue.isEmpty()) {
                int v = queue.poll();
                int neighbor = getFirstNeighbor(v);
                while (neighbor != -1) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        visitPath.add(neighbor);
                        queue.add(neighbor);
                    }

                    neighbor = getNextNeighbor(v, neighbor);
                }

            }

        }
    }

}