leetcode depth first search, breadth first search and joint search

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;
    }
};

Tags: data structure leetcode Union Find dfs bfs

Posted by jax_15 on Wed, 30 Mar 2022 21:36:20 +0300