Search Graph Nodes

• Lintcode : 618 / Leetcode :
• Level : Medium

Problem

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.

Example
Example 1:

Input:
{1,2,3,4#2,1,3#3,1,2#4,1,5#5,4}
[3,4,5,50,50]
1
50
Output:
4
Explanation:
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
Example 2:

Input:
{1,2#2,1}
[0,1]
1
1
Output:
2
Notice
It's guaranteed there is only one available solution

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(nodes * avg edges)
space: O(n)

Answer

/**
 * Definition for Undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
     UndirectedGraphNode* searchNode(vector<UndirectedGraphNode*>& graph,
                                    map<UndirectedGraphNode*, int>& values,
                                    UndirectedGraphNode* node,
                                    int target) {
                                        if (node == nullptr) return nullptr;
                                        queue<UndirectedGraphNode*> q;
                                        q.push(node);
                                        set<UndirectedGraphNode*> repeat;
                                        while (!q.empty()) {
                                            UndirectedGraphNode* n = q.front(); q.pop();
                                                if (values[n] == target) return n;
                                                for (auto j : n -> neighbors) {
                                                    if (repeat.find(j) != repeat.end()) continue;
                                                    q.push(j);
                                                    repeat.insert(j);
                                                }
                                        }
                                        return nullptr;
    }
};

tags: BFS

​