The traversal of graphs is mainly investigated. On the basis of fully understanding the meaning of the question, if there is a certain knowledge reserve and the accumulation of questions, it is not difficult to have ideas. Then you write the code and debug it carefully.

“Force button” Question 802: Find the final safety state (medium)

In a directed graph, we start at a certain node and at each turning point and go along the directed edge of the graph. If the node we reach is the end point (that is, it has no directed edge), we stop.

Now, if we make it to the end, then our starting point is ultimately safe. More specifically, there is a natural number K, and no matter where we choose to start walking, we can stop at an end before K steps.

Which nodes are ultimately safe? The result is an ordered array.

The directed graph has N nodes, labeled 0, 1… N minus 1, where N is the number of nodes of the graph. Graph [I] is a list of nodes j, such that (I, j) is a directed edge of the graph.

Example: the input: graph = [[1, 2], [2, 3], [5], [0], [5], [], []] output: [2, 4, 5, 6] here is the schematic diagram above.Copy the code

Tip:

  • n == graph.length

  • 1 Or less n Or less 1 0 4 1 \le n \le 10^4

  • 0 Or less g r a p h [ i ] . l e n g t h Or less n 0 \le graph[i].length \le n
  • graph[i]In strict ascending order.
  • The diagram may contain self-loops.
  • The number of edges in the graph is in the range [1,4∗104][1, 4 * 10^4][1,4∗104].

To understand

  • The graph given in this problem is “directed graph”;
  • “Safe end” means that all of its precursors can go through a finite number of steps to a node that has no successor. In other words, it’s not safe if the node is in the loop;

We can use depth-first traversal or breadth-first traversal to determine whether there is a loop in a directed graph.

Method 1: depth-first traversal

  • Because directed graphs have loops, a Boolean array is required for depth-first traversalvisitedRecords whether a vertex has been accessed;
  • Since it is also necessary to record whether a certain node is in a ring after traversal, the meaning of Boolean array can be enriched, and the return value of recursive function can be used, so the following definition is defined:
    • Expand the Boolean arrayvisitedIn addition to indicating whether a loop has been accessed or not, it also needs to indicate whether a loop exists. Therefore, you can set a Boolean array to a wrapper typeBoolean:nullIt has not been accessed yet,falseThere is no loop from the current vertex,trueThat there is a loop from the current vertex;
    • The return value of depth-first traversal iftrue, indicating that there is a loop traversed from the vertex; If it isfalse, indicating traversal from the vertex, there is no loop.

Reference code 1:

import java.util.ArrayList;
import java.util.List;

public class Solution {

    /** * Use Boolean (null) to indicate that the result has not been computed * true means that all paths from the current vertex have a loop * false means that all paths from the current vertex have no loop */
    private Boolean[] visited;

    private int[][] graph;

    public List<Integer> eventualSafeNodes(int[][] graph) {
        int len = graph.length;
        this.visited = new Boolean[len];
        this.graph = graph;

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            // If all paths from the current vertex have a loop, this vertex skips
            if (dfs(i)) {
                continue;
            }
            res.add(i);
        }
        return res;

    }

    / * * *@param u
     * @returnIs there any path from vertex u that leads back to u? Return true */ if there is a loop
    private boolean dfs(int u) {
        if(visited[u] ! =null) {
            return visited[u];
        }


        // Assume that there is a loop for all paths starting from u
        visited[u] = true;
        // The node u is considered safe only if all of its successors cannot return to the node u
        for (int successor : graph[u]) {
            if (dfs(successor)) {
                return true; }}// Visited [u] = false; // Visited [u] = false
        visited[u] = false;
        return false; }}Copy the code

Complexity analysis:

  • Time complexity: O(V+E)O(V +E)O(V +E), where VVV is the total number of vertices and EEE is the number of edges of the graph;
  • Space complexity: O(V+E)O(V +E)O(V +E).

Note: When declaring variables and designing recursive functions, it is necessary to specify the variable definition of recursive functions and the return value of recursive functions, and write the necessary comments, so that when writing code logic, it will not be messy.

Method 2: Breadth-first traversal (topological sort)

How do you know which vertices are the ends of a breadth-first traversal? You can create an adjacence list by creating an inverse adjacence list, that is, inverting the edges of a directed graph given in the graph. A breadth-first traversal starts with a vertex that has no precursor (no vertex pointing to it), and all nodes traversed are “ultimately safe.”

A typical application scenario for breadth-first traversal in a directed graph is called “topological sorting”, which requires the concept of “grouping in degree”. The question requires that “the elements in the answer array should be arranged in ascending order”, so the nodes visited need to be recorded first and output uniformly.

If you are not familiar with topological sorting, you can do forcings 207 and 210, and write a few times, and you will find that it is actually a very simple thing.

Reference code 2:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Solution {

    public List<Integer> eventualSafeNodes(int[][] graph) {
        int N = graph.length;
        // Step 1: Create the graph, establish the inverse adjacencies list
        Set<Integer>[] reverses = new HashSet[N];
        for (int i = 0; i < N; i++) {
            reverses[i] = new HashSet();
        }

        int[] inDegree = new int[N];
        for (int i = 0; i < N; i++) {
            for (intj : graph[i]) { reverses[j].add(i); inDegree[i]++; }}// Step 2: Topological sort. Set the nodes that topological sort accesses to to true because the output needs to be sequential
        // Add the vertex with the input degree of 0 to the queue and start the breadth-first traversal from those vertices
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 0) { queue.offer(i); }}boolean[] visited = new boolean[N];
        List<Integer> res = new ArrayList<>();
        while(! queue.isEmpty()) {int front = queue.poll();
            All nodes are safe to access from the point where there is no input
            visited[front] = true;
            for (int successor : reverses[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) { queue.offer(successor); }}}// Step 3: The node that has been accessed is the "secure node"
        for (int i = 0; i < N; i++) {
            if(visited[i]) { res.add(i); }}returnres; }}Copy the code

Complexity analysis:

  • Time complexity: O(V+E)O(V +E)O(V +E), where VVV is the total number of vertices and EEE is the number of edges of the graph;
  • Space complexity: O(V+E)O(V +E)O(V +E).

Summary: The problem with a graph is often to do a walk in the graph, according to different requirements, choose depth first walk or breadth first walk, or both can be used. When studying, we need to practice more. Different problems need to pay attention to different details. I’ve written it a few times before I really master it, and so do other algorithms.

That’s all for today. Thanks for watching.