十一、数据结构(图的最短路)


最短路径是图论中最为人们熟知的问题。

基础部分

最短路径问题

在一个图中有 n n n 个点、 m m m条边。边有权值,例如费用、长度等,权值可正可负。边可能是有向的,也可能是无向的。给定两个点,起点是 s s s,终点是 t t t,在所有能连接s和t的路径中寻找边的权值之和最小的路径,这就是最短路径问题。

D F S DFS DFS搜索所有的路径

在一般的图中,求图中任意两点间的最短路径,首先需要遍历所有可能经过的结点和边,不能有遗漏。其次,在所有可能的路径中查找最短的一条。如果用暴力法找所有路径,最简单的方法是把 n n n 个结点进行全排列,然后从中找到最短的。但是共有 n ! n! n!个排列,是天文数字,无法求解。更好的办法是用 D F S DFS DFS输出所有存在的路径,这显然比 n ! n! n!要少得多,不过,其复杂度仍然是指数级的。

B F S BFS BFS求最短路径

在特殊的地图中,所有的边都是无权的,可以把每个边的权值都设成1,那么 B F S BFS BFS也是很好的最短路径算法,在之前也有讲过。

最短路算法

  1. 图的规模小,用 F l o y d Floyd Floyd。如果边的权值有负数,需要判断负圈。
  2. 图的规模大,且边的权值非负,用 D i j k s t r a Dijkstra Dijkstra
  3. 图的规模大,且边的权值有负数,用 S P F A SPFA SPFA。需要判断负圈。
节点 n n n,边 m m m边权值选用算法数据结构
n < 300 n < 300 n<300允许有负数 F l o y d Floyd Floyd邻接矩阵
m × n < 1 0 7 m×n < 10^7 m×n<107允许有负数 B e l l m a n − F o r d Bellman-Ford BellmanFord邻接表
更大有负数 S P F A SPFA SPFA邻接表、链式前向星
更大无负数 D i j k s t r a Dijkstra Dijkstra邻接表、链式前向星

F l o y d Floyd Floyd

一次性求出所有点对间的最短路径
如何一次性求所有结点之间的最短距离? F l o y d Floyd Floyd可以完成这一工作,其他 3 3 3 种算法都不行。而且 F l o y d Floyd Floyd是最简单的最短路径算法,程序比暴力的 D F S DFS DFS更简单。需要提醒的是, F l o y d Floyd Floyd的复杂度有 O ( n 3 ) O(n^3) O(n3),只能用于小规模的图。
F l o y d Floyd Floyd用到了动态规划的思想:求两点 i 、 j i、j ij 之间的最短距离,可以分两种情况考虑,即经过图中某个点 k k k的路径和不经过点 k k k的路径,取两者中的最短路径。

动态规划的过程可以描述为:

  1. k = 1 k=1 k=1,计算所有结点之间(经过结点1、不经过结点1)的最短路径。
  2. k = 2 k=2 k=2,计算所有结点之间(经过结点2、不经过结点2)的最短路径,这一次计算利用了 k = 1 k=1 k=1时的计算结果。
  3. k = 3 k=3 k=3,……

读者可以这样想象这个过程:

  1. 图上有 n n n个结点, m m m条边。
  2. 把图上的每个点看成一个灯,初始时灯都是灭的,大部分结点之间的距离被初始化为无穷大 I N F INF INF,除了 m m m条边连接的那些结点以外。
  3. 从结点 k = 1 k=1 k=1开始操作,想象点亮了这个灯,并以 k = 1 k=1 k=1为中转点,计算和调整图上所有点之间的最短距离。很显然,对这个灯的邻居进行的计算是有效的,而对远离它的那些点的计算基本是无效的。
  4. 逐步点亮所有的灯,每次点灯,就用这个灯中转,重新计算和调整所有灯之间的最短距离,这些计算用到了以前点灯时得到的计算结果。
  5. 灯逐渐点亮,直到图上的点全亮,计算结束。
