节点间通路
题目描述 算法思想
这是一道典型的求图中简单路径的问题，这里利用广度优先搜索是相对简单直接的。
1、首先建图，也就是创建一个二维数组，行号即为起点，每一列的元素代表终点。并且也创建一个访问列表，用以存储顶点是否被访问。
2、然后，利用队列，基于广度优先的思想，依次访问起点所可以到达的顶点，并且加入队列，如果在搜索过程中，可以到达终点，则返回True。
3、如果，搜索结束依然没有找到，则返回Fasle。
深度优先搜索也比较简单，在最后分享一个别人的做法。
代码实现
广度优先搜索
class Solution: def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool: tag = [[] for _ in range(n)] for i, j in graph: tag[i].append(j) visit = [0] * n que = [start] while que: cur_node = que.pop() if target in tag[cur_node]: return True for node in tag[cur_node]: if visit[node] == 0: que.insert(0,node) visit[cur_node] == 1 return False深度优先搜索
class Solution: def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool: gra = defaultdict(set) for key, value in graph: gra[key].add(value) def dfs(start, target, visited): if start == target: return True if visited[start]: return False visited[start] = True judge = False if start in gra: for cur in gra[start]: judge = judge or dfs(cur, target, visited) return judge visited = [False] * n return dfs(start, target, visited)作者：821218213 链接：https://leetcode-cn.com/problems/route-between-nodes-lcci/solution/mian-shi-ti-0401-python3-zi-dian-jian-tu-dfs-by-82/ 来源：力扣（LeetCode）
