Introduction:

Breadth-first search is one of search algorithms. This paper will introduce some algorithm problems solved by breadth-first search. These problems will be classified and the advantages and disadvantages of this algorithm will be summarized


First knowledge breadth first search

Before getting into breadth-first search, let’s take a look at a few common data structures, linked lists, trees, and graphs. Let’s take a look at one of the simpler data structures, a linked list, which is similar to an array. It’s a linear structure. Basically, it’s a path. In contrast to arrays, linked lists can be stored in memory without being a contiguous region. There will be a variable in the linked list node to specify the next node, and the list representation will be written in code as follows:

class ListNode {
    int val;
    ListNode next;
}
Copy the code

Where val represents the value on this node and next represents the next node on this node.

After that, let’s look at another data structure, the binary tree, which is actually an extension of the linked list. Here, instead of having just one node, the next node of a node may have two nodes. If the tree structure is expressed in code, it looks like this:

class TreeNode {
    int val;
    TreeNode left, right;
}
Copy the code

You might ask, well, how do you represent a multi-fork tree? A tree node can have multiple child nodes:

class TreeNode {
    int val;
    List<TreeNode> children;
}
Copy the code

Whether there are two nodes or multiple nodes, there is a hierarchical relationship between the parent and children in the tree. For a normal tree structure, a node only stores the information of its children, but not the information of its parents. You are given a tree node. You only go in the direction of the children, which means that the tree is actually directional.

Finally, we look at the picture, figure divided into directed graph and undirected graph, the tree is actually calculate directed graph of a, is to not to, basically be to see, if the two nodes together, they are between each word is undirected graph, if only from one node to another node, whereas may not line, that is a directed graph, whether directed graph or undirected graph, in the code, We can all represent the following:

class GraphNode {
    int val;
    List<Integer> neighbors;
}
Copy the code

Isn’t that the way we represented the multi-fork tree? That’s right, but the relationship is no longer parent and children, it’s neighbor, there’s no hierarchy, every node is equal.

So with those data structures out of the way, let’s go back to the breadth-first search algorithm, which is often used on trees and graphs, and let’s think about the question, if I give you one node on a connected graph, how do I get all of the nodes on the graph? The idea is very simple, first of all we know, we can add a given node and its neighbor to the answer, but the neighbors and neighbors, so we have to continue the process, until all the points found, of which we will likely encounter a situation is, we access to find the point before, so, here we also need a heavy mechanism. One thing here is that each point can only find its neighbors, that is to say, it will only look around it, it will only spread out one space at a time, to solve the breadth-first search problem, we will use a FIFO data structure like a queue, this is not hard to understand, the point found first we will consider its neighbors first.


Question classification

We briefly introduced the breadth-first search algorithm above, so what kind of problems can it be used to solve?

  • Level traversal
  • From point to surface traversal diagram
  • A topological sort
  • Finding the shortest path

We one by one, first level traversal, and the front said before, each node will only find their way around the node, you can imagine the current layer node can only find the next layer (layer traversal before does not consider), so we can find something together, put a layer of this layer is also use this concept to find all the nodes.

The second point is to traverse the graph, which is actually the example above “Given a node on a connected graph, you need to find all nodes in the graph”. You might ask, what’s the use of traversing the whole graph? If we know the number of all nodes, we can actually judge the connectivity of a graph by traversing the whole graph. If we can’t find some points from a point, it means that the graph is not connected, and some nodes are not on the graph and are separated.

The third point is topological sorting, here you can refer to an article I wrote before the principle of topological sorting and problem analysis.

And the fourth one, which is often used, is to find the shortest path to two points on the graph, but there is a condition, of course, that the graph must be a simple connected graph, and what is a simple graph, is that the edges have no weight, or the weight is fixed. Start at one point and find all the points in the next layer, start at the next layer and find all the points in the next layer, take one step at each layer, and when we find the point we are looking for, the number of steps at that point is the final answer.

