当前位置：首页 > news >正文

搜索与图论

news 来源：原创 2025/8/2 23:01:33

文章目录

搜索与图论
- 深度优先搜索 DFS
- - [843. n-皇后问题 - AcWing题库](https://www.acwing.com/problem/content/845/)
- 宽度优先搜索 BFS
- - [844. 走迷宫 - AcWing题库](https://www.acwing.com/problem/content/description/846/)
- 树与图的存储
- - [846. 树的重心 - AcWing题库](https://www.acwing.com/problem/content/description/848/)
- 树与图的深度优先遍历
- 树与图的宽度优先遍历
- - [847. 图中点的层次 - AcWing题库](https://www.acwing.com/problem/content/849/)
- 拓扑排序
- - 如何求拓扑序
  - - 度：入度和出度
  - [848. 有向图的拓扑序列 - AcWing题库](https://www.acwing.com/problem/content/850/)
  - 题目概述
  - 解题思路
  - - 方法步骤
  - 代码解析
  - 代码解释
  - 复杂度分析
  - 示例输入输出
- 最短路
- - 建图！！！
  - 朴素 Dijkstra
  - - [849. Dijkstra求最短路 I - AcWing题库](https://www.acwing.com/problem/content/851/)
  - 堆优化Dijkstra
  - Bellman_Ford
  - - [853. 有边数限制的最短路 - AcWing题库](https://www.acwing.com/problem/content/855/)
    - - 题目分析
      - 算法思路
      - 关键步骤：
      - 代码解释
      - 复杂度分析
      - 注意事项
  - SPFA
  - - [851. spfa求最短路 - AcWing题库](https://www.acwing.com/problem/content/853/)
    - [852. spfa判断负环 - AcWing题库](https://www.acwing.com/problem/content/854/)
  - Floyd
  - - [854. Floyd求最短路 - AcWing题库](https://www.acwing.com/problem/content/856/)

搜索与图论

		数据结构	空间
DFS	回溯、剪枝	stack	O(h)	不具有最短性		最优性剪枝，不合法剪枝
BFS		queue	O(2^h)	最短路

深度优先搜索 DFS

DFS是一个执着的人会一直尽可能往回走，走到头再回溯，回溯的过程能往前邹尽可能往前走—yxc

顺序，搜索流程是一个树

843. n-皇后问题 - AcWing题库

搜索顺序：

全排列思路：枚举每一行皇后可以放在哪个位置，注意剪枝（提前判断，当前方案不合法直接回溯）O(n*n!)

#include <iostream>using namespace std;
const int N = 20;
int n;
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]);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;
}

每一个位置放和不放O(2ⁿ2)

#include <iostream>using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N], row[N];void dfs(int x, int y, int s)
{if(y == n) y = 0, x ++;if(x == n){if(s == n){for(int i = 0; i < n; i ++) puts(g[i]);puts("");}return;}//不放皇后dfs(x, y + 1, s);//放if(!row[x] && !col[y] && !dg[y + x] && !udg[n + y - x]){g[x][y] = 'Q';row[x] = col[y] = dg[y + x] = udg[n + y - x] = true;dfs(x, y + 1, s + 1);row[x] = col[y] = dg[y + x] = udg[n + y - x] = 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

稳重的人，每一次扩展一层

dp可以理解为特殊的最短路，即没有环的最短路

框架:

844. 走迷宫 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], d[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m;int bfs()
{queue<PII> q;q.push({0, 0});memset(d, -1, sizeof d);d[0][0] = 0;while(!q.empty()){auto t = q.front();q.pop();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.push({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;
}

prv存储从哪个点过来的

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], d[N][N];
PII prv[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m;int bfs()
{queue<PII> q;q.push({0, 0});memset(d, -1, sizeof d);d[0][0] = 0;while(!q.empty()){auto t = q.front();q.pop();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;prv[x][y] = t;q.push({x, y});}}}int x = n - 1, y = m - 1;while(x || y){cout << x << " " << y << endl;auto t = prv[x][y];x = t.first, y = t.second;}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;
}

树与图的存储

树是无环连通图

有向图
无向图（特殊有向图）

邻接矩阵 g[a][b]
邻接表

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int main()
{memset(h, -1, sizeof h);
}

846. 树的重心 - AcWing题库

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

//dfs(u)返回以u为根的树的点的数量
//sum 记录当前u为根的树的大小
// res存删除当前点之后，每个连通块大小的最大值

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
bool st[M];
int n;
int ans = N;//全局答案，最大的最小值void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
//返回以u为根的树的点的数量
int dfs(int u)
{st[u] = true;//已经被搜int sum = 1, res = 0;//sum 记录当前u为根的树的大小// res存删除当前点之后，每个连通块大小的最大值for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];//j存储当前节点对应图的编号if(!st[j]) {int s = dfs(j);//s表示当前子树的大小res = max(res, s);sum += s;}}res = max(res, n - sum);ans = min(ans, res);return sum;
}int main()
{memset(h, -1, sizeof h);cin >> n;for(int i = 1; i <= n - 1; i ++){int a, b;cin >> a >> b;add(a, b);add(b, a);}dfs(1);//随便挑一个点cout << ans << endl;return 0;
}

树与图的深度优先遍历

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
bool st[M];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void dfs(int u)
{st[u] = true;//已经被搜for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];//j存储当前节点对应图的编号if(!st[j]) dfs(j);}}int main()
{memset(h, -1, sizeof h);dfs(1);//随便挑一个点
}

树与图的宽度优先遍历

拓扑排序

有向图才会有拓扑序列，对于每条边，起点在终点前面

有环一定没有拓扑序

可证明有向无环图一定有拓扑图，所以有向无环图也被称为拓扑图

如何求拓扑序

度：入度和出度

所有当前入度为0的点都可以作为起点

入度为零意味着没有任何一条边指向当前点

宽搜过程

题目概述

给定一个有向图，包含 $n$ 个点和 $m$ 条边，可能存在重边和自环。要求输出该图的任意一个拓扑序列，如果不存在拓扑序列（即图中存在环），则输出 $- 1$ 。

解题思路

拓扑排序是针对有向无环图（DAG）的一种线性排序方法，使得对于图中的每一条有向边 $(u, v)$ ， $u$ 在排序中总是位于 $v$ 的前面。如果图中存在环，则无法进行拓扑排序。

方法步骤

计算入度：统计每个节点的入度（即有多少条边指向该节点）。
初始化队列：将所有入度为0的节点加入队列。这些节点没有前置依赖，可以直接作为拓扑序列的起始点。
处理队列：从队列中取出一个节点，将其加入拓扑序列，并移除所有从该节点出发的边（即减少其邻居节点的入度）。如果邻居节点的入度变为0，则将其加入队列。
检查结果：如果拓扑序列包含所有节点，则排序成功；否则，说明图中存在环，无法进行拓扑排序。

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx; // 邻接表存储图
int q[N], d[N]; // q数组模拟队列，d数组存储入度
int n, m;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool topsort() {int hh = 0, tt = -1;// 将所有入度为0的节点加入队列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] --; // 邻居节点的入度减1if(d[j] == 0) // 如果入度为0，加入队列q[++ tt] = j;}}// 如果队列中的节点数等于n，说明拓扑排序成功return tt == n - 1;
}int main() {memset(h, -1, sizeof h); // 初始化邻接表cin >> n >> m;while(m --) {int a, b;cin >> a >> b;d[b] ++; // 更新节点b的入度add(a, b); // 添加边a->b}if(topsort()) {for(int i = 0; i < n; i ++)cout << q[i] << " \n"[i == n];} else {cout << -1 << endl;}return 0;
}

代码解释

邻接表存储图：使用数组模拟邻接表，h数组存储每个节点的头指针，e和ne数组分别存储边的终点和下一条边的索引。
入度数组d：记录每个节点的入度。
add函数：添加一条从a到b的边，并更新b的入度。
topsort函数：
- 初始化队列，将所有入度为0的节点加入队列。
- 处理队列中的节点，减少其邻居节点的入度，如果邻居节点入度为0则加入队列。
- 最后检查队列中的节点数是否等于n，如果是则说明拓扑排序成功。
主函数：读取输入，构建图，调用topsort函数并输出结果。

复杂度分析

时间复杂度： $O (n + m)$ ，每个节点和每条边各处理一次。
空间复杂度： $O (n + m)$ ，存储图结构和队列。

示例输入输出

输入：

输出：

1 2 3

解释：拓扑序列可以是 1 2 3 或 1 3 2，代码输出前者。

最短路

建图！！！

考察抽象成图的过程，即建图的能力

朴素 Dijkstra

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

dist[1] = 0, dist[i] = 0x3f
for(int i = 1 ~ n)
1. t <- 不在s中的距离最近的点
2. s <- t
3. 用t跟新其他点的距离

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

堆优化Dijkstra

在一堆数找最小的数，可以用堆 O(1)

在堆中修改一个数，log(n)

Bellman_Ford

如果有负权回路，最短路不一定存在

for n次 (迭代n次)for 所有边a, b, w //松弛操作dist[b] = min(dist[b], dist[a] + w);dist[b] <= dist[a] + w // 三角不等式

bellmanford 可以用来求负环，时间复杂度较高

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

题目分析

给定一个n个顶点m条边的有向图，图中可能存在重边和自环，边权可能为负数。要求求出从顶点1到顶点n的最多经过k条边的最短路径距离。如果无法到达顶点n，则输出"impossible"。

算法思路

这道题使用Bellman-Ford算法来解决，因为该算法特别适合处理有边数限制的最短路问题。Bellman-Ford算法的基本思想是通过松弛操作逐步逼近最短路径。

关键步骤：

初始化距离数组dist，将所有顶点到起点的距离设为无穷大，起点距离设为0。
进行k次松弛操作，每次操作遍历所有边，尝试通过该边缩短终点到起点的距离。
使用备份数组backup确保每次松弛操作基于上一次迭代的结果，避免"串联更新"。
最终检查终点距离，如果仍大于一个较大值(0x3f3f3f3f/2)，则认为不可达。

代码解释

#include <bits/stdc++.h>
using namespace std;const int N = 550, M = 10010; // 定义顶点和边的最大数量
int n, m, k; // n顶点数，m边数，k边数限制
int dist[N], backup[N]; // dist存储距离，backup用于备份struct Edge {int a, b, w; // 边的起点、终点和权值
} edges[M];void bellman_ford() {memset(dist, 0x3f, sizeof dist); // 初始化距离为无穷大dist[1] = 0; // 起点距离设为0for(int i = 0; i < k; i++) { // 进行k次松弛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); // 松弛操作}}
}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}; // 存储所有边}bellman_ford();// 判断是否可达，注意不是直接比较0x3f3f3f3f因为有负权边if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");else cout << dist[n] << endl;return 0;
}

复杂度分析

时间复杂度：O(k*m)，其中k是边数限制，m是总边数。
空间复杂度：O(n+m)，用于存储距离数组和边集。

注意事项

必须使用backup数组备份上一次的dist状态，避免在同一轮松弛中多次更新导致的错误。
判断不可达的条件是dist[n] > INF/2，而不是dist[n] == INF，因为有负权边可能导致距离略小于INF。
该算法可以检测负权环，但本题有边数限制，所以不需要考虑无限松弛的情况。

SPFA

宽搜优化，队列存所有变小的节点，跟新过谁，再拿他跟新（公司业绩提高才可能加工资

851. spfa求最短路 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], idx, w[N];
int dist[N];
bool st[N];
int n, m;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}void spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while(q.size()){int 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]){q.push(j);st[j] = true;}}}}
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m --){int a, b, c;cin >> a >> b >> c;add(a, b, c);}spfa();if(dist[n] == 0x3f3f3f3f) puts("impossible");else cout << dist[n] << endl;return 0;
}

