找出无向图汇总的相连要素find-the-connected-component-in-the-undirected-graph

请找出无向图中相连要素的个数。

图中的每个节点包含其邻居的 1 个标签和 1 个列表。（一个无向图的相连节点（或节点）是一个子图，其中任意两个顶点通过路径相连，且不与超级图中的其它顶点相连。）

样例

给定图:

A------B  C
      |  | 
      |  |
      |  |
      |  |
      D   E

返回 {A,B,D}, {C,E}。其中有 2 个相连的元素，即{A,B,D}, {C,E}

思路：说实话，lintcode的翻译我并没有看懂是啥意思，当然更不知道怎么做。准确的说，这个问题应该叫做在无向图中找各极大连通子图，使用的算法是广度优先搜索。此处附上广度优先搜索和深度优先搜索算法的比较，顺带复习一下；

http://blog.csdn.net/andyelvis/article/details/1728378

当然代码也是我学习他人的，来源附上http://www.jiuzhang.com/solutions/find-the-connected-component-in-the-undirected-graph/

 1 /**
 2  * Definition for Undirected graph.
 3  * class UndirectedGraphNode {
 4  *     int label;
 5  *     ArrayList<UndirectedGraphNode> neighbors;
 6  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 7  * };
 8  */
 9 public class Solution {
10     /**
11      * @param nodes a array of Undirected graph node
12      * @return a connected set of a Undirected graph
13      */
14     public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
15         // Write your code here
16         int m = nodes.size();
17         Map<UndirectedGraphNode,Boolean> visited = new HashMap<>();
18         for(UndirectedGraphNode node:nodes){
19             visited.put(node,false);
20         }
21         List<List<Integer>> result = new ArrayList<>();
22         for(UndirectedGraphNode node:nodes){
23             if(visited.get(node) == false){
24                 bfs(node,visited,result);
25             }
26         }
27         return result;
28     }
29     public void bfs(UndirectedGraphNode node,Map<UndirectedGraphNode,Boolean> visited,List<List<Integer>> result){
30         List<Integer> row = new ArrayList<>();
31         Queue<UndirectedGraphNode> queue = new LinkedList<>();
32         visited.put(node,true);
33         queue.offer(node);
34         while(!queue.isEmpty()){
35             UndirectedGraphNode u = queue.poll();
36             row.add(u.label);
37             for(UndirectedGraphNode v:u.neighbors){
38                 if(visited.get(v)==false){
39                     visited.put(v,true);
40                     queue.offer(v);
41                 }
42             }
43         }
44         Collections.sort(row);
45         result.add(row);
46     }
47 }