图的连通性判断

用Java实现了一个图的连通性判断，主要是用了广度优先遍历BFS来实现的。

算法思想

判断图是否是连通的，可以通过深度优先遍历的方法判断。 具体实现为：在图中选定任一一个顶点，对该顶点进行深度优先遍历，如果在这个遍历过程中所有的顶点都被遍历到，则该图为连通；反之，若存在没有被遍历到的顶点，则说明该图是非连通的。

public boolean isConnected() {
        int vertices = this.vertices;
        LinkedList<Integer>[] adjList = this.adjList;
        boolean[] visited = new boolean[vertices];

        // start the DFS from 0
        dfs(0, adjList, visited);

        // check if all the vertices are visited,if yes and then graph is connected
        int count = 0;
        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) {
                count++;
            }
        }

        if (vertices == count) {
            System.out.println("Given graph is connected!");
            return true;
        } else {
            System.out.println("Given graph is not connected!");
            return false;
        }
    }

深度优先遍历

public void dfs(int source, LinkedList<Integer>[] adjList, boolean[] visited) {
        // mark the vertex visited
        visited[source] = true;

        //travel the neighbour
        for (int i = 0; i < adjList[source].size(); i++) {
            int neighbour = adjList[source].get(i);
            if (visited[neighbour] == false) {// if neighbour hasn't been visited
                //make recursive call from neighbor
                dfs(neighbour, adjList, visited);
            }
        }
    }

无向连通图的判断有多种方法，除了BFS，还可以用DFS、Union-find、Warshell、Tarjan等方法判断。
(完)