code(Floyd的实现):
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int N = 300;
int n, m, q; //n个地点,m条路线,q次询问
void floyd(){
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
		if(dp[i][k] == INF)continue;
			for(int j = 1; j <= n; j++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
				//min 最好改写,因为min比较慢 
			}
		}
	}
}
int main(){
	cin >> n >> m >> q;
	ll st, ed, dif;
	memset(dp, INF, sizeof dp);
	for(int i = 0; i < m; i++){
		cin >> st >> ed >> dif; //从 st 到 ed 的距离是 dif
		dp[st][ed] = min(dp[st][ed], dif);
		dp[ed][st] = dp[st][ed];
	}
	
	floyd();
	
	return 0;
}

F l o y d Floyd Floyd算法虽然低效,但是也有优点:

  1. 程序很简单
  2. 可以一次求出所有结点之间的最短路径
  3. 能处理有负权边的图

S P F A SPFA SPFA

S P A F SPAF SPAF很像 B F S BFS BFS

  1. 起点 s s s 入队,计算它所有邻居到 s s s 的最短距离(当前最短距离,不是全局最短距离。在下文中,把计算一个结点到起点 s s s 的最短路径简称为更新状态。最后的“状态”就是 S P F A SPFA SPFA的计算结果)。把 s s s 出队,状态有更新的邻居入队,没更新的不入队。也就是说,队列中都是状态有变化的结点,只有这些结点才会影响最短路径的计算。
  2. 现在队列的头部是 s s s 的一个邻居 u u u。弹出 u u u,更新其所有邻居的状态,把其中有状态变化的邻居入队列。
  3. 这里有一个问题,弹出 u u u 之后,在后面的计算中 u u u 可能会再次更新状态(后来发现, u u u借道其他结点去 s s s,路更近)。所以, u u u可能需要重新入队列。这一点很容易做到:在处理一个新的结点 v v v 时,它的邻居可能就是以前处理过的 u u u,如果 u u u 的状态变化了,把 u u u 重新加入队列就行了。
  4. 继续以上过程,直到队列空。这也意味着所有结点的状态都不再更新。最后的状态就是到起点 s s s 的最短路径。
    上面第(3)点决定了 S P F A SPFA SPFA的效率。有可能只有很少结点重新进入队列,也有可能很多。这取决于图的特征,即使两个图的结点和边的数量一样,但是边的权值不同,它们的 S P F A SPFA SPFA队列也可能差别很大。所以, S P F A SPFA SPFA是不稳定的。
    在比赛时,有的题目可能故意卡 S P F A SPFA SPFA的不稳定性:如果一个题目的规模很大,并且边的权值为非负数,它很可能故意设置了不利于 S P F A SPFA SPFA的测试数据。此时不能冒险用 S P F A SPFA SPFA,而是用下一节的 D i j k s t r a Dijkstra Dijkstra算法。 D i j k s t r a Dijkstra Dijkstra是一种稳定的算法,一次迭代至少能找到一个结点到 s s s 的最短路径,最多只需要 m m m(边数)次迭代即可完成。
code(基于邻接表的 S P F A ) SPFA) SPFA)

在这个程序中,存图最合适的方法是邻接表。上面第(2)步是更新 u u u的所有邻居结点的状态,而邻接表可以很快地检索一个结点的所有邻居,正符合算法的需要。在下程序中输入图时,每执行一次 e [ a ] . p u s h b a c k ( e d g e ( a , b , c ) ) e[a].push_back(edge(a,b,c)) e[a].pushback(edge(a,b,c)),就把边 ( a , b ) (a,b) (a,b)存到了结点 a a a 的邻接表中在 s p f a ( ) spfa() spfa()中,执行 f o r ( i n t i = 0 ; i < e [ u ] . s i z e ( ) ; i + + ) for(int i=0;i<e[u].size();i++) for(inti=0;i<e[u].size();i++),就检索了结点 u u u 的所有邻居。

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 5;
struct edge{
    int to; long long dif;
    //to 表示目标位置, dif表示到目标的距离  
    edge(int x, long long y){to = x, dif = y;}
};

