📈 寻找图中是否存在路径

📝 题目描述

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

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

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

📋 代码模板

java

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {

    }
}

typescript

function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
    
}

💡 提示

1. $1<=n<=2\ast {10}^5$
2. $0<=edges.length<=2\ast {10}^5$
3. $edges[i].length==2$
4. $0<=u_i<=n-1$
5. $0<=v_i<=n-1$
6. $u_i!=v_i$
7. $0<=source<=n-1$
8. $0<=destination<=n-1$
9. 不存在重复边
10. 不存在指向顶点自身的边

🚀 示例

🖊️ 题解

DFS

可惜没有如果

java

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj.get(x).add(y);
            adj.get(y).add(x);
        }
        boolean[] visited = new boolean[n];
        return dfs(adj, visited, destination, source);
    }

    private boolean dfs(List<List<Integer>> adj, boolean[] visited, int destination, int i) {
        if (i == destination) {
            return true;
        }
        if (visited[i]) {
            return false;
        }
        visited[i] = true;
        for (int next : adj.get(i)) {
            if (dfs(adj, visited, destination, next)) {
                return true;
            }
        }
        return false;
    }
}

typescript

function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (const edge of edges) {
        const x = edge[0], y = edge[1];
        adj[x].push(y);
        adj[y].push(x);
    }
    const visited: boolean[] = Array(n).fill(false);
    return dfs(adj, visited, destination, source);
}

function dfs(adj: number[][], visited: boolean[], destination: number, i: number): boolean {
    if (i == destination) {
        return true;
    }
    if (visited[i]) {
        return false;
    }
    visited[i] = true;
    for (const next of adj[i]) {
        if (dfs(adj, visited, destination, next)) {
            return true;
        }
    }
    return false;
}

BFS

可惜没有固若

java

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            adj.get(x).add(y);
            adj.get(y).add(x);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        visited[source] = true;
        while (!queue.isEmpty()) {
            int i = queue.poll();
            if (i == destination) {
                return true;
            }
            for (Integer next : adj.get(i)) {
                if (visited[next]) {
                    continue;
                }
                queue.offer(next);
                visited[next] = true;
            }
        }
        return false;
    }
}

typescript

function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (const edge of edges) {
        const x = edge[0], y = edge[1];
        adj[x].push(y);
        adj[y].push(x);
    }
    const visited: boolean[] = Array(n).fill(false);
    const queue: number[] = [];
    queue.push(source);
    visited[source] = true;
    while (queue.length > 0) {
        const i: number = queue.shift()!;
        if (i == destination) {
            return true;
        }
        for (const next of adj[i]) {
            if (visited[next]) {
                continue;
            }
            queue.push(next);
            visited[next] = true;
        }
    }
    return false;
}

💭 复杂度分析