LeetCode_BFS_DFS_简单_1971.寻找图中是否存在路径

布满荆棘的人生 2023-10-07 22:15 2阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges\[i\] = \[ui, vi\] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由最多一条边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在有效路径，则返回 true，否则返回 false。

**示例 1：**  
![在这里插入图片描述][8c0810553ec840418ded18fecd1226c0.png]  
输入：n = 3, edges = \[\[0,1\],\[1,2\],\[2,0\]\], source = 0, destination = 2  
输出：true  
解释：存在由顶点 0 到顶点 2 的路径：

*  0 → 1 → 2
 *  0 → 2

**示例 2：**  
![在这里插入图片描述][13c4881cc2b74dc089b29ccbdac1de2b.png]  
输入：n = 6, edges = \[\[0,1\],\[0,2\],\[3,5\],\[5,4\],\[4,3\]\], source = 0, destination = 5  
输出：false  
解释：不存在由顶点 0 到顶点 5 的路径。

**提示：**  
1 <= n <= 2 \* 105  
0 <= edges.length <= 2 \* 105  
edges\[i\].length == 2  
0 <= ui, vi <= n - 1  
ui != vi  
0 <= source, destination <= n - 1  
不存在重复边  
不存在指向顶点自身的边

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-if-path-exists-in-graph

## 2.思路 ##

（1）BFS  
① 根据题目所给的数组 edges 来构造邻接表 adj；  
② 开始进行 BFS：  
1）从起点 source 开始按照层次依次来遍历每一层的节点，在遍历过程中使用队列来保存最近访问到的节点，同时使用数组 visited 来保存每个节点的访问状态（true 表示已经访问过了，false 则表示还没有访问到）；  
2）每次从队列中取出节点 v 时，将其它还未访问过的邻接节点加入到队列中；  
3）初始时将起点 source 存入队列，并且将其标记为已访问状态，在之后的遍历过程中，如果队列为空或者访问到终点 destination 时，直接退出遍历，此时直接返回终点 destination 的访问状态即可。

（2）DFS  
① 根据题目所给的数组 edges 来构造邻接表 adj；  
② 开始进行 DFS：  
1）从起点 source 开始遍历并进行深度搜索，在搜索的过程中每访问到一个节点 v，如果该节点就是终点 destination，那么直接返回 true；2）否则将其标记为已访问状态，并且继续递归访问与 v 相邻的下一个未访问节点 next，如果此时 next 与 destination 存在有效路径，那么说明起点 source 到终点 destination 之间也存在有效路径，此时直接返回 true 即可；  
3）当访问完所有邻接节点后仍然没有访问到 destination，则返回 false。

## 3.代码实现（Java） ##

//思路1————BFS
    public class Solution {
        
        public boolean validPath(int n, int[][] edges, int source, int destination) {
        
            //构造邻接表 adj
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) {
        
                adj[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
        
                int x = edge[0];
                int y = edge[1];
                adj[x].add(y);
                adj[y].add(x);
            }
            // visited 用于标记每个节点是否已经被访问过
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new ArrayDeque<>();
            //起点入队
            queue.offer(source);
            //标记起点
            visited[source] = true;
            while (!queue.isEmpty()) {
        
                int v = queue.poll();
                //已经遍历到终点，直接退出循环
                if (v == destination) {
        
                    break;
                }
                for (int next : adj[v]) {
        
                    while (!visited[next]) {
        
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
            return visited[destination];
        }
    }

//思路2————DFS
    public class Solution {
        
        public boolean validPath(int n, int[][] edges, int source, int destination) {
        
            //构造邻接表
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) {
        
                adj[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
        
                int x = edge[0];
                int y = edge[1];
                adj[x].add(y);
                adj[y].add(x);
            }
            // visited 用于标记每个节点是否已经被访问过
            boolean[] visited = new boolean[n];
            return dfs(source, destination, adj, visited);
        }
        
        //判断从起点 source 到终点 destination 是否存在有效路径，如果有则返回 true，否则返回 true
        private boolean dfs(int source, int destination, List<Integer>[] adj, boolean[] visited) {
        
            if (source == destination) {
        
                return true;
            } else {
        
                //标记当前访问到的节点
                visited[source] = true;
                for (int next : adj[source]) {
        
                    while (!visited[next] && dfs(next, destination, adj, visited)) {
        
                        return true;
                    }
                }
                return false;
            }
        }
    }

[8c0810553ec840418ded18fecd1226c0.png]: https://img-blog.csdnimg.cn/8c0810553ec840418ded18fecd1226c0.png
[13c4881cc2b74dc089b29ccbdac1de2b.png]: https://img-blog.csdnimg.cn/13c4881cc2b74dc089b29ccbdac1de2b.png