bool flag[N];           //标记点 i 是否在队列中  
long long dist[N];      //记录 i 到起点的距离  
vector<edge> e[N];      //记录 i 的所有邻接点  

void SPFA(int start){
    memset(dist, INF, sizeof(dist));
    memset(flag, false, sizeof(flag));
    dist[start] = 0;        //起点到自己的距离为0  
    queue<int> que;         
    que.push(start);     
    flag[start] = true;     //入队就标记  
    while(!que.empty()){
        int now = que.front(); que.pop();   //处理队列第一个点  
        flag[now] = false;                  //now不在队列里,取消标记  
        if(dist[now] == INF)continue;       //如果这个点不能到起点,就不管了  
        for(int i = 0; i < e[now].size(); i++){ //访问这个点的所有邻居  
            int next = e[now][i].to;
            int d = e[now][i].dif;
            if(dist[next] > dist[now] + d)
                dist[next] = dist[now] + d;
            //如果这个点有更近的到起点的路,那就把距离记录优化
            if(!flag[next]){        //如果这个点还没进队列的话,就让他进队  
                que.push(next);
                flag[next] = true;
            }
        }
    }
}
int main(){
    int n, m, s;    //n 个地方, m 条路, s 是起点  
    cin >> n >> m >> s;
    for(int i = 1; i<= m; i++){
        int now, to; long long dif;
        cin >> now >> to >> dif;
        e[now].push_back(edge(to, dif));
    }
    
    SPFA(s);

    return 0;
}

D i j k s t r a Dijkstra Dijkstra

D i j k s t r a Dijkstra Dijkstra是非常高效而且稳定的单源随短路算法,它比前面提到的最短路径算法都复杂一些。下面先介绍它的思想:
现实中, D i j k s t r a Dijkstra Dijkstra有另外的模型,多米诺骨牌,读者可以想象下面的场景:在图中所有的边上排满多米诺骨牌,相当于把骨牌看成图的边。一条边上的多米诺骨牌数量和边的权值(例如长度或费用)成正比。规定所有骨牌倒下的速度都是一样的。如果在一个结点上推倒骨牌,会导致这个结点上的所有骨牌都往后面倒下去。在起点 s s s 推倒骨牌,可以观察到,从 s s s 开始,它连接的边上的骨牌都逐渐倒下,并到达所有能达到的结点。在某个结点 t t t,可能先后从不同的线路倒骨牌过来,先倒过来的骨牌,其经过的路径肯定就是从 s s s 到达 t t t 的最短路径,后倒过来的骨牌,对确定结点 t t t 的最短路径没有贡献,不用管它。

从整体看,这就是一个从起点 s s s 扩散到整个图的过程。在这个过程中,观察所有结点的最短路径是这样得到的:

  1. s s s 的所有直连邻居中,最近的邻居 u u u,骨牌首先到达。 u u u 是第一个确定最短路径的结点。从 u u u 直连到 s s s 的路径肯定是最短的,因为如果 u u u 绕道别的结点到 s s s,必然更远。
  2. 然后,把后面骨牌的倒下分成两个部分,一部分是从 s s s 继续倒下到 s s s 的其他的直连邻居,另一部分是从 u u u 出发倒下到 u u u 的直连邻居。那么下一个到达的结点 v v v 必然是 s s s 或者 u u u 的一个直连邻居。 v v v 是第二个确定最短路径的结点。
  3. 继续以上步骤,在每一次迭代过程中都能确定一个结点的最短路径。 D i j k s t r a Dijkstra Dijkstra算法应用了贪心法的思想,即“抄近路走,肯定能找到最短路径”。
    在上述步骤中可以发现: D i j k s t r a Dijkstra Dijkstra的每次迭代,只需要检查上次已经确定最短路径的那些结点的邻居,检查范围很小,算法是高效的;每次迭代,都能得到至少一个结点的最短路径,算法是稳定的。

