import java.util.ArrayList;

/**
 * 图
 */
public class ListGraph {

    ArrayList<ArrayList<Integer>> graphs;

    public static void main(String[] args) {
        // 构建图
        ListGraph graph = new ListGraph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        // 打印邻接表
        graph.print();
        // 图的遍历
        GraphTraversal traversal = new GraphTraversal(graph);
        traversal.DFS();
       // traversal.BFS();

    }

    /**
     * 初始化构造图
     */
    public ListGraph(int v) {
        graphs = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            graphs.add(new ArrayList<>());
        }
    }

    /**
     * 添加边
     */
    public void addEdge(int start, int end) {
        graphs.get(start).add(end);
    }

    /**
     * 移除边
     */
    public void removeEdge(int start, int end) {
        graphs.get(start).remove(end);
    }

    /**
     * 打印邻接表
     */
    public void print() {
        for (int i = 0; i < graphs.size(); i++) {
            System.out.print(i + " ");
            for (int j = 0; j < graphs.get(i).size(); j++) {
                System.out.print("->" + graphs.get(i).get(j));
            }
            System.out.println();
        }
    }
}

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 图的深度优先遍历（DFS）和广度优先遍历（BFS）
 */
public class GraphTraversal {
    /**
     * 图
     */
    ListGraph graph;
    /**
     * 是否被访问标志数组
     */
    boolean[] visited;

    /**
     * 初始化图，和访问标志数组
     */
    public GraphTraversal(ListGraph graph) {
        this.graph = graph;
        visited = new boolean[graph.graphs.size()];
    }

    public void DFS() {
        // 遍历每个节点
        for (int i = 0; i < graph.graphs.size(); i++) {
            if (!visited[i]) {
                DFSTraversal(i);
            }
        }
    }

    private void DFSTraversal(int i) {
        // 访问过直接返回
        if (visited[i]) {
            return;
        }
        // 标记已被访问过
        visited[i] = true;
        System.out.print(i + " -> ");
        // 遍历邻接节点，再递归
        for (Integer neighbor : graph.graphs.get(i)) {
            if (!visited[neighbor]) {
                DFSTraversal(neighbor);
            }
        }
    }

    public void BFS() {
        // 遍历每个节点
        for (int i = 0; i < graph.graphs.size(); i++) {
            if (!visited[i]) {
                BSFTraversal(i);
            }
        }
    }

    private void BSFTraversal(int i) {
        // 队列存放需要遍历的节点
        Queue<Integer> queue = new ArrayDeque<>();
        visited[i] = true;
        queue.add(i);
        while (!queue.isEmpty()) {
            // 当前节点
            Integer current = queue.poll();
            System.out.print(current + " -> ");
            // 获取当前节点的邻接节点
            for (Integer neighbor : graph.graphs.get(current)) {
                // 没有访问过
                if (!visited[neighbor]) {
                    // 设置已访问，并加入待遍历的队列中
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }


}