852. spfa判断负环 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], idx, w[N];
int dist[N];
bool st[N];
int cnt[N];
int n, m;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}bool spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;for(int i = 1; i <= n; i ++){q.push(i);st[i] = true;}while(q.size()){int 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;if(!st[j]){q.push(j);st[j] = true;}}}}return false;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m --){int a, b, c;cin >> a >> b >> c;add(a, b, c);}if(spfa()) puts("Yes");else puts("No");return 0;
}

Floyd

求多源汇最短路

初始化：邻接矩阵存储图 d[i, j]

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

854. Floyd求最短路 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
const int N = 220;
int d[N][N];
int n, m, k;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;memset(d, 0x3f, sizeof d);for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){if(i == j) d[i][j] = 0;}}for(int i = 1; i <= m; i ++){int a, b, w;cin >> a >> b >> w;d[a][b] = min(d[a][b], w);}floyd();while(k --){int a, b;cin >> a >> b;if(d[a][b] > 0x3f3f3f3f / 2) puts("impossible");else cout << d[a][b] << endl;}return 0;
}

文章目录搜索与图论深度优先搜索 DFS[843. n-皇后问题 - AcWing题库](https://www.acwing.com/problem/content/845/) 宽度优先搜索 BFS[844. 走迷宫 - AcWing题库](https://www.acwing.com/problem/content/description/846/) 树与图的存储[846. 树的重心 - AcWing题库](http…...

编程日记 2025/8/2 23:01:33

【递归、搜索和回溯】二叉树中的深搜

个人主页 ： zxctscl 专栏【C】、【C语言】、【Linux】、【数据结构】、【算法】如有转载请先通知文章目录前言1 2331. 计算布尔二叉树的值1.1 分析1.2 代码 2 129. 求根节点到叶节点数字之和2.1 分析2.2 代码 3 814. 二叉树剪枝3.1 分析3.2 代码 4 98. 验证…...

编程日记 2025/7/29 18:32:44

通俗的理解MFC消息机制

1. 消息是什么？ 想象你家的门铃响了（比如有人按门铃、敲门、或者有快递），这些都是“消息”。在 MFC 中，消息就是系统或用户触发的各种事件，比如鼠标点击（WM_LBUTTONDOWN）、键盘输入…...

编程日记 2025/7/31 20:48:17

Windows CMD通过adb检查触摸屏Linux驱动是否被编译

检查 CONFIG_TOUCHSCREEN_GT9XX 是否启用，检查内核是否编译了Goodix GT9XX系列触摸屏的驱动支持 Windows CMD.exe输入： adb shell “zcat /proc/config.gz | grep CONFIG_TOUCHSCREEN_GT9XX” 如果返回CONFIG_TOUCHSCREEN_GT9XXy，表示驱动已编…...

编程日记 2025/7/31 22:07:06

Java并发编程-锁（八）

文章目录 Condition的使用和实现使用add(T t) 实现等待队列await()signal()signalAll() 总结 Condition的使用和实现我们知道，任意一个Java Object，都拥有一组监视器方法，主要包括wait()、 wait(long timeout)、notify()以及notifyAll()方法…...

编程日记 2025/7/31 23:23:32

idea如何快速生成测试类

点击 code -> generate -> Test...

编程日记 2025/7/31 4:58:08

FPGA笔试题review

今天翻网盘上的旧资料，找到了一套20年9月份在武汉某芯片公司食堂做的笔试题（我在做笔试题，旁边的人在嗦酸辣粉，也算是记忆犹新），借着这套题目，正好也可以捡一捡关于FPGA的基础知识点，算是温故而知新。答案更新中 1、名词解释（1）FPGA、ASIC （2）CLB、LUT （3）时…...

编程日记 2025/8/1 7:23:34

[C++类和对象]构造函数和析构函数

类的6个默认成员函数如果一个类中什么成员都没有，简称为空类。空类中真的什么都没有吗？ 并不是，任何类在什么都不写时，编译器会自动生成以下6 个默认成员函数。默认成员函数：用户没有显式实现，编译器会…...

编程日记 2025/7/29 18:32:26

Java【网络原理】（5）深入浅出HTTPS：状态码与SSL/TLS加密全解析

目录 1.前言 2.正文 2.1状态码 2.2HTTP与HTTPS的关系 2.3SSL协议 2.3.1对称加密 2.3.2非对称加密 2.3.3中间人攻击 2.3.4校验机制 2.3.4.1证书 2.3.4.2数字签名 1. 数字签名的生成过程 2. 数字签名的验证过程 2.4TLS协议（握手过程） 3.小结…...

编程日记 2025/7/29 13:34:32

《全球短剧正版授权通道，助力平台出海与流量变现》

正版短剧片源授权，全方位赋能您的内容运营短剧作为短视频领域的一种重要形式，凭借其紧凑的剧情、鲜明的角色和引人入胜的叙事方式，赢得了广大观众的喜爱。然而，在短剧市场蓬勃发展的同时，版权问题也日益凸显。为了保…...

编程日记 2025/8/2 2:40:39

17.【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--微服务基础工具与技术--ELK

在微服务中，日志是非常重要的组成部分。它不仅可以帮助我们排查问题，还可以帮助我们分析系统的性能和使用情况。ELK（Elasticsearch、Logstash、Kibana）是一个强大的日志分析工具，可以帮助我们收集、存储和分析日志数据…...

编程日记 2025/7/29 18:32:17

Linux系统管理与编程16：PXE自动化安装部署centos7.9操作系统

兰生幽谷，不为莫服而不芳； 君子行义，不为莫知而止休。 0.准备 1）防火墙和SELinux systemctl stop firewalld systemctl disable firewalld setenforce 0 sed -i s/^SELINUX.*/SELINUXdisabled/ /etc/selinux/config (很不好的…...

编程日记 2025/7/29 10:48:29

DAMA第10章深度解析：参考数据与主数据管理的核心要义与实践指南

引言在数字化转型的浪潮中，数据已成为企业的核心资产。然而，数据孤岛、冗余和不一致问题严重制约了数据价值的释放。DAMA（数据管理协会）提出的参考数据（Reference Data）与主数据（Master Data&…...

编程日记 2025/8/2 22:10:47

Python+OpenCV打造AR/VR基础框架：从原理到实战的全链路解析

引言：重新定义数字与现实的边界在元宇宙概念持续升温的当下，AR（增强现实）与VR（虚拟现实）技术正成为连接物理世界与数字世界的桥梁。Python凭借其丰富的计算机视觉生态（尤其是OpenCV库&#xf…...

编程日记 2025/7/29 3:57:33

PaddleOCR本地部署

构建TestPaddle目录： TestPaddle/ └── PaddleOCR ├── ocr_server.py ├── ch_PP-OCRv4_det_infer.tar ├── ch_PP-OCRv4_rec_infer.tar └── 001.jpg1、安装PaddleOCR 安装 PaddleOCR git clone https://github.com/PaddlePaddle/PaddleOCR.git cd …...

编程日记 2025/8/2 18:52:52

Spring事务融入(REQUIRED)具体实现步骤解析

Spring事务融入(REQUIRED传播行为)是Spring事务管理中最核心的机制，下面我将深入剖析其具体实现步骤和关键代码逻辑。 1. 整体流程概览事务融入(REQUIRED)的核心逻辑是： 检查当前线程是否存在事务存在则融入(加入)该事务不存在则创建新事务 2. …...

编程日记 2025/8/1 5:18:28

Java 开发者 Linux 学习指南

目录一、引言：为什么 Java 开发者必须掌握 Linux 二、Linux 基础：核心概念与常用命令 （一）文件系统与目录结构 （二）权限体系与用户管理 （三）进程管理与监控三、在 Linux 上安…...

编程日记 2025/8/2 3:41:01

2025年PMP 学习七 -第5章项目范围管理（5.4，5.5，5.6 ）

2025年PMP 学习七 -第5章项目范围管理 5.4 创建 WBS 1.定义与作用定义把项目可交付成果和项目工作分解成较小的，更易于管理的组件作用对所要交付的内容提供一个结构化的视图 2.输入，输出，工具与技术 3. 创建WBS的依据（输入&…...

编程日记 2025/7/29 6:13:17

【LangChain全景指南】构建下一代AI应用的开发框架

目录 🌟 前言🏗️ 技术背景与价值🚧 当前技术痛点🛠️ 解决方案概述👥 目标读者说明 🔍 一、技术原理剖析📊 核心概念图解💡 核心作用讲解🧩 关键技术模块说明⚖️ 技术选…...

编程日记 2025/8/1 15:27:05

Linux系统：虚拟文件系统与文件缓冲区（语言级内核级）

本节重点初步理解一切皆文件理解文件缓冲区的分类用户级文件缓冲区与内核级文件缓冲区用户级文件缓冲区的刷新机制两级缓冲区的分层协作一、虚拟文件系统 1.1 理解“一切皆文件” 我们都知道操作系统访问不同的外部设备（显示器、磁盘、键盘、鼠标、网卡&#…...

编程日记 2025/7/30 21:51:27

Linux进程间信号

目录信号入门生活角度中的信号技术应用角度的信号信号的发送与记录信号处理常见方式概述产生信号通过终端按键产生通过系统函数向进程发信号由软件条件产生信号由硬件异常产生信号阻塞信号信号其他相关常见概念在内核中的表示 sigset_t 信号集操作…...

编程日记 2025/7/29 18:31:41

数据分析2

五、文件 CSV Comma-Separated Value，逗号分割值。CSV文件以纯文本形式存储表格数据（数字和文本）。 CSV记录间以某种换行符分隔，每条记录由字段组成，字段间以其他字符或字符串分割，最常用逗号或制表符。…...

编程日记 2025/8/2 1:05:28

每日一题：两个仓库的最低配送费用问题

文章目录两个仓库的最低配送费用问题一、问题描述二、解题思路（一）初始假设（二）差值定义（三）选择最优（四）计算答案三、代码实现四、代码分析（一）输入处理&a…...

编程日记 2025/8/1 6:50:04

SemanticSplitterNodeParser 和 Sentence-BERT 的区别和联系是什么

这涉及到文本切分（chunking）与语义向量（embedding）之间的关系。我们来详细对比： ✅ 1. SemanticSplitterNodeParser 是什么？ SemanticSplitterNodeParser 是 llama-index 提供的一种语义感知的文本切分工…...

编程日记 2025/7/31 16:42:36

Fabric系列 - SoftHSM 软件模拟HSM

在 fabric-ca-server 上使用软件模拟的 HSM(密码卡) 功能安装 SoftHSMv2 教程 SoftHSMv2 默认的配置文件 /etc/softhsm2.conf默认的token目录 /var/lib/softhsm/tokens/ 初始化和启动fabric-ca-server，需要设置一个管理员用户的名称和密码初始化令牌 # 初始…...

编程日记 2025/7/31 15:46:14

简易图片编辑工具，支持抠图和替换背景

软件介绍 Photo Retouch是一款由微软官方商店推出的免费图片处理软件，具有抠图、换背景、修复等功能，操作便捷且效率极高，非常值得尝试。功能详解这款软件提供五大功能，包括删除物体、快速修复、一键抠图、背景调整和裁剪…...

编程日记 2025/7/29 18:31:26

CountDownLatch 并发编程中的同步利器

CountDownLatch 并发编程中的同步利器文章目录 CountDownLatch 并发编程中的同步利器一、CountDownLatch 基础概念1.1 什么是 CountDownLatch？1.2 CountDownLatch 的核心方法1.3 基本使用示例二、CountDownLatch 实战应用2.1 应用场景一：并行任务协调2…...

编程日记 2025/7/29 18:31:22

C++GO语言微服务之用户信息处理

目录 01 01-微服务实现用户注册-微服务端-上 02 02-微服务实现用户注册-微服务端-下 03 03-微服务实现用户注册-web端 04 04-微服务实现用户注册-web端-流程小结 05 05-获取地域信息-读MySQL写Redis入 06 06-获取地域信息-先查redis-没有读MySQL写入 01 07-Cookie简介 0…...

编程日记 2025/7/31 13:13:09

互联网大厂Java求职面试实战：Spring Boot微服务与数据库优化详解

💪🏻 1. Python基础专栏，基础知识一网打尽，9.9元买不了吃亏，买不了上当。 Python从入门到精通 😁 2. 毕业设计专栏，毕业季咱们不慌忙，几百款毕业设计等你选。 ❤️ 3. Python爬虫专栏…...

编程日记 2025/8/2 21:39:14

Linux基本指令（一）

目录基本指令 pwd指令 cd指令 cd ..编辑 cd ~ ls指令 ls -l ls -a ls -d touch指令 mkdir指令 rmdir指令 && rm 指令操作系统是什么呢？一个好的操作系统要具备什么条件呢？ 简单来说，操作系统是是一款做软硬件管理的软…...

编程日记 2025/7/31 17:01:27

Java—— 集合 List

List集合的特点有序：存和取的元素顺序一致有索引：可以通过索引操作元素可重复：存储的元素可以重复 List集合的方法 Collection的方法List都继承了，可以使用Collection中的方法此外，List集合因为有索引，…...

编程日记 2025/7/28 21:15:32

使用谱聚类将相似度矩阵分为2类

使用谱聚类将相似度矩阵分为2类的步骤如下： 构建相似度矩阵：提供的1717矩阵已满足对称性且对角线为1。计算度矩阵：对每一行求和得到各节点的度，形成对角矩阵。计算归一化拉普拉斯矩阵：采用对称归一化形式 LsymI−D…...

编程日记 2025/8/1 1:42:54

【Bootstrap V4系列】学习入门教程之组件-表单（Forms）高级用法（二）

Bootstrap V4系列学习入门教程之组件-表单（Forms）高级用法（二） 表单（Forms）高级用法（二）一、Help text 帮助文本二、Disabled forms 禁用表单三、Validation 验证3.1 How it works…...

编程日记 2025/8/2 20:58:24

【许可证】Open Source Licenses

长期更新扩展：shield.io装饰开源许可证（Open Source Licenses）有很多种，每种都有不同的授权和限制，适用于不同目的。默认的ISC🟰MIT License是否可商用是否要求开源衍生项目是否必须署名是否有专利授权…...

编程日记 2025/7/29 18:31:00

RT-Thread 深入系列 Part 7：RT-Thread vs 其他 RTOS 对比与选型指南

摘要本文对比 RT-Thread、FreeRTOS、Zephyr、uC/OS、Mbed OS 等主流嵌入式操作系统，从功能特性、社区生态、学习成本、商业支持、安全性和典型应用场景六个维度进行详尽对比，并给出不同项目类型下的选型建议，帮助你为下一个嵌入式项目做出最合适的决策。目录功能特性对比…...

编程日记 2025/7/30 23:42:40

每天五分钟机器学习：KTT条件

本文重点在前面的课程中，我们学习了拉格朗日乘数法求解等式约束下函数极值，如果约束不是等式而是不等式呢？此时就需要KTT条件出手了，KTT条件是拉格朗日乘数法的推广。KTT条件不仅统一了等式约束与不等式约束的优化问题求解范式，KTT条件给出了这类问题取得极值的一阶必要…...

编程日记 2025/7/29 14:37:51

金融学知识笔记

金融学知识笔记一、引言金融学它结合了数学、概率论、统计学、经济学和计算机科学等多学科的知识，用于解决金融领域中的各种问题，如金融衍生品定价、投资组合优化、风险管理和固定收益证券分析等。通过对金融学的学习，我们可以更好地理解…...

编程日记 2025/8/2 10:25:07

Web3 实战项目项目部署到 GitHub 和上线预览的完整指南

目录 🚀 一、部署到 GitHub ✅ 前置准备 🧱 部署步骤： 1. 创建一个 GitHub 仓库 2. 上传项目文件方法一：使用 Git 命令行方法二：直接上传 🌐 二、通过 GitHub Pages 免费上线 DApp（前端…...

编程日记 2025/7/31 21:05:11

嵌入式开发学习（阶段二 C语言基础）

C语言：第05天笔记内容提要分支结构条件判断用if语句实现分支结构用switch语句实现分支结构分支结构条件判断条件判断：根据某个条件成立与否，决定是否执行指定的操作。条件判断的结果是逻辑值，也就是布尔类型值&#…...

编程日记 2025/7/29 17:32:46

【沉浸式求职学习day35】【Tomcat安装、配置】【Http简述】

😩😩😩，真的每天忙死，感觉自己精神上压力真的很大，希望我的努力能够激励到你们~ 沉浸式求职学习 Tomcat1.安装2.Tomcat启动和配置3.配置高难度面试题 4.发布一个web网站5.Http1.什么是HTTP2.两个时代3.Htt…...

编程日记 2025/7/28 22:09:44

基于大模型的新型隐球菌脑膜炎智能诊疗全流程系统设计与实现的技术方案文档

目录一、术前风险预测系统1. 多模态融合模型架构2. 风险预测流程图（Mermaid）二、麻醉剂量预测系统1. 靶控输注（TCI）模型2. 麻醉方案优化流程图（Mermaid）三、术后并发症预测模型1. 时序预测模型（LSTM）2. 并发症预测流程图（Mermaid）四、健康教育管理模块1. 移动健康（…...

编程日记 2025/7/30 21:14:41

如何实现PLC远程编程

1. 什么是PLC编程 PLC编程是指为可编程逻辑控制器（Programmable Logic Controller，PLC）编写控制逻辑的过程。PLC是一种工业自动化控制设备，广泛应用于制造业、机械控制、流水线、电力系统等领域，用于替代传统的继电器…...

编程日记 2025/7/31 3:09:58

Go基于plugin的热更新初体验

背景对于一个部署在生产环境的项目来说，我们希望当代码出现bug的时候，可以不用重启进程而达到动态修改代码的目的—— 这就是代码热部署！ 使用java做游戏服务器，最大的好处是，当代码出现bug，可以直接热…...

编程日记 2025/7/29 17:32:38

【STM32 学习笔记】I2C通信协议

注：通信协议的设计背景 3:00~10:13 I2C 通讯协议(Inter－Integrated Circuit)是由Phiilps公司开发的，由于它引脚少，硬件实现简单，可扩展性强， 不需要USART、CAN等通讯协议的外部收发设备，现在被广…...

编程日记 2025/8/1 9:24:16

RAG与语义搜索：让大模型成为测试工程师的智能助手

引言 AI大模型风头正劲，自动生成和理解文本的能力让无数行业焕发新生。测试工程师也不例外——谁不想让AI自动“看懂需求、理解接口、生成用例”？然而，很多人发现：直接丢问题给大模型，答案貌似“懂行”，细…...

编程日记 2025/8/1 9:24:17

Nakama：让游戏与应用更具互动性和即时性

在现代游戏和应用程序开发中，实现社交互动和实时功能已成为用户体验的核心需求。为满足这种需求，许多开发者正转向分布式服务器技术，在这些技术中，Nakama 构建起了一座桥梁。Nakama 是一个开源的分布式服务器，专门为社…...

编程日记 2025/7/31 19:16:29

[Spring AOP 7] 动态通知调用

动态通知调用本笔记基于黑马程序员 Spring高级源码解读更美观清晰的版本在：Github 注意：阅读本章内容之前，建议先熟悉静态通知调用的内容在静态通知调用一节中，我们还有一个悬而未决的问题。我们谈到了调用链MethodInvocation…...

编程日记 2025/7/29 19:36:00

Redis 集群

集群基本介绍广义的集群，只要是多个机器构成了分布式系统，都可以称为是一个“集群”（主从模式，哨兵模式） 狭义的集群，Redis 提供的集群模式，在这个模式下主要解决的是存储空间不足的问题&…...

编程日记 2025/7/31 16:51:27

【Redis】基础命令数据结构

文章目录基础命令keysexistsdelexpirettltype 数据结构和内部编码在介绍数据类型前先介绍一下 Redis 的基础命令，方便理解基础命令 keys 返回所有满足样式（pattern）的 key keys pattern 当前有如下 key PS：实际开发环境和生…...

编程日记 2025/8/1 7:42:03

C++（6）：逻辑运算符

目录 1. 代码示例示例 1：基础用法示例 2：条件判断 2. 短路求值（Short-Circuit Evaluation） 代码示例 3. 实际应用场景场景 1：输入合法性验证场景 2：游戏状态判断 4. 注意事项逻辑运算符用于组…...

编程日记 2025/7/29 19:35:55

文章目录

搜索与图论

深度优先搜索 DFS

宽度优先搜索 BFS

树与图的存储

树与图的深度优先遍历

树与图的宽度优先遍历

拓扑排序

如何求拓扑序

度：入度和出度

题目概述

解题思路

方法步骤

代码解析

代码解释

复杂度分析

示例输入输出

最短路

建图！！！

朴素 Dijkstra

堆优化Dijkstra

Bellman_Ford

题目分析

算法思路

关键步骤：

代码解释

复杂度分析

注意事项

SPFA

Floyd

相关文章：