图论

图的存储

image-20230719102529647

邻接矩阵

二维数组 $w[u][v]$ 存储从点 $u$ 到点 $v$ 的边的权值

边集数组

边集数组 $e[i]$ 存储第 $i$ 条边的 { 起点 $u$ ,终点 $v$ ,边权 $w$ }

image-20230719102709293

应用：在Kruskal算法中，需要将边按边权排序，直接存边

邻接表

出边数组 $e[u][i]$ 存储 $u$ 点的所有出边的{ 终点$v$ , 边权 $w$ }

应用：各种图，不能处理反向边

image-20230719103008523

链式邻接表

边集数组 $e[j]$ 存储第 $j$ 条边的{ 起点 $u$ , 终点 v ,边权 $w$ }
表头数组 $h[u][i]$ 存储 $u$ 点的所有出边的编号

成对性质：与1异或可以找到另一条边。

image-20230719103330941image-20230719103348552 image-20230719103401166image-20230719103514132image-20230719103546024

链式前向星

一个表头数组悬挂多个链表
边集数组 $e[i]$ 存储第 $i$ 条出边的{ 终点 $v$, 边权 $w$ ,下一条边 $ne$ }
表头数组 $h[u]$ 存储 $u$ 点的第一条出边的编号
边的编号 $idx$ 可取 $0,1,2,3…$

image-20230719104518403image-20230719104544637

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
const int N = 510, M = 3000; // N 最大点数 M 最大边数
struct edge                  // 边
{
    int v, w, ne; // v 终点 w 权值 ne 下一条
};
edge e[M];     // 边集
int idx, h[N]; // h[N] 点的第一条出边 idx边数

void add(int a, int b, int c) // 加边
{
    // 头插法
    e[idx] = {b, c, h[a]};
    h[a] = idx++;
}
void dfs(int u, int fa)
{
    // 从第一个条出边开始，到达-1找完，下一次找的是下一条e[i].ne
    for (int i = h[u]; ~i; i = e[i].ne)
    {
        int v = e[i].v, w = e[i].w;
        if (v == fa) // 不能往回找
            continue;
        cout << u << " " << v << " " << w << endl; // 访问操作
        dfs(v, u);                                 // 递归
    }
}
void figure()
{
    int n, m, a, b, c;           // n 点数 m 边数
    cin >> n >> m;               
    memset(h, -1, sizeof h);     // 初始化为-1
    for (int i = 1; i <= m; i++) // 输入边
    {
        cin >> a >> b >> c; // a、b两顶点，c表示权值
        add(a, b, c);
        add(b, a, c);
    }
    dfs(1, 0); // 根节点开始dfs
    return;
}

搜索

深度优先搜索（DFS） 广度优先搜索（BFS）
实现 系统栈 队列
搜索顺序 一搜到底 逐层扩展
触碰点的时机 多次：入、下、回、离 两次：入队、出队
时间复杂度 不回溯 $O(n+m)$ ，回溯 $O(指数级)$ $O(n+m)$
连通性问题 适合 适合
方案数问题 适合 不适合
最少步数问题 不适合 适合

深度优先搜索（DFS）

语句时机

一般情况：进入时机、下走时机、上回时机、离开时机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 510, M = 3000; // N 最大点数 M 最大边数
// 链式邻接表
vector<int> h[N]; // 点的所有出边
void dfs(int u, int fa)
{
    // 进入时机
    for (auto v : h[u])
    {
        if (v == fa)
            continue;
        // 下走时机
        dfs(v, u);
        // 上回时机
    }
    // 离开时机
}

退化：二叉树的先、中、后序遍历——线段树

1
2
3
4
5
6
7
8
void dfs(int u)
{
    // 先序
    dfs(2 * u); // 左儿子
    // 中序
    dfs(2 * u + 1); // 右儿子
    // 后序
}

再退化：一条链入、离——并查集

1
2
3
4
5
6
7
8
const int N = 1e5;
int next[N] = {0};
void dfs(int u)
{
    // 入
    dfs(next[u]);
    // 离
}

图的DFS树

图经过一次DFS访问所生成的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 链式邻接表
const int N = 500;
int vis[N];       // 是否被访问
vector<int> e[N]; // 邻接表

