代码

public class Graph {
    // 邻接链表
    private LinkList<Integer>[] adj;
    // 顶点数量
    private int vertexSize;
    // 边的数量
    private int edgeSize;
    // 记录顶点是否被访问过
    private boolean[] visited;

    public Graph(int vertexSize) {
        this.vertexSize = vertexSize;
        this.adj = new LinkList[vertexSize];
        this.visited = new boolean[vertexSize];
    }

    /**
     * 添加一条连接v1和v2的边
     *
     * @param v1
     * @param v2
     */
    public void addEdge(int v1, int v2) {
        if (adj[v1] == null) {
            adj[v1] = new LinkList();
        }
        if (adj[v2] == null) {
            adj[v2] = new LinkList();
        }
        adj[v1].insert(v2);
        adj[v2].insert(v1);
        edgeSize++;
    }


    /**
     * 查询和顶点v直接相连的顶点
     *
     * @param v
     * @return
     */
    public LinkList<Integer> adj(int v) {
        return adj[v];
    }

    /**
     * 深度优先搜索
     *
     * @param v
     * @return
     */
    public void dsf(int v) {
        resetVisited();
        dsfVisit(v);
    }

    private void dsfVisit(int v) {
        System.out.printf(" %d", v);
        visited[v] = true;
        for (Integer n : adj[v]) {
            if (!visited[n]) {
                dsfVisit(n);
            }
        }
    }

    private Queue<Integer> bfsQueue = new ConcurrentLinkedQueue();

    /**
     * 广度优先搜索
     *
     * @param v
     * @return
     */
    public void bfs(int v) {
        resetVisited();
        bfsVisit(v);
    }

    private void bfsVisit(int v) {
        System.out.printf(" %d", v);
        visited[v] = true;
        for (Integer n : adj[v]) {
            if (!visited[n]) {
                visited[n] = true;
                bfsQueue.offer(n);
            }
        }
        if (!bfsQueue.isEmpty()) {
            bfsVisit(bfsQueue.poll());
        }
    }

    /**
     * 重置visited数据
     */
    public void resetVisited() {
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
    }

    /**
     * 查询顶点是否被访问过
     */
    public boolean[] visited() {
        return visited;
    }

    /**
     * 查询某个顶点是否被访问过
     */
    public boolean visited(int v) {
        return visited[v];
    }

    /**
     * 图中顶点的数量
     */
    public int vertexSize() {
        return vertexSize;
    }

    /**
     * 图中边的数量
     */
    public int edgeSize() {
        return edgeSize;
    }
}

测试

    public static void main(String[] args) {
        Graph graph = new Graph(10);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 3);

        graph.addEdge(1, 0);
        graph.addEdge(1, 4);

        graph.addEdge(2, 0);
        graph.addEdge(2, 6);
        graph.addEdge(2, 7);

        graph.addEdge(3, 0);
        graph.addEdge(3, 5);

        graph.addEdge(4, 1);
        graph.addEdge(4, 5);

        graph.addEdge(5, 4);
        graph.addEdge(5, 3);

        graph.addEdge(6, 2);
        graph.addEdge(7, 2);

        int start = 0;

        System.out.print("深度优先搜索：");
        graph.dsf(start);
        System.out.println();

        System.out.printf("顶点 %d 与顶点 %d 是否相通：%b\n", start, 5, graph.visited(5));
        System.out.printf("顶点 %d 与顶点 %d 是否相通：%b\n", start, 9, graph.visited(9));

        System.out.print("广度优先搜索：");
        graph.bfs(start);
        System.out.println();

        System.out.printf("顶点 %d 与顶点 %d 是否相通：%b\n", start, 5, graph.visited(5));
        System.out.printf("顶点 %d 与顶点 %d 是否相通：%b\n", start, 9, graph.visited(9));
    }

输出结果：

深度优先搜索： 0 1 4 5 3 2 6 7
顶点 0 与顶点 5 是否相通：true
顶点 0 与顶点 9 是否相通：false
广度优先搜索： 0 1 2 3 4 6 7 5
顶点 0 与顶点 5 是否相通：true
顶点 0 与顶点 9 是否相通：false