网站换ip影响 百度,wordpress 添加关键词和描述,怎么看一个网站是不是仿站,优购物app最新版下载系列文章目录
目录 图的遍历深度优先遍历递归算法堆栈算法 广度优先搜索 拓扑排序定义定理算法思想伪代码 关键路径基本概念关键活动有关量数学公式伪代码时间复杂性 图的遍历
从给定连通图的某一顶点出发#xff0c;沿着一些边访问遍图中所有的顶点#xff0c;且使每个顶点…系列文章目录
目录 图的遍历深度优先遍历递归算法堆栈算法 广度优先搜索 拓扑排序定义定理算法思想伪代码 关键路径基本概念关键活动有关量数学公式伪代码时间复杂性 图的遍历
从给定连通图的某一顶点出发沿着一些边访问遍图中所有的顶点且使每个顶点仅被访问一次称为图的遍历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(ne)如果用邻接矩阵存储则查找每一个顶点的所有的边所需时间为 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) {stackint S; // 创建栈Svectorbool 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) d0d1⋯dn−1O(e)其中 d i d_i di 是顶点 i i i 的度无向图或出度有向图。总的时间复杂度为 O ( n e ) O(n e) O(ne)如果使用邻接矩阵则对于每一个被访问的顶点循环要检测矩阵中的 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) d0d1⋯dn−1O(e)其中 d i d_i di 是顶点 i i i 的度。总的时间复杂度为 O ( n e ) O(n e) O(ne)如果使用邻接矩阵则对于每一个被访问的顶点循环要检测矩阵中的 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(ne)
算法思想
拓扑排序算法的基本步骤 从网中选择一个入度为 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} vn−1 的最长路径长度 活动 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⟩)},k0⟨vj,vk⟩∈E(G),k1,2,…,n−1 求所有事件的最迟发生时间} 递推公式拓扑排序逆序 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⟩)},jn−1⟨vj,vk⟩∈E(G),jn−2,n−3,…,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(ne)以拓扑次序求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(ne)定理 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⟩).
