搜索与图论

数据结构 空间
DFS stack O(n)
BFS queue 最短路

DFS

  • 采用stack
  • 回溯——恢复状态
  • 剪枝——提前回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

const int N = 100;

int n;  //记录深度

int path[N];
int st[N];

void dfs(int u)
{
    if (u== n)  
        {
            for (int i = 0 ;i < n; i ++)
            printf("%d", path[i]);
            puts("");
            return;
        }
    for (int i = 1; i <= n; i ++)
        {
            if(!st[i])
                path[u] = i;
                st[i] = true;
                dfs(u + 1);
                st[i] = false;
        }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>

using namespace std;

const int N = 100;

int n;  //记录

char g[N][N];
bool col[N], dg[N], udg[N];
//列    column
//行    line
//对角线    diagonal

void dfs(int u)
{
    if (u == n)  
        {
            for (int i = 0 ;i < n; i ++)    puts(g[i]); //char* 型指针
            puts("");
            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;
}

逐行放置皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>

using namespace std;

const int N = 100;

int n;  //记录

char g[N][N];
bool raw[N], col[N], dg[N], udg[N];
//列    column
//行    raw
//对角线    diagonal

void dfs(int x, int y, int s)
{
    if (x == n)  x = 0 ,y ++;

    
    if(y == n){    
        if (s == n)     //是否放置了n个皇后
        {
            for (int i = 0 ;i < n; i ++)    puts(g[i]); //char* 型指针
            puts("");
            
        }
        return ;
    }
    dfs(x + 1 , y, s);




    if(!raw[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
            { g[x][y] = 'Q';
                raw[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
                dfs(x + 1, y , s + 1);
                 raw[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
                 g[x][y] =  '.';
}          
}



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



    dfs(0, 0, 0);
    return 0;
}

逐个格子枚举

BFS

  • 采用queue
  • 边权都为1时，为最短路径
  • DP是特殊的最短路问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 110;

typedef pair<int, int> PII;


int n, m;
int g[N][N];        //存放数组
int d[N][N];        //到任意可达点的最短路径

PII q[N * N];



int bfs()
{
    int hh = 0, tt = 0;     //队头和队尾
    q[0] = {0, 0};      //起始点

    memset(d, -1, sizeof d);
    d[0][0] = 0;        //起始点距离为0

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    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 >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1 )
                        {
                            d[x][y] = d[t.first][t.second] + 1;  //存储距离
                            q[ ++ tt] = {x,y} ; //
                        }
            }
    }

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

有向图

  • 邻接矩阵
  • 邻接表

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010, M = N * 2;

int n;

int ans = N;

int h[N], e[M], ne[M], idx;
//idx表示第n条边
//h[N] : 表示 第 i 个节点的 第一条边的 idx
//ne[M] : 表示 与 第 idx 条边 同起点 的 下一条边 的 idx
//e[M] : 表示 第idx 条边的 终点

bool st[N];

void add(int a,int b)
{
    e[idx] =  b;            //记录终点节点
    ne[idx] = h[a];        //相当于插入链表 ，将此节点后面的值传进来
    h[a] = idx ++;         //h[a]指向当前新增的节点
}

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])
        {
            int s = dfs(j);
            res = max (res, s);
            sum += s;

        }
    }
    res = max (res, n - sum);
    ans = min(ans, res);
    return sum;
}


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

    dfs(1);
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010, M = N * 2;

int n, m;


int h[N], e[M], ne[M], idx;
//idx表示第n条边

int d[N], q[N];
//q为队列，d为距离


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

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


        }
    }
    return d[n];
}


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

    cout << bfs(1) << endl;
    return 0;
}

拓扑序列

  • 有向无环图
  • 一个有向无环图，一定至少有一个入度为0的点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010;

int n,m;

int h[N], e[N], ne[N], idx ;
int q[N], d[N];





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

int topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++)
        if (!d[i])      //将入度为0的点入队
            q[ ++ tt] = i;
    
    while (hh <= tt)
    {
        int t = q[hh ++];

        for (int i = h[t]; i != -1; i = ne[i])  //bfs
        {
                int j = e[i];
                d[j] --;
                if (d[j] == 0)
                    q[++tt] = j;
        }
        
    }
    
    if(tt == n - 1){
        for(int i = 0; i < n; i++)
            cout << q[i] << " ";
        
    }
    else
            cout << -1;




}


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

    topsort();
    return 0;


}

最短路

image-20240311224225995

单源最短路
所有边权都为正数

朴素Dijkstra算法O():稠密图

堆优化版Dijkstra算法O(mlogn)：稀疏图

存在负权边

Bellman-Ford算法O(nm)

SPFA算法，一般O(m), 最坏O(nm)

多源汇点最短路

Floyd算法 O()