一.DFS

1.1 数字排列

#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N];
void dfs(int u){
    if(u == n){
        for(int i = 0;i < n;i++)
            cout << path[i] <<" ";
        cout << endl;
        return ;
    }
    for(int i = 1;i <= n;i++){
        if(!st[i]){
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}


int main(){
    cin >> n;
    dfs(0);
}

1.2 n皇后问题

#include <iostream>
using namespace std;
int n;
const int N = 10;
char g[N][N];
bool col[N],dg[N],udg[N];//列数、正对角线、反对角线
void dfs(int u){
    if(u == n){
        for(int i = 0;i < n;i++) puts(g[i]);
        cout << endl;
        return ;
    }
    for(int i = 0;i < n;i++)
        if(!col[i] && !dg[u+i] && !udg[n - u + i])
        {
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            dfs(u+ 1);
            col[i] = dg[u+i] = udg[n-u+i] = false;
            g[u][i] = '.';
        }
}

int main(){
    cin >> n;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            g[i][j] = '.';
        
    dfs(0);
    return 0;
    
}

二.BFS

2.1 走迷宫

using PII = pair<int,int>;
const int N = 110;
int n,m;
int g[N][N];
int d[N][N];
queue<PII> q;

int bfs(){
    q.push({0,0});
    memset(d,-1,sizeof d);
    d[0][0] = 1;
    int next[4][2] = {
            {1,0},
            {-1,0},
            {0,1},
            {0,-1}
    };
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        for(int i = 0;i < 4;i++){
            int tx = t.first + next[i][0];
            int ty = t.second + next[i][1];
            if(tx >= 0 && tx< n && ty >= 0 && ty< m&& g[tx][ty] == 0 && d[tx][ty] == -1){
                d[tx][ty] = d[t.first][t.second] + 1;
                q.push({tx,ty});
            }
        }
    }

    return d[n-1][m-1];

}
int main(){
    cin >> n>> m;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++){
            cin >> g[i][j];
        }

    cout << bfs() << endl;

    return 0;

}

2.2 八数码

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

int direction[4][2] = {
    {0,1},
    {0,-1},
    {1,0},
    {-1,0}
};

int bfs(string start){
    queue<string> q;
    unordered_map<string,int> d;
    q.push(start);
    d[start] = 0;
    
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int distance = d[t];
        if(t == "12345678x") return distance;
        int k = t.find('x');
        int x = k / 3,y = k % 3;
        for(int i = 0;i < 4;i++){
            int a = x + direction[i][0];
            int b = y + direction[i][1];
            if(a >= 0 && a < 3 && b>= 0 && b < 3){
                swap(t[k],t[a *3 + b]);
                if(!d.count(t)){
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[k],t[a *3 + b]);
            }
        }
        
    }
    
    
    return -1;
}



int main(){
    string start;
    for(int i = 0;i < 3;i++)
        for(int j = 0;j < 3;j++)
            {
                char c;
                cin >> c;
                start += c;
            }
            
    cout << bfs(start) << endl;

    return 0;

}

三、树与图的遍历

3.1 树与图的深度优先遍历之树的重心

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010,M = N * 2;
int h[N];
int e[M];
int ne[M];
int idx;
bool st[N];
int ans = N;
int n;
;void add(int a,int b){
    e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}

int dfs(int u){
    st[u] = true;
    int sum = 1,res = 0;
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(!st[j]){ //均为平级，所以需要循环遍历所有的平级子树 然后找到res最大值
            int s = dfs(j);
            res = max(res,s);
            sum += s;
        }
        
    }
    res = max(res , n - sum);
    ans = min(ans,res); //每一层递归保证ans取得最小值
    
    return sum;
}




int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i = 0;i < n - 1;i++ ){
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;

}

3.2 图的广度优先遍历之图中节点的层次

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>
#include <iso646.h>
#include <queue>
using namespace std;

const int N = 1e5 + 10,M = N* 2;
int n,m;
int h[N],ne[M],e[M],idx;
queue<int> q;
int d[N];

void add(int a,int b){
    e[idx] = b;ne[idx] = h[a],h[a] = idx++;
}

int bfs(){
    q.push(1);
    d[1] = 0;
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    
    return d[n];
}

int main(){
    cin >> n>> m;
    memset(d,-1,sizeof d);
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i++){
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    cout << bfs() ;
    return 0;

}

四、拓扑排序

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E5 + 10,M = N* 2;
int n,m;
int h[N],ne[M],e[M],idx;
int q[N];
int d[N];

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

bool topsport(){
    int hh = 0,tt = -1;
    for(int i = 1;i <= n;i++){
        if(!d[i]){
            q[++tt] = i;
        }
    }

    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[++tt] = j;
        }
    }

    return tt == n - 1;
}



int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i++) {
        int a,b;
        cin >> a >> b;
        add(a,b);
        d[b]++;
    }
    
    if(topsport()){
        for(int i = 0;i < n;i++) cout << q[i] <<" ";
    }else{
        cout << "-1";
    }
    
    return 0;

}

五、dijkstra算法

5.1朴素版dijkstra算法

#include<bits/stdc++.h>

using namespace std;

const int N = 510;
const int inf = 0x3f3f3f3f;

int mp[N][N], dis[100010];
int n,m;
bool st[N];

int dijkstra(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    for(int i = 1; i <= n - 1; ++i){
        int t = -1;
        for(int j = 1; j <= n; ++j){
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        }

        st[t] = true;
        for(int j = 1; j <= n; ++j){
            if(dis[j] > dis[t] + mp[t][j])
                dis[j] = dis[t] + mp[t][j];
        }
    }

    return dis[n] == inf ? -1 : dis[n];
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            mp[i][j] = (i == j ? 0 : inf);
    int a,b,v;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d",&a,&b,&v);
        mp[a][b] = min(mp[a][b], v);
    }

    printf("%d\n", dijkstra());

    return 0;
} 

5.2堆优化版Dijkstra

#include<bits/stdc++.h>

using namespace std;

using PII = pair<int,int>;
const int N = 150010;
const int inf = 0x3f3f3f3f;

int dist[N], h[N], e[N], w[N], ne[N], idx;
int n,m;
bool st[N];

void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}


int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    while(!heap.empty()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second,distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver];i != -1;i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    
    return dist[n] == inf ? -1: dist[n];
}
int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;

    int a,b,v;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d",&a,&b,&v);
        add(a,b,v);
    }

    printf("%d\n", dijkstra());

    return 0;
} 

六、Bellman-ford算法

#include<iostream>
#include <cstring>
using namespace std;


const int N = 510,M = 10010;
int n,m,k;
int dist[N],backup[N];
struct Edge{
    int a,b,w;
}edges[M];

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for(int i = 0;i < k;i++){
        memcpy(backup,dist,sizeof dist);
        for(int j = 0;j < m;j++){
            int a = edges[j].a,b = edges[j].b,w = edges[j].w;
            dist[b] = min(dist[b],backup[a] + w);
        }
    }

    if(dist[n] > 0x3f3f3f3f /2 ) return -1; //因为存在负的边权，但是不会减太多，所以是0x3f3f3f3f/2
    return dist[n];
}


int main(){
    cin >> n >> m >> k;
    for(int i = 0;i < m;i++){
        int a,b,w;
        cin >> a >> b >> w;
        edges[i] = {a,b,w};
    }
    int t = bellman_ford();
    if(t == -1) puts("impossible");
    else cout << t;
}

版权属于：superzhaoyang

本文链接：https://www.superzhaoyang.top/archives/39/

转载时须注明出处及本声明