You must be able to implement DFS recursively and stack

I. Algorithm principle

Compared with BFS, DFS uses the queue to realize the center spread search. DFS uses the idea of stack (advanced after out), using backtracking algorithm, or using DFS recursion. Intuitively, it is a way to go to the black, if it finds the south wall, it will return to the last intersection and continue to go to the black…. And so on and so forth until you reach the target, so it’s called a depth-first search.

1. Stack implementation method

• The root node is first pushed onto the stack.
• Pop a node from the stack and verify that it is the target.
  • If the target is found, the search ends and the results are returned.
  • Otherwise, all of its immediate children that have not yet been checked are added to the stack.
• If the stack is empty, the entire graph has been checked — that is, there is no target searched in the graph. End the search and return “target not found”.
• Repeat Step 2.

Pseudo code

stack.push(root)
while(!stack.isEmpty())
	node = stack.pop()
	forEach neighbor node is a neighboring nodeifNeighbor was not accessedstack.push(neightbor)
			// Record the path
			stack.parent = node
			// Other operations...
			todo...
Copy the code

2. Implementation method of recursion

• Given root node
• Traverses all adjacent nodes of the root node that have not been accessed
  • If the target is found, the search ends and the results are returned
  • Otherwise, set the adjacent node as the new root node and repeat Step 2
  • If there are no adjacent nodes that have not been visited, the search for the branch ends and returns
• All branches are traversed, the search ends and “target not found” is returned.

Pseudo code:

DFS()
	dfsVisit(root)

dfsVisit(node)
	forEach neighbor node is a neighboring nodeifNeighbor has not been visited// Record the path
			neighbor.parent = root
			// Other operations
			todo..
			dfs(neighbor)
Copy the code

Two. Concrete implementation

Use a common recursive implementation

package com.example.DFS;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DFS {
    // <1, [2, 3]> indicates that the parent node of node 1 is node 2 and the distance from the source point is 3
    private Map<Integer, int[]> disTo;
    / * * *@paramThe distance between one node and other nodes * [[0, 1, 1], [1, 2, 2]] indicates that the distance from point 0 to point 1 is 1, and the distance from point 1 to point 2 is 2 *@paramN Number of all nodes 1<= N <= 1000 *@paramK Source node 1< k <n */
    public Map<Integer, int[]> DFS(int[][] edges, int n, int k){
        // Generates a directed graph from the array of edges
        //<0, <{1,2}, {2,3}>> indicates that node 0 has 1,2 adjacent nodes with a distance of 2 and 3 respectively
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for(int[] edge:edges){
            if(! graph.containsKey(edge[0]))
                graph.put(edge[0].new ArrayList<int[] > ()); graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        // Initialize disTo
        disTo = new HashMap<>();
        for(int i=0; i<n; i++){
            if(i==k)
                disTo.put(i, new int[]{k, 0});
            else disTo.put(i, new int[] {-1, Integer.MAX_VALUE});
        }
        dfsVisit(graph, k);
        return disTo;
    }
	
    /**
     * dfs
     * @param graph
     * @param k
     */
    private void dfsVisit(Map<Integer, List<int[]>> graph, int k){
        if(graph.containsKey(k))
            for(int[] edge:graph.get(k)){
                int[] temp = disTo.get(edge[0]);
                // Ensure that the node is not accessed
                if(temp[0] = = -1 && temp[1] == Integer.MAX_VALUE) {
                    //setParent records the path
                    temp[0] = k;
                    //setDisTo records distance
                    temp[1] = disTo.get(k)[1] + edge[1];
                    // Recursive implementation
                    dfsVisit(graph, edge[0]); }}}/** * Output result *@param disTo
     * @param end
     */
    public void printPath(Map<Integer, int[]> disTo,int pathTo){
        int distance = disTo.get(pathTo)[1];
        List<Integer> path = new ArrayList<>();
        int temp = pathTo;
        path.add(temp);
        while(temp! =0&& temp! = -1){
            temp = disTo.get(temp)[0];
            path.add(temp);
        }
       System.out.print("From initial node to node"+end+The distance of "is"+distance+"\n"
       					+"Path is: \n"+path.get(0));
        for(int i=1; i<path.size(); i++){ System.out.print("<--"+path.get(i)); }}}Copy the code

Example 1.

Test input Input:

Expected output: Distance: 30 Path: 0–>1–>5–>4

Environment: Windows10, Java11

Results 2.

Try to output the path and distance to node 5

How to output all paths?

Allowing a node to be traversed down by multiple different parent nodes in a graph without a loop, or after the loop is removed, allows you to actually find all paths in the graph

DFS, no BFS? I arranged Dijkstra for you