Leetcode 图_面试题 04.01. 节点间通路

今天药忘吃喽~ 2023-02-09 05:29 12阅读 0赞

### Leetcode 图\_面试题 04.01. 节点间通路 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

题目链接：[https://leetcode-cn.com/problems/route-between-nodes-lcci/submissions/][https_leetcode-cn.com_problems_route-between-nodes-lcci_submissions]  
  本质上就是一个图的遍历问题，这里需要将原来的`graph`数组变成邻接表，接着遍历该邻接表，如果遍历到`target`节点即返回，同时设置已经遍历过的节点`vis`为`true`，表示已经访问过了。代码我已经进行了详细的注释，理解应该没有问题。

# 2、问题解决 #

笔者以`C++`方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "set"
    
    
    class Solution { 
    private:
    	// 设置最大的节点数
    	const static int MAXV = 100001;
    	// 定义邻接 set ,注意这里没有使用 vector 因为题目中有重复的边
    	// 但是使用 vector 也是去遍历，所以使用 set 也没有影响
    	set<int> Adj[MAXV];
    	// 标记某个节点是否已经访问过
    	bool vis[MAXV] = {  false };
    	// 找到节点就快速退出，类似于剪枝
    	int flag = 0;
    public:
    	bool findWhetherExistsPath(int n, vector<vector<int>> &graph, int start, int target) { 
    		init(graph);
    		dfs(start, target);
    		return vis[target];
    	}
    
    	/** * 初始化邻接表 将题目中的二维数组转化成邻接表 * @param graph */
    	void init(const vector<vector<int>> &graph) { 
    		for (int i = 0; i < graph.size(); ++i) { 
    			// graph 中的元素类似于 [0,1], 这里使得 1 存储到 0 的邻接矩阵中
    			Adj[graph[i][0]].insert(graph[i][1]);
    		}
    	}
    
    	// 深搜遍历
    	void dfs(int u, int target) { 
    		// 找到对应的节点，快速退出
    		if (u == target) { 
    			// 设置该节点已经访问过，即可以到达
    			vis[target] = true;
    			// 快速退出标志
    			flag = 1;
    			return;
    		}
    		// 设置该节点已经访问过，即可以到达
    		vis[u] = true;
    
    		//遍历邻接矩阵 即 set 集和
    		for (auto it = Adj[u].begin(); it != Adj[u].end(); it++) { 
    			if (flag == 1) { 
    				return;
    			}
    			int v = *it;
    			if (!vis[v]) { 
    				dfs(v, target);
    			}
    		}
    
    	}
    
    };
    
    
    int main() { 
    	// vector<vector<int>> graph = { {0, 1},
    	// {0, 2},
    	// {1, 2},
    	// {1, 2}};
    
    	vector<vector<int>> graph = {  {  0, 1 },
    	{  0, 2 },
    	{  0, 4 },
    	{  0, 4 },
    	{  0, 1 },
    	{  1, 3 },
    	{  1, 4 },
    	{  1, 3 },
    	{  2, 3 },
    	{  3, 4 } };
    
    
    	Solution *pSolution =
    		new Solution;
    
    	bool b = pSolution->findWhetherExistsPath(3, graph, 0, 2);
    	cout << b << endl;
    	system("pause");
    	return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]  
有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[https_leetcode-cn.com_problems_route-between-nodes-lcci_submissions]: https://leetcode-cn.com/problems/route-between-nodes-lcci/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200518145916433.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70