数据结构与算法 PART 2
breayhing / SIRI Lv2
  2023-03-10 17:03:10 2023-03-10 17:03   2023-03-10 17:04:43    15.9k 字  70 分钟

数据结构与算法：PART 2

搜索与图论

查找中静态与动态差异仅在于是否可以动态增删元素

动态查找在几何计算上应用广泛

搜索种类：

无信息搜索：

1.DFS：递归结束条件的选择+状态标记+递归后的恢复(也可以用栈来搭建出来)
2.BFS：模拟队列 q[N], d[N] 使用d数组标记状态
3.搜索：解空间的搜索往往需要dfs+剪枝，bfs用来找最短路
4.树和图的存储：邻接表 h[N], e[N], ne[N], idx
5.树和图的遍历：遍历不用像搜索解空间一样递归后恢复，只用遍历一次即可

有信息搜索：

A搜索算法

建立搜索模型：
image image

DFS

优势：可以获取子树的大小
核心：顺序

842. 排列数字 - AcWing题库

DFS人称暴力搜索，对应的是一个多叉树的形式，DFS的搜索顺序和前序遍历其实一样，但是实际上存储结构只会存一条路径，回溯的时候就会消失，不需要真正建立树，但是一定要注意恢复现场

![深度优先遍历.png](D:\typora note\55289_0cd4222d73-深度优先遍历.png)

举例：全排列做法，使用回溯（还可以使用剪枝）

全排列做法：

时间复杂度为 O(n*n!)。

空间复杂度为 O(n)。

算法：

  1. 用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。\
  2. 用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
  3. dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
  4. 回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。
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
#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++)//这里就是选择如何遍历，想反方向就是逆序遍历了
        //空位上可以选择的数字为:1 ~ n
    {//关键在这里
        /*
        比如123
        回溯到1，state[2]=0,2又可以用，但循环走到了2，到3了，因此是132
        */
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯，取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);//从1开始
    }
DFS另一种应用：皇后位置

c++直接完整版本代码：（LeetCode 版本）

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
class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋牌的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {//回溯到最后一行，说明满足情况了
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);//再进一行进行检验
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    int count = 0;
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {//另一个剪支
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);//注意这里是从0开始的，所以最后到n，实际上以及对n层进行了判断
        return result;
    }
};

