DFS

排列數(shù)字

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

n皇后

#include<iostream>
using namespace std;
const int N = 20 ;
char g[N][N] ;
bool c[N], x[N] , y[N];
int n , m ;
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i < n; i++) cout << g[i] << endl;
        cout << endl;
        return ;
    }
    for(int i = 0 ; i < n ; i++)
    {
        if(!c[i] && !x[u+i] && !y[u-i+n])
        {
            c[i] = x[u+i] = y[u-i+n] = true ;
            g[u][i] = 'Q';
            dfs(u+1);
            g[u][i] = '.';
            c[i] = x[u+i] = y[u-i+n] = false ;
        }
    }
}
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

走迷宮

#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII ;
const int N = 110 ;
PII q[N * N];
int f[N][N] , d[N][N];
int n , m ;
int dx[] = {0,1,0,-1} , dy[] = {1,0,-1,0} ;
int bfs()
{
    memset(d , -1 , sizeof d);
    d[1][1] = 0 ;
    q[0] = {1,1};
    int hh = 0 , tt = 0 ;
    while(hh <= tt)
    {
        auto t = q[hh++] ;
        for(int i = 0 ; i < 4 ; i++)
        {
            int x = t.first + dx[i] , y = t.second + dy[i] ;
            if(x<=n &&x>0 && y<=m && y>0 && d[x][y] == -1 && f[x][y] == 0)
            {
               q[++tt] = {x,y};
               d[x][y] = d[t.first][t.second] + 1 ;
            }
        }
    }
    return d[n][m];
}
int main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            cin >> f[i][j];
    
    cout << bfs();
    return 0;
}

拓撲序列

單鏈表

點擊跳轉(zhuǎn)至例題


idx存的是指針

樹與圖的深度優(yōu)先搜索

樹的重心

每個節(jié)點都是一個單鏈表

模擬隊列

hh = 0 , tt = -1

有向圖的拓撲序列

都是從前指向后,即有向無環(huán)圖（不能有環(huán)）
所有入度為0的點，都能排在前面的位置

刪掉t->j的邊，僅僅是j的入度減一，當j的入度為0的時候，放入隊列文章來源地址http://www.zghlxwxcb.cn/news/detail-478062.html

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n , m ;
int e[N] , h[N] , ne[N] , idx;
int d[N] , q[N];
void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}
bool topool()
{
    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 x,y;
        cin >> x >> y;
        add(x,y);
        d[y]++;
    }
    if(topool())
    {
        for(int i = 0 ; i < n ; i++) cout << q[i] << " " ;
    }
    else cout << -1 ;
    return 0;
}

bellman-ford

有邊數(shù)限制的最短路

spfa

spfa求最短路

spfa判斷負環(huán)

Floyd

Floyd求最短路

Prim

Prim算法求最小生成樹

Kruskal

Kruskal算法求最小生成樹

染色法判定二分圖

染色法判定二分圖

到了這里，關(guān)于搜索與圖論（acwing算法基礎(chǔ)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！