那么如何编程实现呢?程序的主要内容是维护两个集合,即已确定最短路径的结点集合 A A A、这些结点向外扩散的邻居结点集合 B B B。程序逻辑如下:

  1. 把起点 s s s放到 A A A中,把 s s s所有的邻居放到 B B B中。此时,邻居到 s s s的距离就是直连距离。
  2. B B B中找出距离起点 s s s最短的结点 u u u,放到 A A A中。
  3. u u u所有的新邻居放到 B B B中。显然, u u u的每一条边都连接了一个邻居,每个新邻居都要加进去。其中 u u u的一个新邻居 v v v,它到 s s s的距离 d i s ( s , v ) dis(s,v) dis(s,v)等于 d i s ( s , u ) + d i s ( u , v ) dis(s,u)+dis(u,v) dis(s,u)+dis(u,v)
  4. 重复(2)、(3),直到 B B B为空时结束。计算结束后,可以得到从起点 s s s到其他所有点的最短距离。

    如上图,起点是 1 1 1,求 1 1 1到其他所有结点的最短路径。
  5. 1到自己的距离最短,把 1 1 1放到集合 A A A里: A = { 1 } A=\{1\} A={1}。把 1 1 1的邻居放到集合 B B B里: B = { ( 2 − 5 ) , ( 3 − 2 ) } B=\{(2-5),(3-2)\} B={(25),(32)}。其中 ( 2 − 5 ) (2-5) (25)表示结点 2 2 2到起点的距离是 5 5 5
  6. B B B中找到离集合 A A A最近的结点,是结点 3 3 3。在 A A A中加上 3 3 3,现在 A = { 1 , 3 } A=\{1,3\} A={1,3},也就是说得到了从1到3的最短距离;从 B B B中拿走 ( 3 − 2 ) (3-2) (32),现在 B = { ( 2 − 5 ) } B=\{(2-5)\} B={(25)}
  7. 对结点3的每条边,扩展它的新邻居,放到 B B B中。3的新邻居是2和4,那么 B = { ( 2 − 5 ) , ( 2 − 4 ) , ( 4 − 7 ) } B=\{(2-5),(2-4),(4-7)\} B={(25),(24),(47)}。其中 ( 2 − 4 ) (2-4) (24)是指新邻居2通过3到起点1,距离是4。由于 ( 2 − 4 ) (2-4) (24) ( 2 − 5 ) (2-5) (25)更好,丢弃 ( 2 − 5 ) (2-5) (25) B = { ( 2 − 4 ) , ( 4 − 7 ) } B=\{(2-4),(4-7)\} B={(24),(47)}
  8. 重复步骤 ( 2 ) 、 ( 3 ) (2)、(3) (2)(3)。从 B B B中找到离起点最近的结点,是结点2。在 A A A中加上2,并从 B B B中拿走 ( 2 − 4 ) (2-4) (24);扩展2的邻居放到 B B B中。现在 A = { 1 , 3 , 2 } , B = { ( 4 − 7 ) , ( 4 − 5 ) } A=\{1,3,2\},B=\{(4-7),(4-5)\} A={1,3,2},B={(47),(45)}。由于 ( 4 − 5 ) (4-5) (45) ( 4 − 7 ) (4-7) (47)更好,丢弃 ( 4 − 7 ) , B = { ( 4 − 5 ) } (4-7),B=\{(4-5)\} (47),B={(45)}
  9. B B B中找到离起点最近的结点,是结点4。在 A A A中加上4,并从 B B B中拿走 ( 4 − 5 ) (4-5) (45)。此时已经没有新邻居可以扩展。现在 A = { 1 , 3 , 2 , 4 } , B A=\{1,3,2,4\},B A={1,3,2,4},B为空,结束。

