431. Find the Connected Component in the Undirected Graph

Leave a comment

September 5, 2016 by oneOokay

BSF遍历每一个点。

visited map: Map<UndirectedGraphNode, Boolean>();

public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
Map<UndirectedGraphNode, Boolean> visited = new HashMap<>();
for (UndirectedGraphNode n : nodes) {
visited.put(n, false); //初始化,每个点visited = false
}

List<List<Integer>> result = new ArrayList<>();
for (UndirectedGraphNode n : nodes) {
if (visited.get(n) == false) { //已经visited过的点不需要再bfs了。
bfs(n, visited, result);}}
return result;}
//这一块BFS应该要非常熟悉,要闭着眼都得写出来啊=。=
private void bfs(UndirectedGraphNode node, Map<UndirectedGraphNode, Boolean> visited, List<List<Integer>> result){
List<Integer> row = new ArrayList<Integer>();
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
visited.put(node, true);
queue.offer(node);
while (!queue.isEmpty()){
UndirectedGraphNode n = queue.poll();
row.add(n.label);
for (UndirectedGraphNode neighbor : n.neighbors){
if (visited.get(neighbor) == false){
visited.put(neighbor, true);
queue.offer(neighbor);}}}
Collections.sort(row);
result.add(row);
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: