@public account to read the link

preface

In directed and undirected graphs, DFS and BFS often appear in everyday algorithms if the nodes have equal weights or no rights. Not only that, DFS, BFS can not only solve the problem of graph theory, in the search of other problems is also the most basic (but different strategies) of the two classical algorithms.

Backtracking algorithm
dfs

Adjacency matrix and adjacency list

Adjacency matrix: Adjacency matrix is an array (two-dimensional) representation of the graph. You can see the following examples. Of course, this situation is easy to waste space, so many people do space optimization, even adjacency list approach.

Adjacency list:
It’s still going to waste half the space again
Just add a weight attribute to the node!

Depth-first Search (DFS)

Concept:

Depth First Search belongs to a graph algorithm, abbreviated as DFS, namely Depth First Search. The process is simply as deep as you can go into every possible branch path, and each node can only be accessed once.

Simply put, there are prerequisites for completing DFS. There is a connection. The single node DFS is broken, and he needs to find the nodes that are associated with it. The reason DFS may be easier to start with than BFS is that DFS mostly uses recursive steps to complete DFS and requires little markup.

We usually store graph information using an adjacency List (a one-dimensional array nested List A [List]) or an adjacency matrix (a two-dimensional array [][]). Sometimes in order to optimize the space will choose the cross linked list or adjacent multiple list for storage to save space, but the operation is often very complex. And in general, the larger the graph needs to design algorithm optimization, so this example uses adjacency matrix to complete!

The DFS process can be thought of as follows:

• Start at the starting point and walk in one direction, stop at the end and go in the other direction, until all operations are finished and exit!
• The depth-first search executes like a stack operation.Discard the. Always deal with the latest node added, this recursion just meets its nature, and recursive codeIt’s also simpler to write.
• DFS process can refer to the binary tree prior traversal, which is essentially a DFS.

For the DFS shown above. This can be expressed in the following code:

packageGraph theory;public class dfs {
	static boolean isVisit[];
	public static void main(String[] args) {
		int map[][]=new int[7] [7];
		isVisit=new boolean[7];
		map[0] [1]=map[1] [0] =1;
		map[0] [2]=map[2] [0] =1;
		map[0] [3]=map[3] [0] =1;
		
		map[1] [4]=map[4] [1] =1;
		map[1] [5]=map[5] [1] =1;
		map[2] [6]=map[6] [2] =1;
		map[3] [6]=map[6] [3] =1;
	
		isVisit[0] =true;
		dfs(0,map);// Start traversal from 0
	}
	private static void dfs(int index,int map[][]) {
		// TODO Auto-generated method stub
		System.out.println("Access"+(index+1) +"");
		for(int i=0; i<map[index].length; i++)// Find the unicom node
		{
			if(map[index][i]>0&&isVisit[i]==false)
			{
				isVisit[i]=true;
				dfs(i,map);
			}
		}
		System.out.println((index+1) +"End of visit"); }}Copy the code

The approximate order of access is

Width (breadth) First Search (BFS)

Concept:

BFS, its English full name is Our First Search. BFS does not use a rule of thumb algorithm. From an algorithmic point of view, all children created by expanding a node are added to a first-in, first-out queue. In normal experiments, the nodes whose neighbors have not been verified are placed in a container called open (such as a queue or linked list), while the verified nodes are placed in a container called closed. (open, closed table)

In simple terms, BFS is a first-in, first-out queue traversal, however, such a distribution in the case of the layer traversal, can refer to the binary tree traversal of the layer traversal!

If you look at the path, the DFS is a mad dog running fast and biting everywhere. Run out of road, turn around, run out of road, run back to other places, and BFS is like a gas, slow delay!

In the example of the above figure, we use an adjacency list to implement traversal.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class bfs {
	public static void main(String[] args) {
		List<Integer> map[]=new ArrayList[7];
		boolean isVisit[]=new boolean[7];
		for(int i=0; i<map.length; i++)/ / initialization
		{
			map[i]=new ArrayList<Integer>();
		}
		map[0].add(1); map[0].add(2); map[0].add(3);
		map[1].add(0); map[1].add(4); map[1].add(5);
		map[2].add(0); map[2].add(6);
		map[3].add(0); map[3].add(6);
		map[4].add(1);
		map[5].add(1);
		map[6].add(2); map[6].add(3);
		
		Queue<Integer>q1=new ArrayDeque<Integer>();
		q1.add(0); isVisit[0] =true;
		while(! q1.isEmpty()) {int va=q1.poll();
			System.out.println("Access"+(va+1));
			for(int i=0; i<map[va].size(); i++) {int index=map[va].get(i);
				if(! isVisit[index]) { q1.add(index); isVisit[index]=true;
				}
			}
		}
	}
}
Copy the code

Summary and comparison

DFS and BFS are often the two extremes of pathfinding! Of course, it may be used differently in different scenarios.

• DFS can be used in search and crawler, if crawler, it is more priority to find different links, which can be used for statistics. And in the search for such as maze class can use DFS to determine whether there is a path, way out and so on.
• BFS can also be used in algorithms and crawlers. BFS prioritizes resources around itself. So the crawler can be used to traverse the site, search the value of the entire site information and so on, the author used beforeCrawler + BFS implemented the template for downloading websites(17 material web page template). And in the algorithm,In a maze or in a powerless graph.BFS can find shortest paths.
  

  

As you can see above, a lot of space is wasted on adjacency matrix implementation storage, but there are some situations where two-dimensional arrays are appropriate — maze-like problems. During the interview, we will often encounter maze classes that require BFS to find the shortest path, or DFS to query whether there is any. Or double BFS or DFS + BFS and so on to solve specific problems.

Finally, I hope you can pay attention to my public account (Bigsai), we learn data structure and algorithm together! It’s okay. You can use your little hands and give it a thumbs up!