《数据结构》学习系列——图(中)

系列文章目录

目录

  • 图的遍历
    • 深度优先遍历
      • 递归算法
      • 堆栈算法
    • 广度优先搜索
  • 拓扑排序
    • 定义定理
    • 算法思想
    • 伪代码
  • 关键路径
    • 基本概念
    • 关键活动有关量
    • 数学公式
    • 伪代码
    • 时间复杂性


图的遍历

  • 从给定连通图的某一顶点出发,沿着一些边访问遍图中所有的顶点,且使每个顶点仅被访问一次,称为图的遍历(Graph Traversal)
  • 存在的问题:图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的顶点。
    • 避免重复访问:设置一个标志顶点是否被访问过的辅助数组 visited[],它的初始状态为 0。在图的遍历过程中,一旦某一个顶点 i i i 被访问,就立即让 visited[i] 置为 1,防止它被多次访问

深度优先遍历

  • 深度优先遍历又被称为深度优先搜索 DFS (Depth First Search),其类似于树的先根遍历
  • 基本思想:
    • DFS在访问图中某一起始顶点 v v v 后,由 v v v 出发,访问它的任一邻接顶点 w 1 w_1 w1;再从 w 1 w_1 w1 出发,访问与 w 1 w_1 w1 邻接但还没有访问过的顶点 w 2 w_2 w2;然后再从 w 2 w_2 w2 出发,进行类似的访问。如此往下去,直至到达所有的邻接顶点都被访问过的顶点 u u u 为止。接着,退回一步,退到前一次访问过的顶点,看看还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止
      在这里插入图片描述

递归算法

伪代码

// 图的深度优先遍历的递归算法
DepthFirstSearch(v, visited)
{visited[v] = 1;p = adjacent(Head[v]);while (p != NULL){if (visited[VerAdj(p) != 1]){DepthFirstSearch(VerAdj(p), visited)p = link(p);	}}
}// 算法主体
DFS_Main()
{// 为辅助数组申请空间visited = new int[graphsize];// 数组初始化for (int k = 0; k < graphsize; k++){visited[k] = 0;// 从序号为0的顶点出发,深度优先遍历图DepthFirstSearch(0, visited)delete[] visited;}
}

非连通图需要多次调用深度优先遍历算法

for i = 0 to n-1
{for j = 0 to n-1{if visited[j] = 0{DepthFirstSearch(v[j], visited)}}	
}

算法分析

  • 图中有 n n n 个顶点, e e e 条边
  • 如果用邻接表存储,沿顶点的adjacent可以找到某个顶点 v v v 的所有邻接顶点 w w w。由于总共有 2 e 2e 2e(无向图)或 e e e(有向图)个边结点,所以扫描边的时间为 O ( e ) O(e) O(e)。而且对所有顶点递归访问 1 次,所以遍历图的时间复杂性为 O ( n + e ) O(n + e) O(n+e)
  • 如果用邻接矩阵存储,则查找每一个顶点的所有的边,所需时间为 O ( n ) O(n) O(n),则遍历图中所有的顶点所需的时间为 O ( n 2 ) O(n^2) O(n2)

堆栈算法

  • 可以利用堆栈实现深度优先遍历的非递归算法
  • 堆栈中存放已访问结点的还没有被访问的邻接顶点。每次弹出栈顶元素时,如其未被访问则访问该顶点,检查当前顶点的边链表,将还没有被访问的邻接顶点入栈,循环进行

基本思想
首先将所有顶点的visited[]值置为 0,初始顶点压入堆栈

  • ① 检测堆栈是否为空。若堆栈为空,则迭代结束;否则,从栈顶弹出一个顶点 v v v
  • ② 如果 v v v 未被访问过,则访问 v v v,将visited[v]值更新为 1,然后根据 v v v 的邻接顶点表,将 v v v 的未被访问的邻接顶点压入栈,执行步骤 ①
// 非递归实现深度优先遍历算法
void DFS(Graph &graph, int v) {stack<int> S;         // 创建栈Svector<bool> visited(graph.size(), false); // 初始化访问标记数组S.push(v);            // 将起始顶点压入栈while (!S.empty()) {  // 当栈不为空时int v = S.top();  // 弹出栈顶元素S.pop();if (!visited[v]) {cout << v << " ";  // 访问顶点visited[v] = true; // 标记为已访问// 获取顶点v的所有邻接顶点,并压入栈中for (auto p = graph.adjacent(v); p != nullptr; p = p->link) {if (!visited[p->VerAdj]) {S.push(p->VerAdj);}}}}
}

