leetcode 链接：节点间通路

题目

给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例：

  1.  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
  2.  输出：true
 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 输出 true

解答 & 代码

  • 先用哈希表存储 pair<节点编号, 该节点的邻居们的编号数组>，方便之后的搜索（否则之后搜索每个节点的子节点都要遍历一遍二维数组 graph）

  • 借助队列实现广度优先搜索

    • 如果遍历到 target 节点，说明 start 和 target 之间存在通路

    • 如果遍历结束（即队列为空），说明 start 和 target 之间不存在通路

      class Solution {
public:
bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
   // 先将 <节点编号, 该节点的邻居们的编号数组> 存储到哈希表
   unordered_map<int, vector<int>> nodeMap;
   for(int i = 0; i < graph.size(); ++i)
   {
       if(nodeMap.find(graph[i][0]) == nodeMap.end())
       {
           vector<int> children(1, graph[i][1]);
           nodeMap.insert(make_pair(graph[i][0], children));
       }
       else
       {
           nodeMap[graph[i][0]].push_back(graph[i][1]);
       }
   }

   // 借助队列实现广度优先搜索
   queue<int> nodeQ;
   nodeQ.push(start);
   while(!nodeQ.empty())
   {
       int cur = nodeQ.front();
       nodeQ.pop();
       if(nodeMap.find(cur) != nodeMap.end())
       {
           for(int i = 0; i < nodeMap[cur].size(); ++i)
           {
               if(nodeMap[cur][i] == target)
                   return true;
               nodeQ.push(nodeMap[cur][i]);
           }
       }
   }

   return false;
}
};

      执行结果： ``` 执行结果：通过

执行用时：324 ms, 在所有 C++ 提交中击败了 37.44% 的用户 内存消耗：75 MB, 在所有 C++ 提交中击败了 43.03% 的用户 ```