下面讨论上述步骤的复杂度。图的边共有 m m m个,需要往集合 B B B中扩展 m m m次。在每次扩展后,需要找集合 B B B中距离起点最小的结点。集合 B B B最多可能有 n n n个结点。把问题抽象为每次往集合 B B B中放一个数据,在 B B B中的 n n n个数中找最小值,如何快速完成?如果往 B B B中放数据是乱放,找最小值也是用类似冒泡的简单方法,复杂度是 n n n,那么总复杂度是 O ( n m ) O(nm) O(nm)
上述方法可以改进,得到更好的复杂度。改进的方法如下:

  1. 每次往 B B B中放新数据时按从小到大的顺序放,用二分法的思路,复杂度是 O ( l o g 2 n ) O(log_2n) O(log2n),保证最小的数总在最前面。
  2. 找最小值,直接取 B B B的第一个数,复杂度是 O ( 1 ) O(1) O(1)
    此时 D i j k s t r a Dijkstra Dijkstra算法总的复杂度是 O ( m l o g 2 n ) O(mlog_2n) O(mlog2n),是最高效的最短路径算法。
    在编程时,一般不用自己写上面的程序,直接用STL的优先队列就行了,完成数据的插入和提取。
    下面的程序代码中有两个关键技术:
  3. 用邻接表存图和查找邻居。对邻居的查找和扩展是通过动态数组 v e c t o r < e d g e > e [ N U M ] vector<edge>e[NUM] vector<edge>e[NUM]实现的邻接表,和上一节的 S P F A SPFA SPFA一样。其中 e [ i ] e[i] e[i]存储第i个结点上所有的边,边的一头是它的邻居,即 s t r u c t   e d g e struct\ edge struct edge的参数 t o to to。在需要扩展结点i的邻居的时候,查找 e [ i ] e[i] e[i]即可。已经放到集合 A A A中的结点不要扩展;程序中用 b o o l   d o n e [ N U M ] bool\ done[NUM] bool done[NUM]记录集合 A A A,当 d o n e [ i ] = t r u e done[i]=true done[i]=true时,表示它在集合 A A A中,已经找到了最短路径。
  4. 在集合 B B B中找距离起点最短的结点。直接用STL的优先队列实现,在程序中是 p r i o r i t y _ q u e u e < s _ n o d e > Q priority\_queue<s\_node>Q priority_queue<s_node>Q。但是有关丢弃的动作,STL的优先队列无法做到。例如步骤
  5. 中,需要在 B = { ( 2 − 5 ) , ( 2 − 4 ) , ( 4 − 7 ) } B=\{(2-5),(2-4),(4-7)\} B={(25),(24),(47)}中丢弃 ( 2 − 5 ) (2-5) (25),但是STL没有这种操作。在程序中也是用 b o o l   d o n e [ N U M ] bool\ done[NUM] bool done[NUM]协助解决这个问题。从优先队列 p o p pop pop ( 2 − 4 ) (2-4) (24)时,记录 d o n e [ 2 ] = t r u e done[2]=true done[2]=true,表示结点2已经处理好。下次从优先队列 p o p pop pop ( 2 − 5 ) (2-5) (25)时,判断 d o n e [ 2 ] done[2] done[2] t r u e true true,丢弃。
code(dijkstra的实现):
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, Maxm = 500010;

struct edge{
	int to, dis, next;
}e[Maxm];

int head[Maxm], dis[Maxm], cnt;
bool vis[Maxm];
int n, m, s;

