搜索题目：寻找图中是否存在路径

文章目录题目标题和出处难度题目描述要求示例数据范围前言解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析解法三预备知识思路和算法代码复杂度分析题目标题和出处标题寻找图中是否存在路径出处1971. 寻找图中是否存在路径难度3 级题目描述要求有一个包含n \texttt{n}n个顶点的双向图其中每个顶点标记从0 \texttt{0}0到n − 1 \texttt{n} - \texttt{1}n−1。图中的边用一个二维整数数组edges \texttt{edges}edges表示其中edges[i] [u i , v i ] \texttt{edges[i] [u}_\texttt{i}\texttt{, v}_\texttt{i}\texttt{]}edges[i] [ui​, vi​]表示顶点u i \texttt{u}_\texttt{i}ui​和顶点v i \texttt{v}_\texttt{i}vi​之间的双向边。每个顶点对由最多一条边连接并且没有顶点存在指向顶点自身的边。需要判断是否存在从顶点source \texttt{source}source到顶点destination \texttt{destination}destination的有效路径。给定数组edges \texttt{edges}edges和整数n \texttt{n}n、source \texttt{source}source和destination \texttt{destination}destination如果存在从source \texttt{source}source到destination \texttt{destination}destination的有效路径则返回true \texttt{true}true否则返回false \texttt{false}false。示例示例 1输入n 3, edges [[0,1],[1,2],[2,0]], source 0, destination 2 \texttt{n 3, edges [[0,1],[1,2],[2,0]], source 0, destination 2}n 3, edges [[0,1],[1,2],[2,0]], source 0, destination 2输出true \texttt{true}true解释存在由顶点0 \texttt{0}0到顶点2 \texttt{2}2的路径0 → 1 → 2 \texttt{0} \rightarrow \texttt{1} \rightarrow \texttt{2}0→1→20 → 2 \texttt{0} \rightarrow \texttt{2}0→2示例 2输入n 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5 \texttt{n 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5}n 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5输出false \texttt{false}false解释不存在由顶点0 \texttt{0}0到顶点5 \texttt{5}5的路径。数据范围1 ≤ n ≤ 2 × 10 5 \texttt{1} \le \texttt{n} \le \texttt{2} \times \texttt{10}^\texttt{5}1≤n≤2×1050 ≤ edges.length ≤ 2 × 10 5 \texttt{0} \le \texttt{edges.length} \le \texttt{2} \times \texttt{10}^\texttt{5}0≤edges.length≤2×105edges[i].length 2 \texttt{edges[i].length} \texttt{2}edges[i].length20 ≤ u i , v i ≤ n − 1 \texttt{0} \le \texttt{u}_\texttt{i}\texttt{, v}_\texttt{i} \le \texttt{n} - \texttt{1}0≤ui​, vi​≤n−1u i ≠ v i \texttt{u}_\texttt{i} \ne \texttt{v}_\texttt{i}ui​vi​0 ≤ source, destination ≤ n − 1 \texttt{0} \le \texttt{source, destination} \le \texttt{n} - \texttt{1}0≤source, destination≤n−1不存在重复边不存在指向顶点自身的边前言由于给定的图是双向图每条边都是双向边因此对于同一条边连接的两个顶点可以从其中任意一个顶点到达另一个顶点。判断是否存在从顶点source \textit{source}source到顶点destination \textit{destination}destination的有效路径等价于判断顶点source \textit{source}source和顶点destination \textit{destination}destination是否连通。连通性问题可以使用广度优先搜索或深度优先搜索解决也可以使用并查集解决。解法一思路和算法使用广度优先搜索判断是否存在从顶点source \textit{source}source到顶点destination \textit{destination}destination的有效路径需要从顶点source \textit{source}source开始依次遍历每一层的顶点判断是否可以到达顶点destination \textit{destination}destination。由于题目中的图的表示方式是边数组为了方便处理需要首先将边数组转换成邻接顶点列表的形式转换后可以在O ( 1 ) O(1)O(1)时间获得一个顶点的全部相邻顶点然后使用广度优先搜索遍历图。广度优先搜索需要使用哈希表或数组记录每个顶点的访问状态使用队列存储最近访问过的顶点。初始时将顶点source \textit{source}source设为已访问并将其入队列。每次将一个顶点vertex \textit{vertex}vertex出队列对于每个与vertex \textit{vertex}vertex相邻且未访问的顶点next \textit{next}next将next \textit{next}next设为已访问并将其入队列。当队列为空或访问到顶点destination \textit{destination}destination时遍历结束将顶点destination \textit{destination}destination的访问状态返回。代码classSolution{publicbooleanvalidPath(intn,int[][]edges,intsource,intdestination){ListInteger[]adjacentArrnewList[n];for(inti0;in;i){adjacentArr[i]newArrayListInteger();}for(int[]edge:edges){adjacentArr[edge[0]].add(edge[1]);adjacentArr[edge[1]].add(edge[0]);}boolean[]visitednewboolean[n];visited[source]true;QueueIntegerqueuenewArrayDequeInteger();queue.offer(source);while(!queue.isEmpty()!visited[destination]){intvertexqueue.poll();ListIntegeradjacentadjacentArr[vertex];for(intnext:adjacent){if(!visited[next]){visited[next]true;queue.offer(next);}}}returnvisited[destination];}}复杂度分析时间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的顶点数m mm是图中的边数。广度优先搜索的时间复杂度由顶点数和边数决定。空间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的顶点数m mm是图中的边数。空间复杂度主要取决于邻接顶点列表、记录每个顶点访问状态的数组和队列邻接顶点列表需要O ( n m ) O(n m)O(nm)的空间记录每个顶点访问状态的数组和队列需要O ( n ) O(n)O(n)的空间。解法二思路和算法使用深度优先搜索判断是否存在从顶点source \textit{source}source到顶点destination \textit{destination}destination的有效路径需要从顶点source \textit{source}source开始依次遍历每一条路径判断是否可以到达顶点destination \textit{destination}destination。由于题目中的图的表示方式是边数组为了方便处理需要首先将边数组转换成邻接顶点列表的形式转换后可以在O ( 1 ) O(1)O(1)时间获得一个顶点的全部相邻顶点然后使用深度优先搜索遍历图。深度优先搜索需要使用哈希表或数组记录每个顶点的访问状态。从顶点source \textit{source}source开始遍历。每次访问一个顶点vertex \textit{vertex}vertex时将该顶点设为已访问对于每个与vertex \textit{vertex}vertex相邻且未访问的顶点next \textit{next}next递归地访问next \textit{next}next。当没有更多顶点可以访问或访问到顶点destination \textit{destination}destination时遍历结束将顶点destination \textit{destination}destination的访问状态返回。代码classSolution{ListInteger[]adjacentArr;boolean[]visited;publicbooleanvalidPath(intn,int[][]edges,intsource,intdestination){adjacentArrnewList[n];for(inti0;in;i){adjacentArr[i]newArrayListInteger();}for(int[]edge:edges){adjacentArr[edge[0]].add(edge[1]);adjacentArr[edge[1]].add(edge[0]);}visitednewboolean[n];returndfs(source,destination);}publicbooleandfs(intvertex,intdestination){visited[vertex]true;if(!visited[destination]){ListIntegeradjacentadjacentArr[vertex];for(intnext:adjacent){if(!visited[next]dfs(next,destination)){returntrue;}}}returnvisited[destination];}}复杂度分析时间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的顶点数m mm是图中的边数。深度优先搜索的时间复杂度由顶点数和边数决定。空间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的顶点数m mm是图中的边数。空间复杂度主要取决于邻接顶点列表、记录每个顶点访问状态的数组和递归调用栈邻接顶点列表需要O ( n m ) O(n m)O(nm)的空间记录每个顶点访问状态的数组和递归调用栈需要O ( n ) O(n)O(n)的空间。解法三预备知识该解法涉及到并查集。并查集是一种树型的数据结构用于处理不相交集合的合并与查询问题。思路和算法这道题要求判断顶点source \textit{source}source和顶点destination \textit{destination}destination是否连通连通性问题可以使用并查集解决。并查集初始化时n nn个顶点分别属于n nn个不同的集合每个集合只包含一个顶点。初始化之后遍历每条边将同一条边连接的两个顶点所在的集合做合并。遍历所有的边之后判断顶点source \textit{source}source和顶点destination \textit{destination}destination所在的集合是否相同如果两个顶点所在的集合相同则两个顶点连通如果两个顶点所在的集合不同则两个顶点不连通。代码classSolution{publicbooleanvalidPath(intn,int[][]edges,intsource,intdestination){UnionFindufnewUnionFind(n);for(int[]edge:edges){uf.union(edge[0],edge[1]);if(uf.find(source)uf.find(destination)){returntrue;}}returnuf.find(source)uf.find(destination);}}classUnionFind{privateint[]parent;privateint[]rank;publicUnionFind(intn){parentnewint[n];for(inti0;in;i){parent[i]i;}ranknewint[n];}publicvoidunion(intx,inty){introotxfind(x);introotyfind(y);if(rootx!rooty){if(rank[rootx]rank[rooty]){parent[rooty]rootx;}elseif(rank[rootx]rank[rooty]){parent[rootx]rooty;}else{parent[rooty]rootx;rank[rootx];}}}publicintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}}复杂度分析时间复杂度O ( n m × α ( n ) ) O(n m \times \alpha(n))O(nm×α(n))其中n nn是图中的顶点数m mm是图中的边数α \alphaα是反阿克曼函数。并查集的初始化需要O ( n ) O(n)O(n)的时间然后遍历m mm条边执行m mm次合并操作最后对source \textit{source}source和destination \textit{destination}destination分别执行查询操作这里的并查集使用了路径压缩和按秩合并单次操作的时间复杂度是O ( α ( n ) ) O(\alpha(n))O(α(n))因此并查集初始化之后的操作的时间复杂度是O ( m × α ( n ) ) O(m \times \alpha(n))O(m×α(n))总时间复杂度是O ( n m × α ( n ) ) O(n m \times \alpha(n))O(nm×α(n))。空间复杂度O ( n ) O(n)O(n)其中n nn是图中的顶点数。并查集需要O ( n ) O(n)O(n)的空间。