For breadth-first search space and time complexity analysis is relatively simple, general questions are need to traverse the entire figure, so the time complexity is O (N + M), space complexity is O (N), where N is the total number of nodes, M is the number of edges, some diagrams, such as the connected graph (M = N ^ 2), When we traverse, we try to walk all the edges. For space, we usually only record the nodes visited and the nodes of the current layer, and do not consider the edges, so the time complexity and space complexity are not quite the same here.


LeetCode common topics

LeetCode 103. Binary Tree Zigzag Level Order Traversal

Analysis of the topic:

Consider the first point mentioned above, hierarchy traversal. We need to record the information of each layer, but the order of recording is distinguished, the first layer is recorded from left to right, the second layer is reversed, from right to left, the third layer is recorded from left to right,… Direction, you can see the record of each layer and the lower level is different, is a form of crisscross, of course, we can all records from left to right, then to a specific layer can give reversal record results, but there is a small trick is, we are recorded from left to right, but the record way, a way to record from the tail end of the list, The other is to join from the head of the list. Tree traversal is relatively easy because tree traversal is directional. This directionality ensures that we do not access nodes that we have previously visited. Therefore, we do not need to use Set or Boolean arrays to help de-load.

Reference code:

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null) {
        return result;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    
    queue.offer(root);
    
    boolean isReverse = false;
    while(! queue.isEmpty()) {int size = queue.size();
                    
        List<Integer> curLevel = new ArrayList<>();
        
        for (int i = 0; i < size; ++i) {
            TreeNode cur = queue.poll();
            if(cur.left ! =null) {
                queue.offer(cur.left);
            }

            if(cur.right ! =null) {
                queue.offer(cur.right);
            }
            
            if (isReverse) {
                curLevel.add(0, cur.val);
            } else{ curLevel.add(cur.val); } } isReverse = ! isReverse; result.add(curLevel); }return result;
}
Copy the code


LeetCode 261. Graph Valid Tree

Analysis of the topic:

Examine the second point, traversing the graph from points and faces. The first thing you need to know is, how do you tell if a tree is valid? There are two things here. One is that there are no rings in a tree. How do you make sure it’s acyclic? If you draw a tree, you will find that, no matter how, the number of nodes and edges are n – 1 = the number of edges, so this is not enough, is not, we also need to judge the connectivity, that is to say, from one node to traverse all the points, meet the two conditions of figure to a tree.

Reference code:

public boolean validTree(int n, int[][] edges) {        
    if (n - 1! = edges.length) {return false;
    }
    
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    
    buildGraph(graph, edges, n);
    
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    
    queue.offer(0);
    
    while(! queue.isEmpty()) {int cur = queue.poll();
        
        if(! visited.add(cur)) {return false;
        }
        
        for (intnei : graph.get(cur)) { queue.offer(nei); graph.get(nei).remove(cur); }}return visited.size() == n;
}

private void buildGraph(Map<Integer, Set<Integer>> graph, int[][] edges, int n) {
    for (int i = 0; i < n; ++i) {
        graph.put(i, new HashSet<Integer>());
    }
    
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]); }}Copy the code


LeetCode 317. Shortest Distance from All Buildings

The shortest distance is mainly investigated. Please refer to the previous algorithm in ARTS. There is one thing need to explain, matrix in fact can also be seen as a figure, the Spaces in the matrix can as a node, each node can be connected to the adjacent to the up and down or so four nodes, each form an edge between two nodes, for a m * n matrix, if as a figure, figure is m * n, the number of nodes The number of edges is m times n over 2.


conclusion

Breadth-first search is here, here I don’t have listed many questions, understand the algorithm itself, and is suitable for solving the problem is the key, breadth-first search is suited to solve hierarchy traversal, by the point and the surface traversal graph, topological sort and the o the shortest distance between two points in a simple chart, after understanding the original rational thing, I’m going to go through a few more problems to solidify this, and finally I’m going to get a good idea of this algorithm.