531. Six Degrees

Leave a comment

September 5, 2016 by oneOokay

531 好数字!

  • 需要的是BFS,用queue。
  • 主要是如何处理已经访问过的节点的问题,这里用一个HashMap来存node和step数,同时也能够排除已经访问过的节点。

/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) {
* label = x;
* neighbors = new ArrayList<UndirectedGraphNode>();
* }
* };
*/
public class Solution {
/**
* @param graph a list of Undirected graph node
* @param s, t two Undirected graph nodes
* @return an integer
*/
public int sixDegrees(List<UndirectedGraphNode> graph,
UndirectedGraphNode s,
UndirectedGraphNode t) {
if (s == t) {
return 0;
}
// Write your code here
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
Map<UndirectedGraphNode, Integer> visited = new HashMap<UndirectedGraphNode, Integer>();
queue.offer(s); //直接把s放到queue里面去,而不需要从List里面找。
visited.put(s, 0); //s点为起点,所以step数为0
while (!queue.isEmpty()){
UndirectedGraphNode node = queue.poll();
int step = visited.get(node); //得到从起点走到当前点的step数
for (UndirectedGraphNode neighbor : node.neighbors) {
if (visited.containsKey(neighbor)){ //如果visited中已经存在该数说明已经visited过了,没必要再找它的neighbors。
continue;
}
visited.put(neighbor, step + 1); //把它的neighbors存入,同时step + 1.
queue.offer(neighbor);
if (neighbor == t) {
return step + 1;
}}}
return -1;
}}

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: