mvc 门户网站开发框架,贵州建设官方网站,seo排名的方法,wordpress网站翻译目录 一、拓扑排序介绍
定义
特点
实现方法#xff08;2种#xff09;
应用
二、题目与题解
题目#xff1a;卡码网 117. 软件构建
题目链接
题解#xff1a;拓扑排序 - Kahn算法#xff08;BFS#xff09;
三、小结 一、拓扑排序介绍
对于拓扑排序#xff0c…目录 一、拓扑排序介绍
定义
特点
实现方法2种
应用
二、题目与题解
题目卡码网 117. 软件构建
题目链接
题解拓扑排序 - Kahn算法BFS
三、小结 一、拓扑排序介绍
对于拓扑排序可以看看b站这个视频了解一下基本原理图-拓扑排序
定义
拓扑排序Topological Sorting是对有向无环图Directed Acyclic Graph简称DAG进行排序的一种算法。在图论中拓扑排序为一个线性序列这个序列满足对于每一条有向边(u, v)u在序列中都出现在v之前。换句话说拓扑排序是对有向图顶点的一种线性排序使得对于每一条有向边(u, v)u在排序中都在v之前。
特点
一、有向无环图拓扑排序只适用于DAG如果图中存在环则无法进行拓扑排序。故可以通过拓扑排序检查图中是否存在环
二、线性序列拓扑排序的结果是一个线性的序列满足边的方向性要求。
三、唯一性一个DAG可能有多个拓扑排序序列。
实现方法2种 Kahn算法BFS 计算所有顶点的入度。将所有入度为0的顶点入队。当队列非空时 从队列中取出一个顶点将其添加到拓扑序列中。减少其所有出边指向的顶点的入度。如果某个顶点的入度变为0将其入队。 深度优先搜索DFS 对于每个顶点如果它没有被访问过从它开始进行深度优先搜索。在DFS结束时将该顶点添加到拓扑序列的开始位置。重复上述过程直到所有的顶点都被访问过。
应用 项目调度1在项目管理中确定任务执行的顺序使得所有前置任务都完成后才开始后续任务。 2在敏捷开发或瀑布模型中确定各个阶段的完成顺序。 课程安排在大学课程设计中确定课程的学习顺序考虑到某些课程是其他课程的前提条件。 编译依赖在编译大型软件项目时确定源文件的编译顺序以确保所有依赖关系都得到满足。 任务优先级在操作系统中确定进程或线程的执行顺序考虑到某些任务必须在其他任务之后执行。 网站链接结构分析确定网页之间的链接关系用于搜索引擎优化或网站导航设计。 事件序列化在日志分析中确定事件发生的先后顺序特别是当事件之间存在因果关系时。 文件依赖解析在文件系统或版本控制系统中确定文件修改的顺序以避免冲突和错误。 有向无环图分析在任何DAG有向无环图的分析中确定顶点的一个线性序列使得对于每一条有向边(u, v)u在序列中都出现在v之前。 层次结构排序确定组织结构或分类层次中的元素的顺序如公司员工、产品类别等。
二、题目与题解
题目卡码网 117. 软件构建
题目链接
117. 软件构建 (kamacoder.com) 题目描述 某个大型软件项目的构建系统拥有 N 个文件文件编号从 0 到 N - 1在这些文件中某些文件依赖于其他文件的内容这意味着如果文件 A 依赖于文件 B则必须在处理文件 A 之前处理文件 B 0 A, B N - 1。请编写一个算法用于确定文件处理的顺序。 输入描述 第一行输入两个正整数 N, M。表示 N 个文件之间拥有 M 条依赖关系。 后续 M 行每行两个正整数 S 和 T表示 T 文件依赖于 S 文件。 输出描述 输出共一行如果能处理成功则输出文件顺序用空格隔开。 如果不能成功处理相互依赖则输出 -1。 输入示例 5 4
0 1
0 2
1 3
2 4 输出示例 0 1 2 3 4 提示信息 文件依赖关系如下 所以文件处理的顺序除了示例中的顺序还存在 0 2 4 1 3 0 2 1 3 4 等等合法的顺序。 数据范围 0 N 10 ^ 5 1 M 10 ^ 9 每行末尾无空格。 题解拓扑排序 - Kahn算法BFS
这题是拓扑排序一个基本的应用文件依赖问题。
Kahn算法的基本思路 计算所有顶点的入度。将所有入度为0的顶点入队。当队列非空时 从队列中取出一个顶点将其添加到拓扑序列中。减少其所有出边指向的顶点的入度。如果某个顶点的入度变为0将其入队。 代码如下
#include bits/stdc.h
using namespace std;int main()
{int n, m; // n表示文件数量m表示依赖关系的数量cin n m;vectorint inDegree(n, 0); // 初始化所有文件的入度为0// 使用哈希表存储文件依赖关系键key为文件编号值value为依赖于该文件的文件列表unordered_mapint, vectorint dependencies;vectorint ans; // 用于存储拓扑排序的结果// 读取依赖关系并构建依赖图for (int i 0; i m; i){int s, t;cin s t;inDegree[t]; // 文件t依赖于文件s因此文件t的入度增加dependencies[s].push_back(t); // 记录文件s的依赖列表}// 初始化队列将所有入度为0的文件加入队列queueint q;for (int i 0; i n; i){if (inDegree[i] 0){q.push(i);}}// 进行拓扑排序while (!q.empty()){int cur q.front(); // 取出当前入度为0的文件q.pop();ans.push_back(cur); // 将其加入拓扑排序结果中for (int next : dependencies[cur]) // 遍历当前文件依赖的所有文件{--inDegree[next]; // 减少依赖文件的入度if (inDegree[next] 0) // 如果入度变为0说明所有依赖的文件都已经处理过可以将其加入队列{q.push(next);}}}// 检查是否所有文件都已处理如果没有说明存在循环依赖if (ans.size() n){// 输出拓扑排序结果for (int i 0; i ans.size(); i){cout ans[i];if (i ans.size() - 1){cout ; // 在文件编号之间添加空格最后一个文件后不加空格特别注意}}}else // 如果结果集大小不等于文件数量说明存在循环依赖{cout -1 endl;}return 0;
}这题当然也可以通过DFS实现即是采用递归的思路这里就不过多介绍了。对于拓扑排序问题一般选择Kahn算法。
三、小结
最近图论章节的难度较大打卡有延误。不过训练营的打卡也快要结束了后边会继续加油打卡