/*总结操作流程：
类似二叉树，对每个节点进行遍历，实际复杂度是n^2，从开头一直向下延申，可满足情况进行返回

c++数组版本皇后问题:老子自己写的！（双手叉腰）

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<vector>
using namespace std;
const int maxn=9;
int solu[maxn]={0};
int qn[maxn]={0};
bool isValid(int posj,int posi)//最后那个pos也就是棋子的坐标
{
    //posi=i,posj=qn[i]
    if(posi==0)return true;
    for(int i=0;i<posi;i++)
    {
        if(qn[i]==posj)return false;//相同的列判断
    }
    for(int i=posi-1;i>=0;i--)//45判断
    {
        if(posi-i==posj-qn[i])return false;
    }
    for(int i=posi-1;i>=0;i--)//135
    {
        if(posi-i==qn[i]-posj)return false;
    }
    return true;
}
void backtracing(int n,int row)
{
    if(row==n){//终止了，找到了其中一种解决方案
        cout<<"bottom reached\n";
        cout<<"solution:\n";
        for(int  i=0;i<n;i++)
        {
            cout<<"row "<<i+1<<" equals to "<<qn[i]+1<<" \n";
        }
        cout<<"go find other solution\n\n";
        return;
    }
    else{
        for(int i=0;i<n;i++)//注意这里的传参
        {
            qn[row]=i;//row，行固定，列用变量i对每一行进行遍历，如果满足之前条件进入下一行
            if(isValid(qn[row],row))//该行该位置能否放
            {

                backtracing(n,row+1);//可以就继续往下走

            }
        }
    }

}

int main()
{
    int n;

    cin>>n;
    backtracing(n,0);
}

BFS（使用二维数组）

原因：宽搜的性质：辐射性向外搜索（想想一层一层向外扩张的信号）

844. 走迷宫 - AcWing题库

注意：
  1. dp问题和最短路问题其实是互通的
  2. 边的权重都是1的时候才可以使用BFS求最短路，一般都用最短路
  3. dp问题不能用最短路算法（最短路时间一般都高)
  4. 第一次搜到的点才是最短的点，之后的都不是

不同于深搜，宽搜一般有一个框架

image
广搜的框架
  1. 初始状态放到队列中
  2. 写一个while循环，只要队列不空，在循环内每一次拿出队头，扩展队头

往上下左右扩展的技巧：使用向量来表示

代码（如该道题）
  • void bfs(int a, int b): 广度优遍历函数。输入的是起点坐标。
  • queue q;:用来存储每一步走到的点。
  • while(!q.empty())循环：循环依次取出同一步数能走到的点，再往前走一步。
  • int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 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
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N];//存储地图
int f[N][N];//存储距离
int n, m;
void bfs(int a, int b)//广度优先遍历
{
    queue<PII> q;
    q.push({a, b});//压入队列
    while(!q.empty())
    {
        PII start = q.front();
        q.pop();
        g[start.first][start.second] = 1;
        int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
        for(int i = 0; i < 4; i++)//往四个方向走
        {
            int x = start.first + dx[i], y = start.second + dy[i];//走出一步之后
            if(g[x][y] == 0)//如果还没有走过
            {
                g[x][y] = 1;//该点进行更新,因为广搜中第一次遇到的就是最短路径
                f[x][y] = f[start.first][start.second] + 1;//从当前点走过去，则距离等于当前点的距离+1.
                q.push({x, y});//再入栈一个
            }

        }
    }
    cout << f[n][m];
}

int main()
{
    memset(g, 1, sizeof(g));
    cin >> n >>m;
    for(int i = 1; i <= n; i++)//对地图进行一个更新
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
        }
    }
    bfs(1,1);//对起点进行bfs

}

树和图的DFS，BFS

树和图的DFS，BFS就是特殊的搜索（因为有那个环）

树和图的遍历时间复杂度都是o（n+m）

树与图的存储选择

稠密图：邻接矩阵

稀疏图：邻接表

无向图实际上就是有向图进行一个对称

有向图的存储方式

邻接矩阵：

同BFS，开二维数组存就完事了

优化：使用vector向量

1
2
3
4
5
6
7
8
9
int V,num;
   cin>>V>>num;//V边数量
   vector<vector<int>> graph(V);
   vector<vector<int>> price(V);//记录权值
   for(int i=0;i<V;i++)
   {
       graph[i].resize(V);
       price[i].resize(V);
   }
邻接表：

使用数组模拟链表（还是注意idx的作用类似于分配器）,有多少个点开多少个单链表

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
//这个的不好的地方是不好统计哪些地方已经走过和

#include<cstring>//memset位置
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
//h存链表头，e存每一个节点的值，ne存每一个节点的下一个节点的地址，与单链表的不同就是把head换成h数组

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx  ;
    idx++;//是你熟悉的头插
}
void add_to_tail(int x)//尾插
{
    e[idx]=x;
    if(head==-1//当是第一次插入时特殊处理
    {
        ne[idx]=head;
        head=idx;
        idx++;
        return;
    }
    int i=head;
    if(head!=-1)while(ne[i]!=-1)i=ne[i];//最后ne[i]=-1
    ne[idx]=-1;
    ne[i]=idx;
    idx++;
}
void dele(int a,int b)
{
    	if(e[h[a]]==b)h[a]=ne[h[a]];//如果在第一个元素的时候的操作方法
       else	for(int i=h[a];ne[i]!=-1;i=ne[i])
       {
       	if(e[ne[i]]==b)//这里关系是
       	{
      		ne[i]=ne[ne[i]];
      	}
      }
    
}
bool find(int a,int b)
{
    for(int i=h[a],i!=-1;i=ne[i])
    {
        if(e[i]==b)return true;
    }
    return false;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);//单链表的n个头节点全部变成-1

另一种选择：使用vector+list来构建（很方便）

树图DFS
模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
这个模板同样是使用邻接表来存储的

bool st[N];//同其它，st数组在一开始开好，用来表示该节点是否被遍历过
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    这里是要对DFS进行的操作部分
    
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);//递归进行向下遍历
    }
}

846. 树的重心 - AcWing题库

树的重心可能不唯一，但是树是唯一的

该题解法：遍历删掉所有点之后连通块的最大值，之后在一堆最大值里面对比寻找出来最小的就行

发现：获取了子树的大小也就获得了剩余树的大小（即全部节点数量减去子树的size就好）

image

本题的本质是树的dfs， 每次dfs可以确定以u为重心的最大连通块的节点数，并且更新一下ans。

也就是说，dfs并不直接返回答案，而是在每次更新中迭代一次答案。

这样的套路会经常用到，在 树的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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //在最大连通块中寻找最小的那一个

bool st[N]; //记录节点是否被访问过，访问过则标记为true

//a所对应的单链表中插入b  a作为根 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点
    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {//链表的遍历
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {// u节点的单棵子树节点数 如图中的size值
            int s = dfs(j);  //获取j为根的子树中节点个数
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数，也就是1+s
        }//每一次这样执行一遍就进行了一个节点的更新
    }
    //n-sum 如图中的n-size值；
    res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
    return sum;//返回子树的节点个数
}

int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin >> n; //表示树的结点数

    // 题目接下来会输入，n-1行数据，
    // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }

    dfs(1); //可以任意选定一个节点开始 u<=n

    cout << ans << endl;

    return 0;
}
树图BFS

思想：从1开始不断扩展一层节点，然后不断向下辐射

自闭环在dp问题中及逆行讨论

模板：
  1. 初始状态放到队列中
  2. 写一个while循环，只要队列不空，在循环内每一次拿出队头，扩展队头的所有邻点
  3. 只考虑第一次遍历，只要没有被遍历过，将x入队
  4. 更新路径距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//使用邻接表进行存储稀疏图
int ne[N],e[N],h[N];

queue<int> q;
bool st[N];//同其它，st数组在一开始开好，用来表示该节点是否被遍历过
st[1] = true; // 表示1号点已经被遍历过
q.push(1);//对1进行入队
while (q.size())
{
    int t = q.front();//t是队头
    q.pop();//出队

    for (int i = h[t]; i != -1; i = ne[i])//这里对该头能到达的所有点进行一次访问
    {
        int j = e[i];//j也就是对应的节点的值
        if (!st[j])//只要没有访问过
        {
            该干嘛干嘛，进行需要的操作
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);//入队
        }
    }
}

847. 图中点的层次 - AcWing题库

该题答案：

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
#include <cstring>
#include <iostream>

using namespace std;

const int N=1e5+10;

int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离  d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点

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

int bfs()
{
    int hh=0,tt=0;

    q[0]=1; //0号节点是编号为1的节点

    memset(d,-1,sizeof d);

    d[1]=0; //存储每个节点离起点的距离

    //当我们的队列不为空时
    while(hh<=tt)//不同的是这里用了数组模拟队列，一个道理
    {
        //取出队列头部节点
        int t=q[hh++];

        //遍历t节点的每一个邻边
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //如果j没有被扩展过
            if(d[j]==-1)
            {
                d[j]=d[t]+1; //d[j]存储j节点离起点的距离，并标记为访问过
                q[++tt] = j; //把j结点 压入队列
            }
        }
    }

    return d[n];//因为题目要求第一个点到第n个点就ok
}

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

    cout<<bfs()<<endl;
}

一致代价BFS：改进版本BFS

image

拓扑排序：BFS的一种应用（AOV网，流程能否正确执行）

拓扑、dfs、并查集都可以图中判断有没有环， floyd可以找最小环

仅针对有向图，无向图没得拓扑

定义：每条边都是起点在终点的前面，即所有的边都是从前指向后面的

image

这种算一个拓扑

image

这种就不算了（有一个环，只要有环就一定木大）

可以证明：有向无环一定可以整成一个拓扑图

如何进行一个求

一个有向图有入度和出度，由所有都是从前指向后，则所有入度为0的点都可以排在当前最前面的位置

  • 一个无环图一定至少存在一个入度为0的点
  • 有向无环的top序不唯一
思路：
  1. 所有入度为0的点进行入队
  2. 进行一个BFS，每一次出队一个队头，然后找出所有出队列这个点发出的边，删除边，同时边的另一侧的点的入度 -1。
  3. 如果d[j]==0,说明j之前的都排序好了，入队j就完事了
  4. 如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。
模板：
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
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    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];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

848. 有向图的拓扑序列 - AcWing题库

AcWing 848. $\color{green}{拓扑排序–思路介绍+图解模拟+详细代码注释 }$ - AcWing

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];//邻接表表头
int q[N], hh = 0, tt = -1;//队列保存入度为0的点，也就是能够输出的点，
int n, m;//保存图的点数和边数
int d[N];////保存各个点的入度

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;//邻接表的创建
}

void topsort(){
    for(int i = 1; i <= n; i++){//遍历一遍顶点的入度。
        if(d[i] == 0)//如果入度为 0, 则可以入队列
            q[++tt] = i;
    }//tt头，hh尾
    while(tt >= hh){//循环处理队列中点的
        int a = q[hh++];//取出队头元素
        for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边
            int b = e[i];//a 有一条边指向b
            d[b]--;//删除边后，b的入度减1
            if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出，入队列
                q[++tt] = b;
        }
    }
    if(tt == n - 1){//进去了n个点
        //如果队列中的点的个数与图中点的个数相同，则可以进行拓扑排序
        for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点，依次输出
            cout << q[i] << " ";
        }
    }
    else//如果队列中的点的个数与图中点的个数不相同，则不可以进行拓扑排序
        cout << -1;//输出-1，代表错误
}


int main(){
    cin >> n >> m;//保存点的个数和边的个数
    memset(h, -1, sizeof h);//初始化邻接矩阵
    while (m -- ){//依次读入边
        int a, b;
        cin >> a >> b;
        d[b]++;//顶点b的入度+1
        add(a, b);//添加到邻接矩阵
    }
    topsort();//进行拓扑排序
    return 0;
}

动态查找：二叉搜索树

构建树：每个左孩子都比双亲小，每个右孩子都比双亲大

插入节点：
删除节点
叶子节点

直接删除

节点p仅有一棵子树：

• 直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即原来p是f的左子树，则p的子树成为f的左子树；原来p是f的右子树，则p的子树成为f的右子树

即类似链表的删除操作（懂得都懂）

节点p既有左子树又有右子树：
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
76
77
#include<iostream>
#include <string>
using namespace std;
const int M=1024;
int tree[M]={0};
int char_to_int(char a)
{
    return (int)(a-'0');
}
void add_tree(int tree[],string a,int str_pos,int tree_pos,int judge)
{
    int length=a.size();
    if(str_pos>length)return;
    int num=char_to_int(a[str_pos]);
    if(tree[tree_pos]==-1)//新节点插入
    {
        tree[tree_pos]=num;
        judge=0;
        return;
    }
    else if(num>=tree[tree_pos])tree_pos=2*tree_pos+1;//大，向右边搜索
    else tree_pos=2*tree_pos;//小,向左边搜索
    add_tree(tree,a,str_pos,tree_pos,judge);
}
int main()
{
    int n;
    cin>>n;
    string ans;
    cin>>ans;//初始化的输入
    int total=ans.size();
    for(int i=1;i<=M;i++)
    {
        tree[i]=-1;//-1表示是空指针
    }
    tree[1]=char_to_int(ans[0]);
    for(int i=1;i<total;i++)//开始对树进行节点插入
    {
        add_tree(tree,ans,i,1,1);
    }
//    cout<<"origin tree:  ";
//    for(int i=1;i<=M;i++) {
//        if (tree[i] != -1)cout << tree[i] << ' ';
//    }
    cout<<endl;
    int str_com[M];
    string str_a;
    for(int time=0;time<n;time++)//循环多少次
    {
        if(time==6)break;
        for(int i=1;i<=M;i++)
        {
            str_com[i]=-1;//进行初始化
        }
        cin>>str_a;//新的输入
        str_com[1]=char_to_int(str_a[0]);
        for(int i=1;i<total;i++)//开始对树进行节点插入
        {
            add_tree(str_com,str_a,i,1,1);
        }
        int judge=1;
//        cout<<"new tree:  ";
        for(int i=1;i<=M;i++) {
            if(str_com[i]!=tree[i])
            {
                cout<<"NO\n";
                judge=0;
                break;
            }
//            if (str_com[i] != -1)cout << str_com[i] << ' ';
        }
        if(judge==1)cout<<"YES\n";
    }
    int time;
    cin>>time;
    return 0;
}
动态查找：kd树（图形相关的东西会涉及，很重要的一种数据结构）🙏

空间划分树：

  • 网格
  • 四叉树
  • 二维树
  • 二叉空间分割树

二维树：最近邻查找

实际就使用了剪枝（即切除不可能的子树）

最短路问题

朴素Dijkstra算法(和堆有关)（面试也有）

书的作者写的算法通常都很长

与bf算法最大区别：所有边只松弛一次（bf每条边多次）（这里很有可能数据结构考）

image

堆优化：Dijkstra

应用场景：（什么时候使用该算法）
  • 计算机网络中网络传输问题（参考ele实验室路由器）与协议
  • 迷宫问题（往下看图形化篇章）

核心思想：贪心

迪杰斯特拉算法适用于求正权有向图中，源点到其余各个节点的最短路径。注意：图中可以有环，但不能有负权边。

思路：

s:当前已经确定最短距离的点

  1. 初始化距离（只有起点的距离是确定的）
  2. 开始循环迭代n次，找到不在s中的距离最近的点
  3. 用 t来更新其它所有点的距离（就能更新起点到每个点最短距离）
模板：（朴素版本的Dijkstra）复杂度：n^2

849. Dijkstra求最短路 I - AcWing题库

AcWing 849. Dijkstra求最短路 I：图解 详细代码（图解） - AcWing

注意这里读入都是从1开始

dist注意初始化为+∞

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
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
const int INF=0x3f;//用于标注是无穷点
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    
    memset(dist, 0x3f, sizeof dist);//所有距离初始化成正无穷
    dist[1] = 0;//起点到起点当然是0力

    for (int i = 0; i < n - 1; i ++ )//这里i不重要，只知道需要循环n-1次就行（）
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            {
            	if (!st[j] && (t == -1 || dist[t] > dist[j]))//如果没有确定最短路或者当前路不是最短的
                {t = j;}//把t给更新，头个节点在第一步这里变成0
            }
想想dijkstra的步骤，每一次都是先找到所有里面最近的点
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            {使用一开始寻找到的点逐个遍历所有其它可以到达的点进行比较并更新
            	dist[j] = min(dist[j], dist[t] + g[t][j]);//再次遍历一次所有
        	}

        st[t] = true;//将那一个点标记为已经访问并且
    }

    if (dist[n] == 0x3f3f3f3f) return -1;//说明1和n不联通
    return dist[n];//起点到终点的距离
}


//这里是读入的时候，注意注意要从1开始
for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int tem;
            cin>>tem;
            if(tem==0)g[i][j]=INF;
            else g[i][j]=tem;
        }
    }

对于该题有重边和自环，因此需要考虑一下处理

  • 多重边仅保留路径最短的那一条
  • 自环肯定不会被纳入最短路，可以不考虑
修改（任意一个点到其它所有点）
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>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=60;
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中，存储已纳入的集合
void dijkstra(int s)//s是源点，其它都不重要
{
    s=s+1;
    memset(dist, 0x3f3f3f3f, sizeof dist);//所有距离初始化成正无穷
    dist[s] = 0;//起点到起点当然是0力
    for (int i = 0; i < n - 1; i ++ )//这里i不重要，只知道需要循环n-1次就行（）
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))//如果没有确定最短路或者当前路不是最短的
                t = j;//把t给更新，头个节点在第一步这里变成0
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);//再次遍历一次所有
        st[t] = true;
    }
    for(int i=1;i<=n;i++)//这里就是最后的输出部分
    {
        if(i!=s&&dist[i]!=0x3f3f3f3f)cout<<dist[i]<<' ';
        else if(i!=s&&dist[i]==0x3f3f3f3f)cout<<-1<<' ';
    }
}
int main()
{
    int s;//s标记源点
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int tem;
            cin>>tem;
            if(tem==0)g[i][j]=INF;
            else g[i][j]=tem;
        }
    }
    dijkstra(s);

}
题目模板
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 <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;
const int inf = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool vis[N];


int dijkstra()
{
    memset(vis, 0, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    for(int i = 1; i <= n; i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
        {
            if(!vis[j] && (t == -1 || dist[j] < dist[t]))
            {
                t = j;
            }
        }
        
        vis[t] = 1;
        for(int j = 1; j <= n; j ++ )
        {
            if(dist[j] > g[t][j] + dist[t])
            {
                dist[j] = g[t][j] + dist[t];
            }
        }
    }
    if(dist[n] * 2> inf)
    {
        return -1;
    }
    return dist[n];
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int in, out, weight;
        cin >> in >> out >> weight;
        g[in][out] = min(g[in][out], weight);
    }
    
    cout << dijkstra() << "\n";
    return 0;
}
模板：（优化版本的Dijkstra）

实际有点像广搜的

如果是一个稀疏图，但是还要用遍历矩阵（n2复杂度）容易时间爆掉

使用小根堆优化

image

也就是可以优化第一步，可以将第一步时间变成o1，第三步就要修改成mlogn，第二步不变

即通过堆来存储，就可以减少计算量

堆的实现方式：

  • 手写堆（好处在于方便维护）
  • 优先队列（c++的stl库已经预置好了），但是不支持修改任意一个元素，解决思路：每一次改变就插入一个新的数（好处方便操作，坏处会多了操作数，时间复杂度变成mlogm，但是方便，）

因此直接使用c++内置的优先队列就ok

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
typedef pair<int, int> PII;
//存储方式从邻接矩阵转换成邻接表
int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;//这里的初始化和朴素版本是一样的
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;//这里使用优先队列维护所有距离，
    heap.push({0, 1});      //第一次先把起点放进去，
    // first存储距离，second存储节点编号

    while (heap.size())//队列里面最多只有m个元素（最多只有m条边）
    {
        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];//使用j来存储编号
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});//如果更新成功就把这个点放到队列里面去
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

全部：

有关优先队列库的函数：

(110条消息) 【C++】优先队列详细讲解（原理+STL库调用）_半路杀出来的小黑同学的博客-CSDN博客_c++ 优先队列遍历

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
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的头文件

using namespace std;

typedef pair<int, int> PII;//堆里存储距离和节点编号

const int N = 1e6 + 10;

int n, m;//节点数量和边数
int h[N], w[N], e[N], ne[N], idx;//邻接表存储图
int dist[N];//存储距离
bool st[N];//存储状态

void add(int a, int b, int c)//修改了一下add函数
{//w存储距离
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大
    dist[1] = 0;
    //pair的比较，先比较第一个元素，第一个相等比较第二个。
    priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
    heap.push({0, 1});//插入距离和节点编号

    while (heap.size())//遍历了这个堆
    {
        auto t = heap.top();//取距离源点最近的点，最小的
        heap.pop();

        int ver = t.second, distance = t.first;//ver:节点编号，distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定，则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//这里是链表的遍历方法
            //更新ver所指向的节点距离
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});//距离变小，则入堆
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}


Bellman-Ford算法（bf算法）

复杂度通常为o（VE）

会多次访问同一条边

解决问题：
  • 可能有负边回路，Dijkstra如果判断的图中有负会导致距离成正无穷
  • 部分只能使用bf解决（如果有边数限制，就只能用bf）

很牛逼：可以用任意存储方式，也可以用结构体

应用：比如坐火车不能无限坐火车

思路：

  • 两重循环，第二次循环所有边

  • n次迭代，更新思路有点类似dijistra

可以判断是否存在负回路,即是可以用来找负环（如果限制了走的边的个数就可以用来找最短路）的，但时间较高，一般使用spfa寻找负环

模板：
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
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
            //正常的模板是自身进行迭代对比的
        }
    }
//这里注意要/2是因为如果有负边到达终点会造成距离不满足，如10^9−2，小于无穷，但仍然并不存在最短路 
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

AcWing 853. 有边数限制的最短路 - AcWing

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
#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {//使用结构体来存储所有的边
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);//每一次迭代之前都要对当前数组进行备份，防止出现串联使得打破有限边数的限制
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else return dist[n];

}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");//说明最短路长度不存在
    else cout << res;

    return 0;
}

spfa(队列优化版本的Bellman-Ford)

处理稀疏图，使用邻接表进行存储

可以视为各方面都更加优秀的bf，就是对于bf进行一个优化

AcWing 851. spfa求最短路—图解–$\color{red}{海绵宝宝来喽}$ - AcWing

其实正权图也可以用spfa去整

bf缺点：每一次都要迭代所有边进行更新（每一次都要全部扫描）

优化：使用广搜进行优化

思路：

  • 起点放到队列里面去
  • 只要队列不空，就是广搜的迭代操作
  • 即我更新过谁，我再用谁去更新别人，我后面的人才会更小

图中一定不能有负环(但是可以有负权边)，不然不能用

时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，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
39
40
41
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;  // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中，防止队列中存储重复点

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);//初始化所有点的距离
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;
//使用队列就是为了如起点更新过bc，则下一步仅针对bc进行更新
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;//该点不在队列里面

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])//如果可以更新
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     
                    // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

851. spfa求最短路 - AcWing题库

spfa判断是否存在负环

时间复杂度是 O(nm), n 表示点数，m 表示边数

原理：使用dist数组表示1号数组到其它数组的距离，使用cnt表示当前最短路的边数

模板：
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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];       
// dist[x]存储1号点到x的最短距离，
//cnt[x]存储1到x的最短路中经过的点数
//每一次更新表示
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);//这里不同在于要全部入对保证每个点都能进行判断
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;//更新的时候同步更新边数
                if (cnt[j] >= n) return true; 
 // 如果从1号点到x的最短路中包含至少n个边（抽屉原理），则说明存在环
 //这个环一定是个负环（因为spfa选择短的路，为了走短还多走一个点一定是存在负环）
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}
FLOYID算法（Dijkstra进一步输出全部）

很简单，针对所有路

原理：动态规划

d[k,i,j]，从i点出发，经过k个点，最终到达j点

那么有d[k,i,j]=d[k-1,i,k]+d[k-1,k,j]//右边各经过了k-1个点

可以优化，去掉一维，即d[i,j]=d[i,k]=d[k,j]

应用：

可以对有负边进行操作（但是不能有负回路）

FLOYID可以求出所有点之间的最短路径（很暴力很牛逼很简洁很费时）

使用邻接矩阵存储所有边

模板

时间：n^3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//邻接矩阵初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;//自身到自身为0
            else d[i][j] = INF;



// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

对于求floyid，类似spfa判断无穷情况：

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
#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
int d[N][N];

void floyd() {
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while(m--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        //注意保存最小的边
    }
    floyd();
    while(k--) {
        cin >> x >> y;
        if(d[x][y] > INF/2) puts("impossible");
        //由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}

prim最小生成树

非常非常像dijkstra

处理步骤：

  • 首先全部初始化为+无穷
  • 开始循环迭代，用t更新到集合的距离（dijkstra这里是t更新到起点的距离）
  • st[t]=true（真的真的很像dijkstra）

点到集合的距离指点到集合的所有路径中选择最短的那一条

注意一点 ，这个二维数组要下标是1到n

一次循环只会更新一个最近点

每次更新最近点之后就会在该点可触及范围内更新与其它点的距离

朴素prim模板
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
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离

bool st[N];     // 存储每个点是否已经在生成树中，存储已纳入的集合
const int INF=0x3f

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);//所有距离初始化+∞

    int res = 0;//res存储所有边里面最小生成树的所有边长度之和
    //每一次为了寻找到当前集合外所有点当中距离最小的点
 
    for (int i = 0; i < n; i ++ )//n次迭代
    {
        int t = -1;
        //必须要在集合外，所以从1开始，st
        for (int j = 1; j <= n; j ++ )
            //必须在集合外并且t的距离大于当前点的距离
            {
            	if (!st[j] && (t == -1 || dist[t] > dist[j]))//t==-1是最初始时候的情况
                {
                    t = j;
                }
        	}
        //现在t存的就是当前距离最小的点
        
		//不是第一个点并且距离是+∞
        //说明当前这个图不联通，不存在最小生成树
        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        //否则不是第一条边就把dist加到答案中
        st[t] = true;//说明这一个点已经是树集合的一份子咧

        //对了注意顺序问题哦，一定要先累加再进行更新
        //这一步更新一下其它点到集合的距离，同dijkstra
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        
    }

    return res;
}

858. Prim算法求最小生成树 - AcWing题库

AcWing 858. Prim算法求最小生成树：图解+详细代码注释（带上了保存路径） - AcWing

AcWing 858. $\Huge\color{MediumTurquoise}{prim 与dijkstra的区别}$ - AcWing

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
76
//2022.6.1 更新

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

const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

void prim()
{
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }

        //2022.6.1 发现测试用例加强后，需要判断孤立点了
        //如果孤立点，直返输出不能，然后退出
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }


        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }

    cout << res;

}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    prim();//求最下生成树
    //getPath();//输出路径
    return 0;
}

与Dijkstra类似，Prim算法也可以用堆优化，优先队列代替堆，优化的Prim算法时间复杂度O(mlogn)。适用于稀疏图，但是稀疏图的时候求最小生成树，Kruskal 算法更加实用。

克鲁斯卡尔最小生成树

时间是mlogm，思路也简单（不用考虑prim的）

核心：删除，判断

优点：

  • 稀疏图尽管使用kruskal就ok
  • kruskal也可以处理负权边的哦
  • kruskal同bf算法，对于存储方式不挑剔，能存就行，可以用结构体
  1. 将所有边按照权重从小到大进行排序（这里用原有的排序就行）
  2. 枚举每条边ab（权重是c），如果ab不连通（即在），就将这条边加入到集合里面
  3. 只要边数是节点数-1就ok辽

这里建议参考并查集例题，837题

837. 连通块中点的数量 - AcWing题库

kruskal是使用一个并查集去维护的，堆用于去做dijkstra

AcWing 859. Kruskal算法求最小生成树—$\color{red}{海绵宝宝来喽}$ - AcWing

模板
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
#include<algorithm>//需要引入这个头文件实现对结构体的大小排序操作
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    //下面这里是结构体的另一个函数，重载一下＜
    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];//这里是开了一个结构体数组叫edges,有M个

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);//nlogn

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    //res存最小生成树里边所有边的权重之和
    //cnt存的是当前增加了多少条边
    int res = 0, cnt = 0;
    //这里是从小到大枚举所有边
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        //使用一个并查集来判断两个点是否联通
           // 如果两个连通块不连通，则将这两个连通块合并
         if (a != b) 
        {
            p[a] = b;//这里是两个点的合并操作
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

题：

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int p[N];//保存并查集

struct E{
    int a;
    int b;
    int w;
    bool operator < (const E& rhs){//通过边长进行排序
        return this->w < rhs.w;
    }

}edg[N * 2];
int res = 0;

int n, m;
int cnt = 0;
int find(int a){//并查集找祖宗
    if(p[a] != a) p[a] = find(p[a]);
    return p[a];
}
void klskr(){
    for(int i = 1; i <= m; i++)//依次尝试加入每条边
   {
        int pa = find(edg[i].a)；// a 点所在的集合
        int pb = find(edg[i].b);// b 点所在的集合
        if(pa != pb){//如果 a b 不在一个集合中
            res += edg[i].w;//a b 之间这条边要
            p[pa] = pb;// 合并a b
            cnt ++; // 保留的边数量+1
        }
    }
}
int main()
{

    cin >> n >> m;//同样注意这里是1开始，因此下面sort函数起始也是+1
    for(int i = 1; i <= n; i++) p[i] = i;//初始化并查集
    for(int i = 1; i <= m; i++){//读入每条边
        int a, b , c;
        cin >> a >> b >>c;
        edg[i] = {a, b, c};
    }
    sort(edg + 1, edg + m + 1);//按边长排序
    klskr();//并查集初始化包含在函数中
    if(cnt < n - 1) {//如果保留的边小于点数-1，则不能连通
        cout<< "impossible";
        return 0;
    }
    cout << res;
    return 0;
}

二分图

染色法判定：

使用性质：一个图是二分图当且仅当图中不含奇数环/奇圈

奇数环：环，而且当中边的数量是奇数

时间复杂度是 O(n+m), n 表示点数，m 表示边数

思路：一条边的两个端点一定属于不同的集合，一个联通块中只要一个点的颜色确定，其它点的颜色都确定（白色只能与黑色相邻，黑色只能与白色相邻），由于不存在奇数环，染色过程中一定没有矛盾

因此需要将整个图遍历一遍，由于图没有权，负边，因此可以用dfs，bfs来弄，模板这里使用dfs

因此，如果有矛盾，那肯定就不是了呗

则判定两个关键函数：

  • 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
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
//三色染色法，考虑go语言runtime部分三色标定部分

// 参数：u表示当前节点，c表示当前点的颜色
//这里使用深搜因为相对而言深搜的代码量更少，只用回溯，不需要手写队列
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

随便整一道例题康康：

AcWing 860. 染色法判定二分图—$\color{green}{详细代码注释+图解}$ - AcWing

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 <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 * 2;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int color[N];//保存各个点的颜色，0 未染色，1 是红色，2 是黑色
int n, m;//点和边

void add(int a, int b)//邻接表插入点和边
{
    e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}

bool dfs(int u, int c)//深度优先遍历
{
    color[u] = c;//u的点成 c 染色

    //遍历和 u 相邻的点
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int b = e[i];                   
        if(!color[b])//相邻的点没有颜色,则递归处理这个相邻点
        {
            if(!dfs(b, 3 - c)) return false;//（3 - 1 = 2， 如果 u 的颜色是2，则和 u 相邻的染成 1）
                                            //（3 - 2 = 1， 如果 u 的颜色是1，则和 u 相邻的染成 2）
        }
        else if(color[b] && color[b] != 3 - c)//如果已经染色，判断颜色是否为 3 - c
        {                                     
            return false;//如果不是，说明冲突，返回                   
        }
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表
    cin >> n >> m;
    for(int i = 1; i <= m; i++)//读入边
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for(int i = 1; i <= n; i++)//遍历点
    {
        if(!color[i])//如果没染色
        {
            if(!dfs(i, 1))//染色该点，并递归处理和它相邻的点
            {
                cout << "No" << endl;//出现矛盾，输出NO 
                return 0;
            }

        }
    }
    cout << "Yes" << endl;//全部染色完成，没有矛盾，输出YES
    return 0;
}

匈牙利算法

作用：给定一个二分图，求它的最大匹配（可以在一个较短的时间内匹配）

把它想象成月老匹配对象算法

image

一些概念：

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E}中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数

基本思路：

  • 对于每个男生从前往后看（果然开始当月老看了），如果女生处于单身状态则可以匹配
  • 再看下一个，某个男生匹配某个女生，如果该女生已经被匹配，这个男生也不会善罢甘休（什么黄毛剧情），如果之前匹配的男生a可以更换女生（越来越奇怪了），男生b会与这个女生匹配（他甚至专门用了绿色绝了）

所以很多时候做错是没事的，错过是真的会后悔

image

时间复杂度（n*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
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)//判断能否找到妹子
{//使用枚举
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])//如果妹子之前没有考虑过
        {
            st[j] = true;
            
            //如果妹子之前没有匹配任何男生或者女生匹配的男生可以找到下家
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;//当前妹子匹配就改变了
                return true;
            }
        }
    }

    return false;//就是在匹配不上，那咱就算了
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
//这里是main函数里面的部分
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);//先把所有的妹子清空
    if (find(i)) res ++ ;//如果可以找到的话，成功数量增加
}

AcWing 861. 二分图的最大匹配 - AcWing

AcWing 861. 二分图最大匹配 - 如果你看了别的题解，仍然对递归写法的st数组心存疑虑，看看这里【21.12.7更新】 - AcWing

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<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

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

void init()
{
    memset(h,-1,sizeof h);
}

int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}
int main()
{
    init();
    cin>>n1>>n2>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }


    int res = 0;
    for(int i = 1; i <= n1 ;i ++)
    {  
         //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
          memset(st,false,sizeof st);
        if(find(i)) 
          res++;
    }  

    cout<<res<<endl;
}

关键路径（AOE网，拓扑plus版本）

基础背景知识：

AOE网：AOV网基础上加上每个节点（工序）所消耗的时间

AOE网要建立再活动之间制约关系没有矛盾的基础之上，再来分析完成整个工程需要多少时间，或者为了缩短完成工程所需时间，应当加快哪些活动

关键路径：从源点到汇点具有最大长度的路径：

关键活动：关键路径上的活动（实际上就可以理解成多种活动并行执行，有些耗时最长的活动来衡量整体工程的执行时间）->修改关键活动才会对整个工期长度进行实际减少

核心：寻找关键活动

方法：找到所有活动的最早开始时间和最晚开始时间，并且进行比较，如果相等意味着此活动是关键活动，活动间的路径是关键路径

贪心

与最短路关系：

dp问题可以视为特殊的最短路问题，即最短路包含dp，是一个没有环存在的最短路，dp实际是深搜，保证可以到达终点，但不保证是最短路

暴力搜索

回溯法

回溯法效率：低，但比for强

解决问题：for嵌套无法解决时候

理论基础：来源于递归的回溯(隐藏在递归的下面)，与二叉树遍历，深度优先搜索混在一起进行，二叉树在返回的过程中也用到了回溯

可解决问题：传统for暴力搜索方式无法解决

  • 组合问题：（如一串数字询问可以组合的方式数）组合强调没有顺序
  • 排列问题：排列强调元素顺序
  • 切割问题：（字符串，加上某种限定条件，询问切割方式）
  • 子集问题：找出所有子集
  • 棋盘问题：（典中典皇后，数独)

小总结，用于解决组合和排列

ADT:可以抽象为一个树形结构，可以抽象为一棵n叉树，树的宽度是集合的大小，即每个节点处理的集合的大小->这里通常使用for循环来处理。树的深度（纵方向）也就是递归的深度，

回溯模板
1
2
3
4
5
6
7
8
9
10
11
12
13
void backtracking(参数) {
    if (终止条件) {//终止条件
        存放结果;//一般问题都是在叶子节点收集结果（最后一个节点）
        		//而子集问题每一个节点都要收集结果
        return;//收集完结果之后返回
    }
    for (选择：本层集合中元素（树中节点的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归，这里是深度，向下探索
        回溯，
        撤销处理结果//结束循环
    }
}
棋盘典中点：皇后位置

c++直接完整版本代码：（LeetCode 版本）

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
class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋牌的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {//回溯到最后一行，说明满足情况了
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);//再进一行进行检验
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    int count = 0;
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {//另一个剪支
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);//注意这里是从0开始的，所以最后到n，实际上以及对n层进行了判断
        return result;
    }
};

/*总结操作流程：
类似二叉树，对每个节点进行遍历，实际复杂度是n^2，从开头一直向下延申，可满足情况进行返回

c++数组版本皇后问题:老子自己写的！（双手叉腰）

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<vector>
using namespace std;
const int maxn=9;
int solu[maxn]={0};
int qn[maxn]={0};
bool isValid(int posj,int posi)//最后那个pos也就是棋子的坐标
{
    //posi=i,posj=qn[i]
    if(posi==0)return true;
    for(int i=0;i<posi;i++)
    {
        if(qn[i]==posj)return false;//相同的列判断
    }
    for(int i=posi-1;i>=0;i--)//45判断
    {
        if(posi-i==posj-qn[i])return false;
    }
    for(int i=posi-1;i>=0;i--)//135
    {
        if(posi-i==qn[i]-posj)return false;
    }
    return true;
}
void backtracing(int n,int row)
{
    if(row==n){//终止了，找到了其中一种解决方案
        cout<<"bottom reached\n";
        cout<<"solution:\n";
        for(int  i=0;i<n;i++)
        {
            cout<<"row "<<i+1<<" equals to "<<qn[i]+1<<" \n";
        }
        cout<<"go find other solution\n\n";
        return;
    }
    else{
        for(int i=0;i<n;i++)//注意这里的传参
        {
            qn[row]=i;//row，行固定，列用变量i对每一行进行遍历，如果满足之前条件进入下一行
            if(isValid(qn[row],row))//该行该位置能否放
            {

                backtracing(n,row+1);//可以就继续往下走

            }
        }
    }

}

int main()
{
    int n;

    cin>>n;
    backtracing(n,0);
}

图形化数据结构学习：

栈：非递归汉诺塔

难点：不能使用递归（如果使用递归在画图之前会全部更新完，最后只会给出结果），改成非递归方式

本质：将递归结构在循环中实现

老师解法：

参考博客：(99条消息) 汉诺塔的非递归实现（堆栈）_.别拖至春天.的博客-CSDN博客_汉诺塔的非递归实现

![屏幕截图 2022-10-12 155526](D:\typora note\屏幕截图 2022-10-12 155526.png)

代码以及注释：

ops是空栈，用于保存指令，并且在n==1的时候才进行弹出操作

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
if(!ops.empty()) {
                //
                op current = ops.top();//非空赋值
                ops.pop();//
                if(current.n == 1) {//每一个待处理的物品数量变成1的时候进行弹栈，一直弹到不是1
                    //
                    // 这里的current.start等等已经改变成对应的代号了
                    //

                    int d = stacks[current.start]->top();
                    stacks[current.start]->pop();
                    stacks[current.end]->push(d);
                } else {
                    //这里应该就是正常非递归
                    //如果不是1，进行分解,
                    //如要做到(n,a,b,c),n个从a到c
                    //分解，并且按照顺序进栈（当然弹出的时候就是相反的顺序）
                    //1:(n-1,a,c,b)
                    //2:(1,a,b,c)
                    //3:(n-1,b,a,c)
                    //因为程序执行语言是从上到下，但是指令压栈应该是321，因此最后是321
                    //ops是一个存储指令的栈
                    ops.push(op(current.n - 1, current.via, current.start, current.end));//3
                    ops.push(op(1, current.start, current.via, current.end));//2
                    ops.push(op(current.n - 1, current.start, current.end, current.via));//1
                }
            }

南大关于非递归的应用（对于C语言作为状态机的分析讲解）

image

队列：迷宫生成及解决

重点解决问题：回溯法

顺便要学习的算法：迪杰斯特拉解法（可以等一等再看看）

  1. 1. 数据结构与算法：PART 2
    1. 1.0.1. 搜索与图论
      1. 1.0.1.0.0.1. 搜索种类：
    2. 1.0.1.0.1. 建立搜索模型：
  2. 1.0.1.1. DFS
    1. 1.0.1.1.0.1. 优势：可以获取子树的大小
    2. 1.0.1.1.0.2. 核心：顺序
    3. 1.0.1.1.0.3. 全排列做法：
    4. 1.0.1.1.0.4. DFS另一种应用：皇后位置
  • 1.0.1.2. BFS（使用二维数组）
    1. 1.0.1.2.0.1. 注意：
    2. 1.0.1.2.0.2. 广搜的框架
    3. 1.0.1.2.0.3. 代码（如该道题）
  • 1.0.1.3. 树和图的DFS，BFS
    1. 1.0.1.3.1. 树与图的存储选择
      1. 1.0.1.3.1.1. 邻接矩阵：
      2. 1.0.1.3.1.2. 邻接表：
    2. 1.0.1.3.2. 树图DFS
      1. 1.0.1.3.2.1. 模板：
    3. 1.0.1.3.3. 树图BFS
      1. 1.0.1.3.3.1. 模板：
  • 1.0.1.4. 拓扑排序：BFS的一种应用（AOV网，流程能否正确执行）
    1. 1.0.1.4.0.1. 仅针对有向图，无向图没得拓扑
    2. 1.0.1.4.0.2. 如何进行一个求
    3. 1.0.1.4.0.3. 思路：
    4. 1.0.1.4.0.4. 模板：
  • 1.0.1.5. 动态查找：二叉搜索树
    1. 1.0.1.5.0.1. 插入节点：
  • 1.0.1.5.1. 删除节点
    1. 1.0.1.5.1.1. 叶子节点
    2. 1.0.1.5.1.2. 节点p仅有一棵子树：
    3. 1.0.1.5.1.3. 节点p既有左子树又有右子树：
  • 1.0.1.5.2. 动态查找：kd树（图形相关的东西会涉及，很重要的一种数据结构）🙏
  • 1.0.1.6. 最短路问题
    1. 1.0.1.6.1. 朴素Dijkstra算法(和堆有关)（面试也有）
      1. 1.0.1.6.1.1. 应用场景：（什么时候使用该算法）
      2. 1.0.1.6.1.2. 思路：
      3. 1.0.1.6.1.3. 模板：（朴素版本的Dijkstra）复杂度：n^2
      4. 1.0.1.6.1.4. 修改（任意一个点到其它所有点）
      5. 1.0.1.6.1.5. 题目模板
      6. 1.0.1.6.1.6. 模板：（优化版本的Dijkstra）
    2. 1.0.1.6.2. Bellman-Ford算法（bf算法）
      1. 1.0.1.6.2.1. 解决问题：
      2. 1.0.1.6.2.2. 模板：
    3. 1.0.1.6.3. spfa(队列优化版本的Bellman-Ford)
    4. 1.0.1.6.4. spfa判断是否存在负环
      1. 1.0.1.6.4.1. 模板：
    5. 1.0.1.6.5. FLOYID算法（Dijkstra进一步输出全部）
      1. 1.0.1.6.5.1. 应用：
      2. 1.0.1.6.5.2. 模板
  • 1.0.1.7. prim最小生成树
    1. 1.0.1.7.0.1. 朴素prim模板
  • 1.0.1.8. 克鲁斯卡尔最小生成树
    1. 1.0.1.8.0.1. 模板
  • 1.0.1.9. 二分图
    1. 1.0.1.9.1. 染色法判定：
    2. 1.0.1.9.2. 匈牙利算法
      1. 1.0.1.9.2.1. 模板：
  • 1.0.1.10. 关键路径（AOE网，拓扑plus版本）
    1. 1.0.1.10.0.1. 基础背景知识：
    2. 1.0.1.10.0.2. 核心：寻找关键活动
  • 1.0.2. 贪心
    1. 1.0.2.0.0.1. 与最短路关系：
  • 1.0.3. 暴力搜索
    1. 1.0.3.1. 回溯法
      1. 1.0.3.1.0.1. 解决问题：for嵌套无法解决时候
      2. 1.0.3.1.0.2. 回溯模板
      3. 1.0.3.1.0.3. 棋盘典中点：皇后位置
  • 2. 图形化数据结构学习：
    1. 2.0.1. 栈：非递归汉诺塔
    2. 2.0.2. 队列：迷宫生成及解决