leetcode原题：节点间通路-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode原题：节点间通路。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

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

示例：

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

解题思路：

本题借助队列，利用队列的先进先出的特点，保证访问每个节点的顺序不被破坏。

1.建立邻接表map，讲每个节点的可达节点保存在它自己的数组中，例如示例：map[0]={1,2}

2.创建访问数组，记录节点是否已经被访问过，防止一个节点多次被访问，出现死循环

3.创建一个队列qq，先在map中是否可以直接到达target，若没有，则将该节点可以到达的其他节点入队，继续找这些节点能到达的节点是否可以到达target

4.在找的过程中，只要找到了target，就说明存在路径，返回true

5.否则，返回false

源代码如下：文章来源地址https://www.toymoban.com/news/detail-647001.html

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        if(start==target) return true;
        //定义邻接表
        unordered_map<int,vector<int>> map;
        //遍历图，将图中两两节点之间的关系
        //eg.vec[0]={1,2}
        for(auto &vec:graph)
        {
            map[vec[0]].push_back(vec[1]);
        }
        //记录当前节点是否已经访问过，防止出现死循环
        vector<bool> vis(n,false);
        //通过队列使每个顶点能到达的前后顺序不被改变
        queue<int> qq;
        qq.push(start);//将start节点入队
        while(!qq.empty())
        {
            //保存对头元素
            int node=qq.front();
            qq.pop();
            //更新状态：已访问过
            vis[node]=true;
            //查找map，找到target，就说明可以到达
            for(auto point:map[node])
            {
                if(point==target) return true;
                //如果没有找到，需要判断节点是否访问过
                else if(vis[point]==false)
                {
                    //将当前节点入队
                    qq.push(point);//此时point节点相当于最终找到路径中的其中一个节点
                    //当前map[node]找完，没找到target
                    //如果队列不为空，说明路径还没有到达终点，继续找，此时就会找map[point]里的每个节点，直到找到队列为空，如果还没找到，说明不存在从start到target的路径
                }
            }
        }
        return false;
    }
};

到了这里，关于leetcode原题：节点间通路的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！