Keshawn_lu's Blog

Leetcode 1971. 寻找图中是否存在路径

深度优先搜索
字数统计: 458阅读时长: 2 min
2022/12/19 Share

题目简介：

有一个具有 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：

validpath-ex1

1
2
3
4
5
输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

提示：

  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 2 * 10^5
  • edges[i].length == 2
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= source, destination <= n - 1
  • 不存在重复边
  • 不存在指向顶点自身的边

思路：

首先根据edges构造图，然后进行深度优先搜索。

为了避免超时，设置两个策略：

  • 利用flag数组避免重复对一个顶点进行遍历
  • 在进行构造图时，只push_back存在的边即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:

    bool solve(int now_pos, int destination, 
                vector<vector<int>>& map, vector<int>& flag){

        if(now_pos == destination)
            return true;

        flag[now_pos] = 1;

        for(int i = 0; i < map[now_pos].size(); i++){

            if(flag[map[now_pos][i]] == 0){

                if(solve(map[now_pos][i], destination, map, flag))
                    return true;
            }
        }

        return false;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {

        vector<int> flag(n, 0);
        
        vector<vector<int>> map(n);

        for(auto& edge : edges){

            map[edge[0]].push_back(edge[1]);	//只push存在的边
            map[edge[1]].push_back(edge[0]);
        }

        return solve(source, destination, map, flag);
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网