数据结构与算法-图论-复习1（单源最短路，全源最短路，最小生成树）
1. 单源最短路
单一边权 BFS
原理：由于边权为单一值，可使用广度优先搜索（BFS）来求解最短路。BFS 会逐层扩展节点，由于边权相同，第一次到达某个节点时的路径长度就是最短路径长度。
用法：适用于边权都为 1 的图，可快速求出从源点到其他所有节点的最短路径。
代码：
#include <iostream>#include <queue>#include <vector>using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];int dist[MAXN];
void bfs(int s) {
queue<int> q;
fill(dist, dist + MAXN, -1);
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;
}
0 - 1 边权双端队列 BFS
原理：使用双端队列来优化 BFS 过程。对于边权为 0 的边，将其终点插入队头；对于边权为 1 的边，将其终点插入队尾。这样能保证队列中元素的距离是单调递增的。
用法：适用于图中边权只有 0 和 1 的情况。
代码：
#include <iostream>#include <deque>#include <vector>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];
void bfs_01(int s) {
deque<int> q;
fill(dist, dist + MAXN, -1);
dist[s] = 0;
q.push_back(s);
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto [v, w] : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + w;
if (w == 0) {
q.push_front(v);
} else {
q.push_back(v);
}
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
bfs_01(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;
}
朴素迪杰斯特拉
原理：通过贪心策略，每次从未确定最短路径的节点中选择距离源点最近的节点，然后以该节点为中间点更新其他节点的距离。
用法：适用于边权非负且节点数较少的图，时间复杂度为 O(V2)稠密图。
代码：
#include <iostream>#include <vector>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];int dist[MAXN];bool vis[MAXN];
void dijkstra(int s, int n) {
fill(dist, dist + MAXN, INT_MAX);
fill(vis, vis + MAXN, false);
dist[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = true;
for (int v = 1; v <= n; v++) {
if (!vis[v] && graph[u][v] != INT_MAX) {
dist[v] = min(dist[v], dist[u] + graph[u][v]);
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
}
dijkstra(s, n);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;}
堆优化迪杰斯特拉
原理：使用优先队列（小根堆）来优化每次选择距离源点最近的节点的过程，减少时间复杂度。
用法：适用于边权非负且节点数较多的稀疏图，时间复杂度为 O((V+E)logV)。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(dist, dist + MAXN, INT_MAX);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;}
Bellman - Ford
原理：通过对所有边进行 V−1 次松弛操作，来更新节点的最短距离。如果图中存在负环，经过 V−1 次松弛操作后，仍然可以继续松弛。
用法：适用于存在负权边的图，也可用于求解只经过 k 条边的最短路。
代码：
#include <iostream>#include <vector>#include <climits>using namespace std;
const int MAXN = 100005;struct Edge {
int u, v, w;};
vector<Edge> edges;int dist[MAXN];
bool bellman_ford(int s, int n) {
fill(dist, dist + MAXN, INT_MAX);
dist[s] = 0;
int flag=0;
for (int i = 0; i < n ; i++) {
for (auto [u, v, w] : edges) {
flag=0;
if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
flag=1;
if(i==n)return true;//如果链接了n条边还能松弛就说明有负环
}
}
}
return false;
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
if (bellman_ford(s, n)) {
cout << "存在负环" << endl;
} else {
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
return 0;
}
SPFA
原理：SPFA 是 Bellman - Ford 算法的优化版本，使用队列来维护需要松弛的节点。
用法：适用于存在负权边的图，但在某些特殊图中可能会退化为 O(VE)。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];int cnt[MAXN]; // 记录每个节点入队的次数bool in_queue[MAXN];
bool spfa(int s, int n) {
fill(dist, dist + MAXN, INT_MAX);
fill(cnt, cnt + MAXN, 0);
fill(in_queue, in_queue + MAXN, false);
dist[s] = 0;
queue<int> q;
q.push(s);
in_queue[s] = true;
cnt[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!in_queue[v]) {
q.push(v);
in_queue[v] = true;
cnt[v]++;
if (cnt[v] > n) {
return true; // 存在负环
}
}
}
}
}
return false;}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
if (spfa(s, n)) {
cout << "存在负环" << endl;
} else {
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
return 0;}
2. 单源最短路和其他算法的结合
二分答案 + 双端队列求最短路
以 “可以免费建立 k 条边，求最小的花费” 为例，二分答案 mid，将边权大于 mid 的边视为 1，边权小于等于 mid 的边视为 0，使用双端队列 BFS 求解最短路，判断最短路径上大于 mid 的边数是否小于等于 k。
缩点 + 最短路
先使用 Tarjan 算法求出图的强连通分量，然后进行缩点，将每个强连通分量缩成一个点，再在缩点后的图上进行最短路计算。
首位两次最短路求节点之间的最大差值（以 2009 年提高组最优贸易问题为例）
分别从起点和终点进行最短路计算，记录从起点到每个节点的最小价格和从终点到每个节点的最大价格，然后枚举每个节点，计算最大差值。
3. 单源最短路自身的拓展
多起点多终点用虚拟节点
添加一个虚拟起点和一个虚拟终点，将虚拟起点与所有起点相连，边权为 0，将所有终点与虚拟终点相连，边权为 0，然后求解从虚拟起点到虚拟终点的最短路。
分图层的最短路
以 “拯救大兵瑞恩” 为例，使用三维数组 d[x][y][st] 记录状态，其中 (x,y) 表示节点坐标，st 表示当前拥有的钥匙状态，只有拿到了钥匙才能进入到对应层的一些状态，在 BFS 或 Dijkstra 过程中更新状态。
新的一个例题：
题目背景
本题原题数据极弱，Subtask 0 中的测试点为原题测试点，Subtask 1 中的测试点为 Hack 数据。
题目描述
C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1∼n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 1∼n 号城市的水晶球价格分别为 4,3,5,6,1。
阿龙可以选择如下一条线路：1→2→3→5，并在 2 号城市以 3 的价格买入水晶球，在 3 号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。
阿龙也可以选择如下一条线路：1→4→5→4→5，并在第 1 次到达 5 号城市时以 1 的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数 x,y,z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。
输出格式
一个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 0。
代码：
分层图，第一层原本的图，第二层，第一层购买后到达的图，第三层，第二层对应节点卖出的图
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=100010;
unordered_map<int,vector<pii>>e;
int n,m;
int a[N];
int dis[N*3];
bool vis[N*3];
void spfa(int s){
memset(dis,-0x3f,sizeof dis);
queue<int> q;
q.push(s);
dis[s]=0;
vis[s]=1;
while(q.size()){
int u=q.front();
q.pop();
vis[u]=0;
for(auto t:e[u]){
int v=t.first,w=t.second;
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
e[i].push_back({i+n,-a[i]});
e[n+i].push_back({i+2*n,a[i]});
}
for(int i=0;i<m;i++){
int u,v,op;
scanf("%d%d%d",&u,&v,&op);
if(op==2){
e[u].push_back({v,0});
e[u+n].push_back({v+n,0});
e[u+2*n].push_back({v+2*n,0});
e[v].push_back({u,0});
e[v+n].push_back({u+n,0});
e[v+2*n].push_back({u+2*n,0});
}else{
e[u].push_back({v,0});
e[u+n].push_back({v+n,0});
e[u+2*n].push_back({v+2*n,0});
}
}
spfa(1);
cout<<dis[3*n];
}
最短路计数
在更新最短路径时，记录路径数量。如果经过某个点的路径更短，计数为 1；如果相等，计数累加。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;const int MOD = 1e9 + 7;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];int cnt[MAXN];
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(dist, dist + MAXN, INT_MAX);
fill(cnt, cnt + MAXN, 0);
dist[s] = 0;
cnt[s] = 1;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
cnt[v] = cnt[u];
pq.push({dist[v], v});
} else if (dist[v] == dist[u] + w) {
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " " << cnt[i] << endl;
}
return 0;}
最短路和次短路
使用两个数组分别记录最短路和次短路，在更新时同时更新这两个数组。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist1[MAXN]; // 最短路int dist2[MAXN]; // 次短路
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(dist1, dist1 + MAXN, INT_MAX);
fill(dist2, dist2 + MAXN, INT_MAX);
dist1[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist2[u]) continue;
for (auto [v, w] : adj[u]) {
int new_dist = d + w;
if (new_dist < dist1[v]) {
dist2[v] = dist1[v];
dist1[v] = new_dist;
pq.push({dist1[v], v});
} else if (new_dist < dist2[v] && new_dist > dist1[v]) {
dist2[v] = new_dist;
pq.push({dist2[v], v});
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist1[i] << " " << dist2[i] << endl;
}
return 0;}
4. 全源最短路
Floyd 算法
原理：通过动态规划的思想，枚举中间节点 k，更新任意两点之间的最短距离。
用法：适用于求解任意两点之间的最短路径，也可用于处理联通问题、传递闭包和最小环问题。
代码：
#include <iostream>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];
void floyd(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
}
floyd(n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
return 0;}
最小环
在 Floyd 算法的基础上，记录最小环的长度。
cpp
#include <iostream>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];int dist[MAXN][MAXN];
int floyd_min_cycle(int n) {
int ans = INT_MAX;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++) {
for (int j = i + 1; j < k; j++) {
if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX && dist[i][j] != INT_MAX) {
ans = min(ans, graph[i][k] + graph[k][j] + dist[i][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
graph[v][u] = min(graph[v][u], w);
}
int min_cycle = floyd_min_cycle(n);
if (min_cycle == INT_MAX) {
cout << "不存在最小环" << endl;
} else {
cout << "最小环长度为: " << min_cycle << endl;
}
return 0;
}
5. 最小生成树
Prim 算法
原理：从一个节点开始，每次选择与当前生成树相连的边中权值最小的边，将其加入生成树，直到所有节点都被加入。
用法：适用于稠密图，时间复杂度为 O(V2)。
代码：
#include <iostream>#include <vector>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];bool vis[MAXN];int dist[MAXN];
int prim(int n) {
fill(vis, vis + MAXN, false);
fill(dist, dist + MAXN, INT_MAX);
dist[1] = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = true;
ans += dist[u];
for (int v = 1; v <= n; v++) {
if (!vis[v] && graph[u][v] != INT_MAX) {
dist[v] = min(dist[v], graph[u][v]);
}
}
}
return ans;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
graph[v][u] = min(graph[v][u], w);
}
int mst = prim(n);
cout << "最小生成树的权值为: " << mst << endl;
return 0;}
Kruskal 算法
原理：将所有边按权值从小到大排序，然后依次选择边，如果该边的两个端点不在同一个连通分量中，则将该边加入生成树，直到所有节点都在同一个连通分量中。
用法：适用于稀疏图，时间复杂度为 O(ElogE)。
代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;
const int MAXN = 100005;struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}};
vector<Edge> edges;int parent[MAXN];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];}
void unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
}}
int kruskal(int n) {
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int ans = 0;
int cnt = 0;
for (auto [u, v, w] : edges) {
if (find(u) != find(v)) {
unite(u, v);
ans += w;
cnt++;
if (cnt == n - 1) {
break;
}
}
}
return ans;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
int mst = kruskal(n);
cout << "最小生成树的权值为: " << mst << endl;
return 0;}
6. 最小生成树的运用
引入虚拟节点
以 “有 k 个点可以用卫星链接，求出让全部点联通的最小花费” 为例，添加一个虚拟节点，将该节点与可以用卫星链接的 k 个点相连，边权为 0，然后使用 Kruskal 或 Prim 算法求解最小生成树。
允许 k 个联通块的最小花费
使用 Kruskal 算法，在合并节点的过程中，当合并到 k 个联通块时停止，此时的花费即为最小花费。
代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;
const int MAXN = 100005;struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}};
vector<Edge> edges;int parent[MAXN];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];}
void unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
}}
int kruskal(int n, int k) {
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int ans = 0;
int cnt = n;
for (auto [u, v, w] : edges) {
if (find(u) != find(v)) {
unite(u, v);
ans += w;
cnt--;
if (cnt == k) {
break;
}
}
}
return ans;}
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
int cost = kruskal(n, k);
cout << "允许 " << k << " 个联通块的最小花费为: " << cost << endl;
return 0;
}
相关文章：
数据结构与算法-图论-复习1（单源最短路，全源最短路，最小生成树）
1. 单源最短路 单一边权 BFS 原理：由于边权为单一值，可使用广度优先搜索（BFS）来求解最短路。BFS 会逐层扩展节点，由于边权相同，第一次到达某个节点时的路径长度就是最短路径长度。 用法：适用…...
oracle 动态性能视图
Oracle 数据库中的 V$SQLAREA 是一个动态性能视图（Dynamic Performance View），用于记录共享池（Shared Pool）中所有 SQL 语句的统计信息。每个 SQL 语句在共享池中存储为一个游标（Cursor）&#x…...
Vue3+Vite+TypeScript+Element Plus开发-10.多用户动态加载菜单
系列文档目录 Vue3ViteTypeScript安装 Element Plus安装与配置 主页设计与router配置 静态菜单设计 Pinia引入 Header响应式菜单缩展 Mockjs引用与Axios封装 登录设计 登录成功跳转主页 多用户动态加载菜单 Pinia持久化 动态路由-配置 文章目录 目录 系列文档目…...
前端用户列表与后端分页协同设计
分页实现方案 在现代Web应用中，用户列表展示与分页是一个常见的功能需求。前端与后端通过API协同工作，使用PageHelper等工具实现高效分页。 例如： 后端实现 (使用PageHelper) public PageResult DishPage(DishPageQueryDTO dishPageQuery…...
三月份面试感触
我毕业三年了，也在公司干了三年本来还以为很快的找到工作，没想到呀现在就业环境是真的差，那个boss和智联一堆的外包找你，找你要了简历然后就没下文了，我也去面了几家自研的公司，只能说这不是欺负老实人吗&a…...
C++使用WebView2控件，通过IPC通信与Javascript交互
引言 在现代桌面应用程序开发中，Web技术与原生应用的融合变得越来越普遍。Microsoft的WebView2控件为C开发者提供了一个强大的工具，使他们能够在桌面应用中嵌入基于Chromium的Web浏览器引擎。本文将详细介绍如何在C应用程序中使用WebView2控件ÿ…...
精准测试建设过程中遇到的一些问题
1.sqlite3 仅可以处理单个任务问题，多线程往往会面临数据库锁定 因为仅临时存储，后来在创建数据库时，给每个任务开了一个临时数据库，存储数据执行完毕后，删除db sql_insert_new:INSERT INTO analyze_api_resault_dynam…...
【Docker】Dockerfile 编写实践
👻创作者：丶重明 👻创作时间：2025年4月8日 👻擅长领域：运维 目录 1. Dockerfile编写原则1.1.选择合适的基础镜像1.2.镜像层优化1.3.多阶段构建1.4.安全增强 2. 关键指令与技巧2.1.COPY vs ADD2.2.ENTRYPOIN…...
Jakarta EE 11发布：云原生Java企业应用的新标准
📝 摘要 Jakarta EE 11于2023年正式发布，这是Java企业版技术栈的一次重要更新。本文将详细介绍Jakarta EE 11的核心特性、改进之处以及如何利用这些新功能构建现代化的云原生应用。我们将通过实际代码示例展示新特性的使用方法，并分析其对Ja…...
蓝桥杯第十五届C++B组省赛真题解析
蓝桥杯第十五届CB组省赛真题解析 一、宝石组合https://www.lanqiao.cn/problems/19711/learning/ 解题思路 题目要求找到三个数，使得它们的最大公约数（GCD）尽可能大，并在GCD相同的情况下选择数值最小的三个数。以下是分步解析&a…...
LabVIEW商业软件开发注意问题
在 LabVIEW 商业软件开发进程中，性能优化、界面设计及兼容性与扩展性，对软件品质、用户体验和市场适配性起着决定性作用。下面，借助多个LabVIEW 编程特性的实际案例，深入分析这些方面的开发要点。 一、性能优化：提升软…...
面试算法高频04-分治与回溯
分治与回溯 分治和回溯算法，包括其概念、特性、代码模板，并结合具体题目进行讲解，旨在帮助学员理解和掌握这两种算法的应用。 分治与回溯的概念 分治（Divide & Conquer）：本质上基于递归，先…...
记录vscode连接不上wsl子系统下ubuntu18.04问题解决方法
记录vscode连接不上wsl子系统下ubuntu18.04问题解决方法 报错内容尝试第一次解决方法尝试第二次解决方法注意事项参考连接 报错内容 Unable to download server on client side: Error: Request downloadRequest failed unexpectedly without providing any details… Will tr…...
Java 中 SQL 注入问题剖析
一、引言 在当今数字化时代，数据是企业和组织的核心资产之一。许多应用程序都依赖于数据库来存储和管理数据，而 Java 作为一种广泛使用的编程语言，常被用于开发与数据库交互的应用程序。然而，SQL 注入这一安全漏洞却如同隐藏在…...
华为数字芯片机考2025合集2已校正
单选 1. 题目内容 关于亚稳态的描述错误的是（ ）。 1. 解题步骤 1.1 理解亚稳态（Metastability）的核心特性 亚稳态是指触发器无法在指定时间内稳定输出有效逻辑电平（0或1）的状态，其关键特点…...
Leedcode刷题 | Day27_贪心算法01
一、学习任务 455.分发饼干代码随想录376. 摆动序列53. 最大子序和 二、具体题目 1.455分发饼干455. 分发饼干 - 力扣（LeetCode） 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对…...
深度学习项目--分组卷积与ResNext网络实验探究(pytorch复现)
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者：K同学啊 前言 ResNext是分组卷积的开始之作，这里本文将学习ResNext网络；本文复现了ResNext50神经网络，并用其进行了猴痘病分类实验…...
CSS 笔记——Flexbox（弹性盒布局）
目录 1. Flex 容器与 Flex 项目 2. 主轴与交叉轴 3. Flex 容器的属性 display flex-direction justify-content align-items align-content flex-wrap 4. Flex 项目的属性 flex-grow flex-shrink flex-basis flex align-self 5. Flexbox 的优点 6. Flexbox 的…...
[实战] linux驱动框架与驱动开发实战
linux驱动框架与驱动开发实战 Linux驱动框架与驱动开发实战一、Linux驱动框架概述1.1 Linux驱动的分类1.2 Linux驱动的基本框架 二、Linux驱动关键API详解2.1 模块相关API2.2 字符设备驱动API2.3 内存管理API2.4 中断处理API2.5 PCI设备驱动API 三、Xilinx XDMA驱动开发详解3.1…...
cpp（c++）win 10编译GDAL、PROJ、SQLite3、curl、libtiff
cpp（c）编译GDAL、PROJ、SQLite3 Sqlite3libtiffcurlprojGDAL Sqlite3 1、下载 Sqlite3 源码、工具、二进制预编译 exe Sqlite3 官网：https://www.sqlite.org/download.html 下载 sqlite-amalgamation-3430200.zipsqlite-dll-win64-x64-3430…...
每日一题（小白）暴力娱乐篇23
由题意得知给我们一串数字，我们每次交换两位，最少交换多少次成功得到有顺序的数组。我们以平常的思维去思考，加入给你一串数字获得最少的交换次数，意味着你的交换后续基本不会变，比如说2 1 3 5 4 中1与2交换后不变&…...
01-Redis-基础
1 redis诞生历程 redis的作者笔名叫做antirez，2008年的时候他做了一个记录网站访问情况的系统，比如每天有多少个用户，多少个页面被浏览，访客的IP、操作系统、浏览器、使用的搜索关键词等等(跟百度统计、CNZZ功能一样)。最开始存储…...
【从零开始学习JVM | 第一篇】快速认识JVM
什么是JVM？ JVM--Java虚拟机，它是Java实现平台无关性的基石。 Java程序运行的时候，编译器将Java代码编译为平台无关的Java字节码文件（.class），接下来对应平台的JVM对字节码进行运行解释，翻译成…...
使用RabbitMQ实现异步秒杀
搭建RabbitMQ 在虚拟机上用docker搭建RabbitMQ，首先拉取镜像 docker run --privilegedtrue -d -p 5672:5672 -p 15672:15672 --name rabbitmq rabbitmq:management mkdir -p /usr/local/docker/rabbitmq再创建rabbitmq容器，下面的命令已经能够创建之后…...
Spring Boot 配置文件加载优先级全解析
精心整理了最新的面试资料和简历模板，有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 Spring Boot 配置文件加载优先级全解析 Spring Boot 的配置文件加载机制是开发者管理不同环境配置的核心功能之一。其通过外部化配置（Externaliz…...
解决华硕主板Z890m下载ubuntu20.04后没有以太网问题
问题描述： 华硕主板Z890m下载双系统ubuntu20.04后，发现ubuntu不能打开以太网。 问题原因： 华硕主板的网卡驱动是r8125,而ubuntu20.04的驱动版本是r8169，所以是网卡驱动不匹配造成 解决方案 开机界面按下F2进入BOIS模式&#…...
xLua的Lua调用C#的2，3，4
使用Lua在Unity中创建游戏对象，组件： 相关代码如下： Lua --Lua实例化类 --C# Npc objnew Npc() --通过调用构造函数创建对象 local objCS.Npc() obj.HP100 print(obj.HP) local obj1CS.Npc("admin") print(obj1.Name)--表方法希…...
Debian系统_主板作为路由器_测试局域网设备间网速
Debian系统_主板作为路由器_测试局域网设备间网速 一、360软件测网速 360测出来的网速实际上是宽带的速度，并不是路由器LAN口到电脑这一段的网速 二、使用iperf3 进行双向带宽测试 1、开发板端下载软件 //Debian系统或者/Ubuntu sudo apt update && sudo…...
从 macos 切换到 windows 上安装的工具类软件
起因 用了很多年的macos, 已经习惯了macos上的操作, 期望能在windows上获得类似的体验, 于是花了一些时间来找windows上相对应的软件. 截图软件 snipaste windows和macos都有的软件, 截图非常好用 文件同步软件 oneDrive: 尝试了不同的同步软件, 还是微软在各…...
JavaScript中通过array.map(）实现数据转换、创建派生数组、异步数据流处理、复杂API请求、DOM操作、搜索和过滤等，array.map(）的使用详解（附实际应用代码）
目录 JavaScript中通过array.map(）实现数据转换、创建派生数组、异步数据流处理、复杂API请求、DOM操作、搜索和过滤等，array.map（）的使用详解（附实际应用代码） 一、什么时候该使用Array.map()࿰…...