在这里插入图片描述

算法分析

  • 如果使用邻接表表示图,则循环的总时间代价为 d 0 + d 1 + ⋯ + d n − 1 = O ( e ) d_0 + d_1 + \dots + d_{n-1} = O(e) d0+d1++dn1=O(e),其中 d i d_i di 是顶点 i i i 的度(无向图)或出度(有向图)。总的时间复杂度为 O ( n + e ) O(n + e) O(n+e)
  • 如果使用邻接矩阵,则对于每一个被访问的顶点,循环要检测矩阵中的 n n n 个元素,总的时间代价为 O ( n 2 ) O(n^2) O(n2)

广度优先搜索

  • 为了实现逐层访问,算法中使用了一个队列,以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问
  • 与深度优先搜索过程一样,为避免重复访问,需要一个辅助数组visited[],为被访问过的顶点加标记
// BFS1 [初始化]
CREATEQ(Q);         // 创建队列 Q
for (int i = 1; i <= n; i++) visited[i] = 0; // 初始化所有顶点为未访问
PRINT(v);           // 打印起始顶点
visited[v] = 1;     // 标记起始顶点为已访问
Q.enqueue(v);       // 起始顶点入队列// BFS2 [广度优先遍历]
while (!Q.isEmpty()) {       // 当队列不为空时v = Q.dequeue();         // 队头元素出队p = adjacent(Head[v]);   // 获取当前顶点的邻接链表while (p != NULL) {      // 遍历邻接链表if (visited[p->VerAdj] == 0) { // 如果邻接顶点未被访问Q.enqueue(p->VerAdj);      // 将邻接顶点入队PRINT(p->VerAdj);          // 打印邻接顶点visited[p->VerAdj] = 1;    // 标记邻接顶点为已访问}p = p->link;        // 继续访问下一个邻接顶点}
}

算法分析

  • 如果使用邻接表表示图,则循环的总时间代价为 d 0 + d 1 + ⋯ + d n − 1 = O ( e ) d_0 + d_1 + \dots + d_{n-1} = O(e) d0+d1++dn1=O(e),其中 d i d_i di 是顶点 i i i 的度。总的时间复杂度为 O ( n + e ) O(n + e) O(n+e)
  • 如果使用邻接矩阵,则对于每一个被访问的顶点,循环要检测矩阵中的 n n n 个元素,总的时间代价为 O ( n 2 ) O(n^2) O(n2)

拓扑排序

  • AOV 网:在有向图中,用顶点表示活动,用有向边表示活动之间的先后关系,称这样的有向图为AOV网 (Activity On Vertex Network)}
    • 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外,一般都把工程分为若干个叫做“活动”的子工程。完成了所有这些活动,这个工程就可以完成了
    • 例如,计算机专业学生的学习就是一个工程,每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程,有些则不要求。这样,在有些课程之间有先后关系,有些课程可以并行地学习

在这里插入图片描述

定义定理

  • 在 AOV 网络中,如果活动 V i V_i Vi 必须在活动 V j V_j Vj 之前进行,则存在有向边 ⟨ V i , V j ⟩ \langle V_i, V_j \rangle Vi,Vj
  • AOV 网络中不能出现有向回路,即有向环。在 AOV 网络中如果出现了有向环,则意味着某项活动应以自己作为先决条件。因此,对给定的 AOV 网络,必须先判断它是否存在有向环
  • 拓扑序列:AOV 网中所有顶点排成的线性序列,要求每个活动的所有前驱活动都排在该活动前面
  • 拓扑排序:构造 AOV 网的拓扑序列的过程被称为拓扑排序
  • 如果通过拓扑排序能将 AOV 网络的所有顶点都排入一个拓扑有序的序列中,则该 AOV 网络中必定不会出现有向环;相反,如果得不到满足要求的拓扑有序序列,则说明 AOV 网络中存在有向环,此 AOV 网络所代表的工程是不可行的
  • 设图 G = ( V , E ) G = (V, E) G=(V,E) 是非循环图, V ( G ) ≠ ∅ V(G) \neq \emptyset V(G)=,则 G G G 中一定存在入度为零的顶点。
  • G = ( V , E ) G = (V, E) G=(V,E) 是非循环图, V ( G ) = { 1 , 2 , … , n } V(G) = \{1, 2, \dots, n\} V(G)={1,2,,n} e = ∣ E ( G ) ∣ e = |E(G)| e=E(G)。则算法是正确的,且算法的时间复杂性为 O ( n + e ) O(n + e) O(n+e)

