DFS-BFS

DFS模板

void dfs(int x){
    visited[x] = true;
    //do something
    for(...){
        //judge next node
        if(!visited[nx] && ...){
            dfs(nx);
        }
    }
}

BFS模板

写法1：由于在插入队列时，没有标记visited，导致queue中出现重复点，但是可被continue过滤

void bfs(){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int f = q.front(); q.pop();
        if(visited[f]) continue; // must write
        visited[f] = true;
        // do something
        for(...){
            // judge next node
            if(!visited[f] && ...){
                q.push(nx)  
            }
        }
    }
    
}

写法2：在输入时就标记新点，queue中无重复点，这种写法更好

void bfs(){
    queue<int> q;
    q.push(s);
    visited[s] = true; // must write
    while(!q.empty()){
        int f = q.front();q.pop();
        //do something
        
        for(...){
            //judge next node
            if(!visited[nx] && ...){
                visited[nx] = true;
                q.push(nx);
            }
        }
    }
    
}