1, Popular explanation: source

Depth first can think like this. A person gets lost and meets many forks. He has only one person and wants to go out, so he can only try one by one. When one road goes to the dark, he finds the end, and then turn back to the other forks of the road just now. Finally, he finds that all the forks of the road have been completed. Choose another road to continue the above operation until all the roads have passed. Breadth first is not like this. A person gets lost, but he has skills (separation). When he meets a fork intersection, he doesn't choose one to go, but try it with multiple people. For example, there are three fork intersections a, B and C. he takes one step on road a, then one step on Road B, and then one step on road C. the steps are neat and unified until all the roads have passed.

Breadth first is not like this. A person gets lost, but he has skills (separation). When he meets a fork intersection, he doesn't choose one to go, but try it with multiple people. For example, there are three fork intersections a, B and C. he takes one step on road a, then one step on Road B, and then one step on road C. the steps are neat and unified until all the roads have passed.

The conclusion is: one to search deep, one to search around

Combined search set:

Merge two disjoint sets into one.

Find: query whether two elements are in the same collection.

2, Characteristics

Depth first search (easy to write into recursion), which is generally implemented by stack and usually solves the connectivity problem

Breadth first search, generally implemented in queues, usually solves the shortest path problem

3, Examples

LeetCode 547 number of provinces

Title Description:

There are n cities, some of which are connected to each other, others are not connected. If city a is directly connected to city b and city b is directly connected to City c, city a is indirectly connected to city c.

A province is a group of directly or indirectly connected cities, excluding other cities that are not connected.

Give you an n x n matrix isConnected, where isConnected[i][j] = 1 indicates that the ith city and the jth city are directly connected, and isConnected[i][j] = 0 indicates that they are not directly connected.

Returns the number of provinces in the matrix.

Method 1: depth first search dfs

The code is as follows:

class Solution { public: int n; vector<bool>visited; int findCircleNum(vector<vector<int>>& isConnected) { n=isConnected.size(); visited.resize(n);//Record whether each city has been traversed int res=0; for(int i=0;i<n;i++){ if(!visited[i]){//If the city has not been traversed, it is a new disconnected city dfs(i,isConnected);//dfs looks for the city connected with it res++; } } return res; } void dfs(int i,vector<vector<int>>isConnected){ visited[i]=true;//It has been traversed and set to true for(int j=0;j<n;j++){ if(isConnected[i][j]==1&&!visited[j]){//Pruning. If some cities have been traversed, skip dfs(j,isConnected); } } } };

Method 2: breadth first search bfs

class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n=isConnected.size(); vector<bool>visited(n); int res=0; queue<int>q; for(int i=0;i<n;i++){ if(!visited){ res++; q.push(i); visited[i]=true; while(q.size()){ int temp=q.front(); q.pop(); for(int j=0;j<n;j++){ if(isConnected[temp][j]==1&&!visited[j]){ visited[j]=true; q.push(j); } } } } } return res; } };

Method 3: union_find

class Solution { public: vector<int>p; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int findCircleNum(vector<vector<int>>& isConnected) { int n=isConnected.size(); //initialization for(int i=0;i<n;i++){ p.push_back(i); } int cnt=n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(isConnected[i][j]&&find(i)!=find(j)){ p[find(i)]=find(j);//Collection merge cnt--; } } } return cnt; } };