@w1024020103
2017-07-08T12:37:16.000000Z
字数 1175
阅读 566
LeetCode
LintCode
This problem is very similar to Clone Graph, we use Queue to assist traverse the graph, and use a HashSet to mark the nodes that have been visited.
We poll a node from the queue to traverse it, first we check if this node has mapped to the value of the target. Then we check its neighbors, if a neighbor has not been visited, we mark it visited and offer it to the queue to be waiting for traverse next time.
It's a very straightforward BFS template question.
public class Solution {
/**
* @param graph a list of Undirected graph node
* @param values a hash mapping, <UndirectedGraphNode, (int)value>
* @param node an Undirected graph node
* @param target an integer
* @return the a node
*/
public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
Map<UndirectedGraphNode, Integer> values,
UndirectedGraphNode node,
int target) {
if (node == null || graph == null) {
return null;
}
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
queue.offer(node);
visited.add(node);
while (!queue.isEmpty){
UndirectedGraphNode temp = queue.poll();
if (values.get(temp) == target){
return temp;
}
for (UndirectedGraphNode nei : temp.neighbors) {
if (!visited.contains(nei)){
queue.offer(nei);
visited.add(nei);
}
}
return null;
}
}
}