算法思想

  • 拓扑排序算法的基本步骤
    • 从网中选择一个入度为 0 的顶点并将其输出
    • 从网中删除该顶点及其所有出边
    • 执行步骤 ① 和 ②,直至所有顶点都已输出,或网中剩余顶点入度均不为 0(说明网中存在回路,无法继续拓扑排序)
      注意:对于任何无回路的 AOV 网,其顶点均可排成拓扑序列,但其拓扑序列未必唯一

在这里插入图片描述

伪代码

  • 假定 AOV 网用邻接表的形式存储。为实现拓扑排序算法,事先需做好两项准备工作:
  • 建立一个数组count[],count[i]的元素值为顶点 i i i 的入度;
  • 建立一个堆栈,栈中存放入度为 0 的顶点,每当一个顶点的入度为 0,就将其压入栈
// TOrder1 [初始化]
// 计算 count 数组(每个顶点的入度)
for (int i = 1; i <= n; i++) count[i] = 0; // 初始化所有顶点的入度为 0// 遍历邻接表,计算每个顶点的入度
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表头指针while (p != NULL) {    // 遍历邻接表count[VerAdj(p)]++; // 更新邻接顶点的入度p = p->link;        // 移动到下一个邻接点}
}// 拓扑排序
top = 0; // 栈顶指针初始化为 0// 将入度为 0 的顶点压入栈
for (int i = 1; i <= n; i++) {if (count[i] == 0) {stack[top] = i; // 顶点 i 入栈top++;          // 栈顶指针加 1}
}for (int i = 1; i <= n; i++) {// 如果循环体执行了 n 次但栈为空,则说明图中存在回路if (top == 0) {PRINT("There is a cycle in the network!");RETURN;} else {// 栈顶元素出栈j = stack[top - 1];top--; // 栈顶指针减 1PRINT(j); // 输出顶点 j(拓扑序中的一个顶点)// 遍历顶点 j 的邻接表,更新邻接顶点的入度p = adjacent(Head[j]);while (p != NULL) {k = VerAdj(p);    // 获取邻接顶点count[k]--;       // 邻接顶点的入度减 1if (count[k] == 0) { // 如果邻接顶点入度变为 0,则压入栈stack[top] = k;top++;}p = p->link; // 继续遍历下一个邻接点}}
}

关键路径

基本概念

  • 如果在有向无环的带权图中

    • 用有向边表示一个工程中的各项活动 (Activity)
    • 用边上的权值表示活动的持续时间 (Duration)
    • 用顶点表示事件 (Event)
  • 则这样的有向图叫做用边表示活动的网络,简称AOE (Activity On Edges) 网络

    • 源点:表示整个工程的开始(入度为零)
    • 汇点:表示整个工程的结束(出度为零)
  • 在 AOE 网络中,有些活动必须顺序进行,有些活动可以并行进行

  • 从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成

  • 完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径被称为关键路径 (Critical Path)

  • 关键路径:从源点到汇点具有最大长度的路径称为关键路径

  • 路径长度:指路径上的各边权值之和

  • 关键活动:关键路径上的活动

在这里插入图片描述

关键活动有关量

  • 事件 v j v_j vj 的最早发生时间ve(j):

    • 从源点 v 0 v_0 v0 v j v_j vj 的最长路径长度。
  • 事件 v j v_j vj 的最迟发生时间vl(j):

    • 保证汇点的最早发生时间不推迟(即不推迟整个工程完成时间)的前提下,事件 v j v_j vj 允许的最迟发生时间,等于ve(n-1)减去从 v j v_j vj v n − 1 v_{n-1} vn1 的最长路径长度
  • 活动 a i a_i ai 的最早开始时间e(i):

    • 设活动 a i a_i ai 在有向边 ⟨ v j , v k ⟩ \langle v_j, v_k \rangle vj,vk 上,e(i)是从源点 v 0 v_0 v0 v j v_j vj 的最长路径长度。因此e(i) = ve(j)
  • 活动 a i a_i ai 的最迟开始时间l(i):

    • l(i)是在不会引起时间延误的前提下,该活动允许的最迟开始时间。设活动 a i a_i ai 在有向边 ⟨ v j , v k ⟩ \langle v_j, v_k \rangle vj,vk 上,则 l ( i ) = vl(k) − weight ( ⟨ j , k ⟩ ) l(i) = \texttt{vl(k)} - \texttt{weight}(\langle j, k \rangle) l(i)=vl(k)weight(⟨j,k⟩)

数学公式

  • 求所有事件的最早发生时间}:
    递推公式: // 拓扑排序正序
    ve(k) = { 0 , k = 0 max ⁡ { ve(j) + weight ( ⟨ j , k ⟩ ) } , ⟨ v j , v k ⟩ ∈ E ( G ) , k = 1 , 2 , … , n − 1 \texttt{ve(k)} = \begin{cases} 0, & k = 0 \\ \max\{\texttt{ve(j)} + \texttt{weight}(\langle j, k \rangle)\}, & \langle v_j, v_k \rangle \in E(G), \; k = 1, 2, \dots, n-1 \end{cases} ve(k)={0,max{ve(j)+weight(⟨j,k⟩)},k=0vj,vkE(G),k=1,2,,n1

  • 求所有事件的最迟发生时间}:
    递推公式:拓扑排序逆序
    vl(j) = { ve(n-1) , j = n − 1 min ⁡ { vl(k) − weight ( ⟨ j , k ⟩ ) } , ⟨ v j , v k ⟩ ∈ E ( G ) , j = n − 2 , n − 3 , … , 0 \texttt{vl(j)} = \begin{cases} \texttt{ve(n-1)}, & j = n-1 \\ \min\{\texttt{vl(k)} - \texttt{weight}(\langle j, k \rangle)\}, & \langle v_j, v_k \rangle \in E(G), \; j = n-2, n-3, \dots, 0 \end{cases} vl(j)={ve(n-1),min{vl(k)weight(⟨j,k⟩)},j=n1vj,vkE(G),j=n2,n3,,0

伪代码

思路
求关键活动的基本步骤:

  • 对 AOE 网进行拓扑排序,若网中有回路,则终止算法;按拓扑次序求出各顶点事件的最早发生时间 ve
  • 按拓扑序列的逆序求出各顶点事件的最迟发生时间 vl
  • 根据ve和vl的值,求出各活动的最早开始时间 e(i)与最迟开始时间l(i),若e(i) = l(i),则 i i i 是关键活动

在这里插入图片描述

// CPath1 - 计算事件的最早发生时间
// 初始化事件的最早发生时间
for (int i = 1; i <= n; i++) ve[i] = 0; // 最早发生时间初始化为 0// 按拓扑序计算事件的最早发生时间
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表while (p != NULL) {k = VerAdj(p); // 获取邻接顶点if (ve[i] + cost(p) > ve[k]) // 更新最早发生时间ve[k] = ve[i] + cost(p);p = p->link; // 继续访问下一个邻接点}
}// CPath2 - 计算事件的最迟发生时间
// 初始化事件的最迟发生时间
for (int i = 1; i <= n; i++) vl[i] = ve[n]; // 最迟发生时间初始化为最后事件的最早时间// 按拓扑逆序计算事件的最迟发生时间
for (int i = n; i >= 1; i--) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表while (p != NULL) {k = VerAdj(p); // 获取邻接顶点if (vl[k] - cost(p) < vl[i]) // 更新最迟发生时间vl[i] = vl[k] - cost(p);p = p->link; // 继续访问下一个邻接点}
}// CPath3 - 关键活动的最早开始时间和最迟开始时间
// 遍历所有活动,计算关键活动
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表while (p != NULL) {k = VerAdj(p); // 获取邻接顶点e = ve[i]; // 最早开始时间l = vl[k] - cost(p); // 最迟开始时间if (e == l) // 如果最早时间等于最迟时间,则为关键活动PRINT("<", i, ",", k, "> is Critical Activity!");p = p->link; // 继续访问下一个邻接点}
}

时间复杂性

  • 时间复杂性:对顶点进行拓扑排序的时间复杂性为 O ( n + e ) O(n + e) O(n+e),以拓扑次序求ve[i]和按拓扑逆序求vl[i]}时,所需时间均为 O ( e ) O(e) O(e)。求各个活动的e[k]和l[k]的时间复杂度为 O ( e ) O(e) O(e),整个算法的时间复杂性是 O ( n + e ) O(n + e) O(n+e)
  • 定理 6.3:任意的非空 AOE 网至少存在一条关键路径
  • 推论 6.1:假设边 ⟨ T i , T j ⟩ \langle T_i, T_j \rangle Ti,Tj 属于 AOE 网,则有
    vl[j] − ve[i] ≥ Weight ( ⟨ T i , T j ⟩ ) \texttt{vl[j]} - \texttt{ve[i]} \geq \texttt{Weight}(\langle T_i, T_j \rangle) vl[j]ve[i]Weight(⟨Ti,Tj⟩)
  • 且如果 ⟨ T i , T j ⟩ \langle T_i, T_j \rangle Ti,Tj 属于某一条关键路径,则有
    vl[j] − ve[i] = Weight ( ⟨ T i , T j ⟩ ) . \texttt{vl[j]} - \texttt{ve[i]} = \texttt{Weight}(\langle T_i, T_j \rangle). vl[j]ve[i]=Weight(⟨Ti,Tj⟩).

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C++】static修饰的“静态成员函数“--静态成员在哪定义?静态成员函数的作用?

声明为static的类成员称为类的静态成员&#xff0c;用static修饰的成员变量&#xff0c;称之为静态成员变量&#xff1b;用 static修饰的成员函数&#xff0c;称之为静态成员函数。静态成员变量一定要在类外进行初始化 一、静态成员变量 1)特性 所有静态成员为所有类对象所共…

MySQL面试-1

InnoDB中ACID的实现 先说一下原子性是怎么实现的。 事务要么失败&#xff0c;要么成功&#xff0c;不能做一半。聪明的InnoDB&#xff0c;在干活儿之前&#xff0c;先将要做的事情记录到一个叫undo log的日志文件中&#xff0c;如果失败了或者主动rollback&#xff0c;就可以通…

JavaScript中的this指向绑定规则(超全)

JavaScript中的this指向绑定规则&#xff08;超全&#xff09; 1.1 为什么需要this? 为什么需要this? 在常见的编程语言中&#xff0c;几乎都有this这个关键字&#xff08;Objective-C中使用的是self),但是在JavaScript中的this和常见的面向对象语言中的this不太一样 常见面…

Linux---ps命令

​​​​​​Linux ps 命令 | 菜鸟教程 (runoob.com) process status 用于显示进程的状态 USER: 用户名&#xff0c;运行此进程的用户名。PID: 进程ID&#xff08;Process ID&#xff09;&#xff0c;每个进程的唯一标识号%CPU: 进程当前使用的CPU百分比%MEM: 进程当前使用的…

【Spiffo】环境配置:VScode+Windows开发环境

摘要&#xff1a; 在Linux下直接开发有时候不习惯快捷键和操作逻辑&#xff0c;用Windows的话其插件和工具都更齐全、方便&#xff0c;所以配置一个Windows的开发环境能一定程度提升效率。 思路&#xff1a; 自己本地网络内远程连接自己的虚拟机&#xff08;假定用的是虚拟机…

[ubuntu]编译共享内存读取出现read.c:(.text+0x1a): undefined reference to `shm_open‘问题解决方案

问题log /tmp/ccByifPx.o: In function main: read.c:(.text0x1a): undefined reference to shm_open read.c:(.text0xd9): undefined reference to shm_unlink collect2: error: ld returned 1 exit status 程序代码 #include <stdio.h> #include <stdlib.h> #…

Java基于Spring Boot框架的房屋租赁系统,附源码

博主介绍&#xff1a;✌Java老徐、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&…

librdns一个开源DNS解析库

原文地址&#xff1a;librdns一个开源DNS解析库 – 无敌牛 欢迎参观我的个人博客&#xff1a;无敌牛 – 技术/著作/典籍/分享等 介绍 librdns是一个开源的异步多功能插件式的解析器&#xff0c;用于DNS解析。 源代码地址&#xff1a;GitHub - vstakhov/librdns: Asynchrono…

CTFHUB--yeeclass-web

复现平台CTFHUB靶机为一个完整类论坛网页&#xff0c;题目给了服务端完整代码 代码审计 /src/submit.php Line56-63: 可以看到提交数据存入的时候将$_SESSION["username"]."_"作为前缀&#xff0c;生成了一个uniqid。uniqid的生成方式即{sec:08x}{usec:0…

DataWhale—PumpkinBook(TASK05决策树)

课程开源地址及相关视频链接&#xff1a;&#xff08;当然这里也希望大家支持一下正版西瓜书和南瓜书图书&#xff0c;支持文睿、秦州等等致力于开源生态建设的大佬✿✿ヽ(▽)ノ✿&#xff09; Datawhale-学用 AI,从此开始 【吃瓜教程】《机器学习公式详解》&#xff08;南瓜…

计算机网络socket编程(2)_UDP网络编程实现网络字典

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 计算机网络socket编程(2)_UDP网络编程实现网络字典 收录于专栏【计算机网络】 本专栏旨在分享学习计算机网络的一点学习笔记&#xff0c;欢迎大家在评论区交流讨…

51c多模态~合集3

我自己的原文哦~ https://blog.51cto.com/whaosoft/12409223 #TextHarmony 字节联合华师提出统一的多模态文字理解与生成大模型 字节跳动与华东师范大学联合提出的TextHarmony模型&#xff0c;这是一个统一的多模态文字理解与生成大模型&#xff0c;它通过创新的Slide-LoRA…

el-table vue3统计计算数字

固定合计在最下列 父组件 <template><el-tablev-loading"loading"tooltip-effect"light":data"list"style"width: 100%":max-height"maxHeight"element-loading-text"拼命加载中...":header-cell-styl…

【大数据学习 | Spark-Core】详解分区个数

RDD默认带有分区的&#xff0c;那么创建完毕rdd以后他的分区数量是多少&#xff1f; 从hdfs读取文件的方式是最正规的方式&#xff0c;我们通过计算原理可以推出blk的个数和分区数量是一致的&#xff0c;本地化计算。 我们可以发现数据的读取使用的是textInputFormat&#xff…

Mysql的加锁情况详解

最近在复习mysql的知识点&#xff0c;像索引、优化、主从复制这些很容易就激活了脑海里尘封的知识&#xff0c;但是在mysql锁的这一块真的是忘的一干二净&#xff0c;一点映像都没有&#xff0c;感觉也有点太难理解了&#xff0c;但是还是想把这块给啃下来&#xff0c;于是想通…

Java基础-Java多线程机制

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 一、引言 二、多线程的基本概念 1. 线程与进程 2. 多线程与并发 3. 多线程的优势 三、Java多线程的实…

【LeetCode面试150】——202快乐数

博客昵称&#xff1a;沈小农学编程 作者简介&#xff1a;一名在读硕士&#xff0c;定期更新相关算法面试题&#xff0c;欢迎关注小弟&#xff01; PS&#xff1a;哈喽&#xff01;各位CSDN的uu们&#xff0c;我是你的小弟沈小农&#xff0c;希望我的文章能帮助到你。欢迎大家在…

详细教程-Linux上安装单机版的Hadoop

1、上传Hadoop安装包至linux并解压 tar -zxvf hadoop-2.6.0-cdh5.15.2.tar.gz 安装包&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1u59OLTJctKmm9YVWr_F-Cg 提取码&#xff1a;0pfj 2、配置免密码登录 生成秘钥&#xff1a; ssh-keygen -t rsa -P 将秘钥写入认…

Python 获取微博用户信息及作品(完整版)

在当今的社交媒体时代&#xff0c;微博作为一个热门的社交平台&#xff0c;蕴含着海量的用户信息和丰富多样的内容。今天&#xff0c;我将带大家深入了解一段 Python 代码&#xff0c;它能够帮助我们获取微博用户的基本信息以及下载其微博中的相关素材&#xff0c;比如图片等。…

07-SpringCloud-Gateway新一代网关

一、概述 1、Gateway介绍 官网&#xff1a;https://spring.io/projects/spring-cloud-gateway Spring Cloud Gateway组件的核心是一系列的过滤器&#xff0c;通过这些过滤器可以将客户端发送的请求转发(路由)到对应的微服务。 Spring Cloud Gateway是加在整个微服务最前沿的防…