void addEdge(int u, int v, int d){
	cnt++;
	e[cnt].dis = d;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

struct node{
	int dis, pos;
	bool operator <(const node& x)const{
		return x.dis < dis;
	}
};

priority_queue<node>q;

void dijkstra(){
	dis[s] = 0;
	//s 是起点位置
	q.push({0, s});
	//第一个节点据原点的距离为0,位置是s
	while(!q.empty()){
		node tmp = q.top();
		q.pop();
		int x = tmp.pos;
		int d = tmp.dis;
		if(vis[x] == true){
			continue;
			//这个点走过的话就跳过
		}
		vis[x] = true;
		for(int i = head[x]; i != 0;i = e[i].next){
			//i 是沿着一条路一直走,走到尾部之后i会为0
			int y = e[i].to;
			if(dis[y] > dis[x] + e[i].dis){
				dis[y] = dis[x] + e[i].dis;
				if(vis[y] == false){
					q.push({dis[y], y});
					//如果这个点没有走过,就放入这个点
					//和原点的距离是dis[y],位置是y
				}
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n, &m, &s);
	for(int i = 1; i <= n; i++){
		dis[i] = 0x7fffffff;
	}	
	for(int i = 0; i < m; i++){
		int u, v, d;
		scanf("%d%d%d",&u, &v, &d);
		addEdge(u, v, d);
	}
	
	dijkstra();

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/732545.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Excel导出实例

在上一节的基础上&#xff0c;本文演示下如何导出excel数据。 Excel导出操作演示 继承ocean-easyexcel SDK <dependency><groupId>com.angel.ocean</groupId><artifactId>ocean-easyexcel</artifactId><version>1.0.0</version> …

2024头歌数据库期末综合(部分题)

目录 第1关&#xff1a;数据表结构修改1 任务描述 学习补充 答案 第2关&#xff1a;数据记录删除 任务描述 学习补充 答案 第3关&#xff1a;数据表结构修改2 任务描述 学习补充 答案 第5关&#xff1a;数据查询一 任务描述 学习补充 答案 本篇博客声明&…

【ARMv8/ARMv9 硬件加速系列 4 -- 加解密 Cryptographic Extension 介绍】

文章目录 ARMv8.0 Cryptographic ExtensionFEAT_AESFEAT_PMULLFEAT_SHA1FEAT_SHA256ARMv8.2 扩展FEAT_SHA512FEAT_SHA3FEAT_SM3FEAT_SM4ARMv8.0 Cryptographic Extension ARMv8.0引入了加密扩展(Cryptographic Extension),旨在加速加密和解密操作。这一扩展通过新增专用指令…

【Linux】 yum学习

yum介绍 在Linux系统中&#xff0c;yum&#xff08;Yellowdog Updater, Modified&#xff09;是一个用于管理软件包的命令行工具&#xff0c;特别适用于基于RPM&#xff08;Red Hat Package Manager&#xff09;的系统&#xff0c;如CentOS、Fedora和Red Hat Enterprise Linux…

一、docker简介及卸载、安装

目录 一、Docker 简介 二、dockers三要素 1、Docker镜像&#xff08;image&#xff09; 2、Docker仓库 3、Docker容器 三、docker架构图 四. Docker 运行的基本流程 五、docker 卸载 1、停止docker服务 2、查看yum安装的docker文件包 3、查看docker相关的rpm源文件 …

力扣随机一题 模拟+字符串

博客主页&#xff1a;誓则盟约系列专栏&#xff1a;IT竞赛 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 1910.删除一个字符串中所有出现的给定子字符串【中等】 题目&#xff1a; …

利用LabVIEW项目管理和组织LabVIEW应用程序

如何利用LabVIEW项目管理和组织LabVIEW应用程序&#xff0c;提供了关于文件定义、磁盘上的文件组织、LabVIEW项目浏览器、交叉链接和相关资源的建议。这些推荐在开发前就应建立&#xff0c;以确保应用程序能扩展到大量VIs并适应多开发者环境。 目录 定义和识别应用程序文件 磁…

第五篇:构建与维护私有Docker Registry: 企业级实践指南

构建与维护私有Docker Registry: 企业级实践指南 1. 引言&#xff1a;解析私有Docker仓库的必要性 1.1 Docker Registry简介与私有化的好处 Docker Registry是一个用于存储和分发Docker镜像的系统。在Docker生态系统中&#xff0c;Registry扮演着至关重要的角色&#xff0c;为…

labelme使用笔记:目标检测数据集标注和语义分割数据集批量生成

AI应用开发相关目录 本专栏包括AI应用开发相关内容分享&#xff0c;包括不限于AI算法部署实施细节、AI应用后端分析服务相关概念及开发技巧、AI应用后端应用服务相关概念及开发技巧、AI应用前端实现路径及开发技巧 适用于具备一定算法及Python使用基础的人群 AI应用开发流程概…

网优小插件_利用Power Automate Desktop抓取物业点信息

日常在无线网络优化&#xff0c;经常需要提取某一地市&#xff0c;某个属性物业点信息&#xff08;物业点名称、地址、及经纬度信息&#xff09;&#xff0c;本文利用Power Automate Desktop&#xff08;PRA&#xff09;和百度地图经纬度拾取网站&#xff0c;通过自动的方式抓取…

DS:堆的应用——两种算法和TOP-K问题

欢迎来到Harper.Lee的学习世界&#xff01;博主主页传送门&#xff1a;Harper.Lee的博客主页想要一起进步的uu可以来后台找我哦&#xff01; 一、堆的排序 1.1 向上调整——建小堆 1.1.1 代码实现 //时间复杂度&#xff1a;O(N*logN) //空间复杂度&#xff1a;O(logN) for (…

一文带你了解CAN协议 - 趋于完美的通信协议

参考自&#xff1a; 常见的通讯协议总结&#xff08;USART、IIC、SPI、485、CAN&#xff09;-CSDN博客 趋近于完美的通讯 CAN总线&#xff01;4分钟看懂&#xff01;_哔哩哔哩_bilibili 概念 CAN 是控制器局域网络(Controller Area Network)的简称&#xff0c; 它是由研发和生…

C++ GPU编程(英伟达CUDA)

安装编译环境 https://developer.download.nvidia.com/compute/cuda/12.5.0/local_installers/cuda_12.5.0_555.85_windows.exe CMakeLists.txt cmake_minimum_required(VERSION 3.10)set(CMAKE_CXX_STANDARD 17) set(CMAKE_BUILD_TYPE Release) #set(CMAKE_CUDA_ARCHITECTUR…

深度学习前10节

1.机器学习的流程 (1)数据获取 &#xff08;2&#xff09;特征工程 &#xff08;3&#xff09;建立模型 &#xff08;4&#xff09;评估与应用 2.特征工程的作用 &#xff08;1&#xff09;数据特征决定了模型的上限 &#xff08;2&#xff09;预处理和特征提取是最核心的 &…

Java中对象的比较

1. 对象的比较 在Java中&#xff0c;基本类型的对象可以直接比较大小&#xff0c;而自定义类型却不能 class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank rank;this.suit suit;}}public class TestPriori…

C语言入门系列:可迁移的数据类型

文章目录 1&#xff0c;精确宽度类型(exact-width integer type)2&#xff0c;最小宽度类型&#xff08;minimum width type&#xff09;3&#xff0c;最快的最小宽度类型&#xff08;fast minimum width type&#xff09;4&#xff0c;可以保存指针的整数类型。5&#xff0c; …

基于深度学习的图像识别技术与应用是如何?

基于深度学习的图像识别技术与应用在当今社会中扮演着越来越重要的角色。以下是对该技术与应用的详细解析&#xff1a; 一、技术原理 深度学习是一种模拟人脑处理和解析数据的方式的技术和方法论。在图像识别领域&#xff0c;深度学习主要通过深度神经网络&#xff08;如卷积…

计算机网络 交换机的VLAN配置

一、理论知识 1.VLAN的定义 ①VLAN虚拟局域网&#xff0c;是一种通过将局域网内的设备逻辑地而不是物理地划分成一个个网段从而实现虚拟工作组的技术。 ②IEEE于1999年颁布了用以标准化VLAN实现方案的802.1Q协议标准草案。 ③VLAN技术允许网络管理者将一个物理的LAN逻辑地划…

【C++】平衡二叉树(AVL树)的实现

目录 一、AVL树的概念二、AVL树的实现1、AVL树的定义2. 平衡二叉树的插入2.1 按照二叉排序树的方式插入并更新平衡因子2.2 AVL树的旋转2.2.1 新节点插入较高左子树的左侧&#xff08;LL平衡旋转&#xff09;2.2.2 新节点插入较高右子树的右侧&#xff08;RR平衡旋转&#xff09…

python库BeeWare,一个如雷贯耳的可以创建原生应用程序的库

目录 BeeWare 包括以下主要组件和工具&#xff1a; 创建BeeWare虚拟环境 配置BeeWare 创建一个新的BeeWare项目&#xff08; Hello World! &#xff09; 尝试 Hello World 样例 BeeWare 是一个开源项目&#xff0c;旨在帮助开发者使用 Python 创建原生应用程序&#xff0c;…