void dfs(int u)
{
    vis[u] = true; // 多增加了标记，防止环无限访问
    for (auto v : e[u])
    {
        if (vis[v])
            continue;
        // printf("%d→%d\n",u,v);
        dfs(v);
    }
}

DFS与回溯

题目：洛谷 P1605 迷宫 ，洛谷 P1644 跳马问题 洛谷 P1219 八皇后

偏移量 $dx,dy$ ；

回溯：锁定已走状态，局部递归完成，释放状态

广度优先搜索（BFS）

性质：先入队，必定先出队，满足二段性（队列中最多同时有两层节点）

语句时机

入队时机、出队时机

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
const int N = 100010;
vector<int> e[N]; // 边
int vis[N];       // 是否访问标记
queue<int> q;     // 队列

void bfs()
{
    vis[1] = 1;
    q.push(1);
    while (q.size()) // 队列元素是否为空
    {
        int x = q.front();
        q.pop();
        // 出队时机
        for (auto y : e[x]) // 遍历与x的相连的边，找出它的儿子
        {
            if (vis[y]) // 已经访问过，代表是父亲（？
                continue;
            vis[y] = 1;
            q.push(y);
            // 入队时机
        }
    }
    // 整体结束时机
}

图的BFS树

图经过一次BFS访问所生成的树

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
const int N = 100010;
vector<int> e[N]; // 边
int vis[N];       // 是否访问标记
queue<int> q;     // 队列

void bfs(int s)
{
    // 和上面主要是最开始不一样
    vis[s] = 1;
    q.push(s);
    while (q.size()) // 队列元素是否为空
    {
        int x = q.front();
        q.pop();
        // 出队时机
        for (auto y : e[x]) // 遍历与x的相连的边，找出它的儿子
        {
            if (vis[y]) // 已经访问过，代表是父亲（？
                continue;
            vis[y] = 1;
            q.push(y);
            // 入队时机
        }
    }
    // 整体结束时机
}

DFS

迷宫 方案数

给定一个 $N \times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 $N,M,T$，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 $SX,SY,FX,FY$，$SX,SY$ 代表起点坐标，$FX,FY$ 代表终点坐标。

接下来 $T$ 行，每行两个正整数，表示障碍点的坐标。

对于 $100%$ 的数据，$1 \le N,M \le 5$，$1 \le T \le 10$，$1 \le SX,FX \le n$，$1 \le SY,FY \le m$。

输出格式

输出从起点坐标到终点坐标的方案总数。

代码

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
const int N = 5005;
int a[N][N] = {0};         // 地图
int sx, sy, fx, fy;        // 起点坐标
int ans = 0;               // 总数
int n, m, t;               // n*m的迷宫，t个障碍物
int dx[4] = {-1, 0, 1, 0}; // 偏移量
int dy[4] = {0, 1, 0, -1}; // 偏移量
void dfs(int x, int y)
{
    if (x == fx && y == fy) // 已经到终点
    {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) // 四维偏移
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy < 1 || yy > m)
            continue;
        if (a[xx][yy] == 1) // 地方为障碍物或者走过了
            continue;
        // 正常可走，锁定现在所在地
        a[xx][yy] = 1;
        dfs(xx, yy);   // 递归下一个块
        a[xx][yy] = 0; // 恢复
    }
}
signed main()
{
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;
    a[sx][sy] = 1; // 起点设置为1
    int mx, my;
    for (int i = 0; i < t; i++)
        cin >> mx >> my, a[mx][my] = 1;
    dfs(sx, sy);
    cout << ans << endl;
}

八皇后

image-20230916150508439 image-20230916150629738 
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
const int N = 100;
int n;
int pos[N];
int c[N];
int p[N];
int q[N];
int ans;
void print()
{
    if (ans <= 3)
    {
        for (int i = 1; i <= n; i++)
        {
            cout << pos[i] << " ";
        }
        cout << endl;
    }
}
void dfs(int i)
{
    if (i > n)
    {
        ans++;
        print();
        return;
    }
    for (int j = 1; j <= n; j++)
    {
        if (c[j] || p[i + j] || q[i - j + n]) // 行、列、对角线已经有了
            continue;
        pos[i] = j;                         // 记录第i行放在了第j列
        c[j] = p[i + j] = q[i - j + n] = 1; // 宣布占领
        dfs(i + 1);
        c[j] = p[j + i] = q[i - j + n] = 0; // 恢复现场
    }
}
signed main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;
}