Search Graph Nodes

Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can’t find.

There is a mapping store the nodes’ values in the given parameters.

Notice

It’s guaranteed there is only one available solution

Have you met this question in a real interview? Yes
Example
2——3 5
| |
| |
| |
| |
1 –4
Give a node 1, target is 50

there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50

Return node 4

这道题目基本上就是一个变形后的BFS，因此并不困难
java

/**
* Definition for graph node.
* class UndirectedGraphNode {
*
int label;
*
ArrayList<UndirectedGraphNode> neighbors;
*
UndirectedGraphNode(int x) {
*
label = x; neighbors = new ArrayList<UndirectedGraphNode>();
*
}
* };
*/
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: a node
*/
public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
Map<UndirectedGraphNode, Integer> values,
UndirectedGraphNode node,
int target) {
// write your code here
if (node == null) {
return null;
}
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
UndirectedGraphNode root = queue.poll();
if (values.get(root) == target) {
return root;
}
for (UndirectedGraphNode val : root.neighbors) {
queue.offer(val);
}
}
return null;
}
}

python

"""
Definition for a undirected graph node
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
"""
import Queue
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: a node
"""
def searchNode(self, graph, values, node, target):
# write your code here
if node is None:
return None
queue = Queue.Queue()
queue.put(node)
while not queue.empty():
root = queue.get()
if values[root] == target:
return root
for ele in root.neighbors:
queue.put(ele)
return None

最后

以上就是威武曲奇为你收集整理的Search Graph Nodes的全部内容，希望文章能够帮你解决Search Graph Nodes所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。