Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

LeetCode- The path between nodes

Path between nodes. Given a directed graph, design an algorithm to find out whether there is a path between two nodes.

Example 1:

Input: n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2

Output: true,

Example 2:

Input: n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4

The output of true

Tip:

The number of nodes n is in the range [0, 1E5].

The node id is greater than or equal to 0 and less than N.

There may be self loops and parallel edges in the graph.

Ii. Analysis of Ideas:

Idea 1: First set the access state array

Use DFS depth-first search for recursive search

Gradually compress the search range until the start and target are found in the same path, indicating that the search succeeds

When there is a closed loop, there will be an infinite loop, and the path taken must be marked in each recursive process.

When the positive order recursive search, there will be a timeout situation, so use the reverse order search method to solve.

Idea 2:

Build the Map < Integer, List >

Perform depth-first traversal

Check whether the current node has a path node in the map

Use HashSet to keep track of nodes that have been visited.

Iii. AC Code:

Idea 1:

    class AnimalShelf {
        private boolean[] visitArray = null;

        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            this.visitArray = new boolean[graph.length];
            return helpful(graph, start, target);
        }

        private boolean helpful(int[][] graph, int start, int target) {
            for (int i = 0; i < graph.length; ++i) {
                if(! visitArray[i]) {if (graph[i][0] == start && graph[i][1] == target) return true;
                    visitArray[i] = true;
                    if (graph[i][1] == target && helpful(graph, start, graph[i][0])) return true;
                    visitArray[i] = false; }}return false; }}Copy the code

Idea 2:


    class Solution {
        Set<Integer> visitSet = new HashSet<>();

        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            Map<Integer, List<Integer>> tempMap = new HashMap<>();
            for (int[] a : graph) {
                tempMap.computeIfAbsent(a[0], o -> new ArrayList<>()).add(a[1]);
            }
            if (start == target) {
                return true;
            }
            if(! tempMap.containsKey(start)) {return false;
            }
            return DFS(start, target, tempMap);

        }

        public boolean DFS(int current, int target, Map<Integer, List<Integer>> midMap) {
            if (current == target) {
                return true;
            }
            if(! midMap.containsKey(current)) {return false;
            }
            visitSet.add(current);
            for (int val : midMap.get(current)) {
                if(! visitSet.contains(val)) {if (DFS(val, target, midMap)) {
                        return true; }}}return false; }}Copy the code