[关闭]
@w1024020103 2017-07-08T12:37:16.000000Z 字数 1175 阅读 566

Search Graph Node

LeetCode LintCode


image_1bkg73e7t1a4718hrj15k8mr29.png-112.6kB

image_1bkg742oa18a8f13ul2ug6nim.png-29kB

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.

  1. public class Solution {
  2. /**
  3. * @param graph a list of Undirected graph node
  4. * @param values a hash mapping, <UndirectedGraphNode, (int)value>
  5. * @param node an Undirected graph node
  6. * @param target an integer
  7. * @return the a node
  8. */
  9. public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
  10. Map<UndirectedGraphNode, Integer> values,
  11. UndirectedGraphNode node,
  12. int target) {
  13. if (node == null || graph == null) {
  14. return null;
  15. }
  16. Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
  17. HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
  18. queue.offer(node);
  19. visited.add(node);
  20. while (!queue.isEmpty){
  21. UndirectedGraphNode temp = queue.poll();
  22. if (values.get(temp) == target){
  23. return temp;
  24. }
  25. for (UndirectedGraphNode nei : temp.neighbors) {
  26. if (!visited.contains(nei)){
  27. queue.offer(nei);
  28. visited.add(nei);
  29. }
  30. }
  31. return null;
  32. }
  33. }
  34. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注