数据结构和算法—拓扑的应用

一、拓扑学

拓扑学，topology，是数学中一个重要的分支。它源于几何学是用来研究几何图形在连续变形下保持不变的性质。拓扑学有三个关键的概念：
拓扑空间：即研究的基本对象，指具有最基本的结构的一组数学对象。可看作一个定义了“邻接”关系的点的集合
连续变形：指不撕裂（打孔）、不粘合的拉伸、扭曲变化
拓扑不变量：在连续变形的过程中保持不变的全局变量
拓扑学发展到现在，可以划分成几个不同的分支，如点集拓扑、代数拓扑、微分拓扑以及几何拓扑等等。网上有一个甜甜圈和咖啡杯的例子，非常好理解。

二、计算机与拓扑学

基础学科的发展，最终影响到的是应用科学，拓扑学也是如此。随着计算机技术的发展，拓扑学与其也紧密的结合起来。现代的计算机技术中，应用到拓扑学的方向有：

1. 机器人领域
   通过拓扑学对机器人的运动空间规划来进行处理，从中发现最可行的运动路径
2. AI
   拓扑数据的处理可以引入到机器学习的模型中，现在也提出了拓扑机器学习等新方向
3. 计算机图形学
   它属于直观的体现拓扑学在计算机技术中应用的一个场景。通过拓扑学的性质实现3D建模等的生成简化、拓扑修复以及相关的映射展开等
4. 数据分析
   这是一个比较热门的前沿技术，将代数拓扑与机器学习结合在一起，进行高维数据、生物信息等的分析
5. 网络及分布式系统
   这是个传统的拓扑学应用的场景，对于路由算法、拓扑设计及Overlay Network设计都有着重要的作用
6. 基础理论
   拓扑学可以用在新算法的研究、新的编程范式等等

拓扑学在量子计算和芯片设计与EDA中也有着重要作用。所以说，掌握一些拓扑学的知识还是非常必要的。正所谓“山不厌高，海不厌深”。

三、拓扑排序

说了这么多，还是要把拓扑落实到具体的一个技术点。在学习排序时，大家可能接触过各种排序，比如分组、快速以及堆排序等等。但可能没有接触过拓扑排序。
拓扑排序与上面的排序明显不同，它不是用来对数据进行大小排序的，而是用来解决依赖关系顺序的。可以理解为另外一种抽象的排序。举一个简单的例子，启动一台机器，一般需要几个步骤，上电，检查状态，启动，运行，结束。有没有发现它的一些特性？
所以在计算机图论中，拓扑排序是对有向无环图（DAG）的顶进行线性排序的算法。明白了这个，立刻就明白了前面分析过很多回的并行系统下的任务统筹机制或者说并行任务算法的分配和调度恰好可以体现这个拓扑排序。但这也恰恰限定了，拓扑排序只适合于有向无环图的排序，而不是如快排等排序算法的普适性排序。

四、分析

实现拓扑排序常见的方式有两种：

1. Kahn算法（卡恩算法）
   它有点类似于剥洋葱，先找到入度为0的节点，然后把它们及从其出的边删除。不断重复，直到所有节点取出。如果出现剩余节点则表示有环，这就不对了
2. DFS算法（深度优先搜索）
   对节点进行深度优先的遍历，递归到最深的叶子节点，然后将当前节点加入结果栈的栈顶。保证在递归展开时，父节点与子节点保持先后顺序
   这样其实就可以很明显的看出，拓扑排序具可能存在着多可能。这也符合在实际应用中的特点。一般来说，其时间复杂度O(V+E)，其中V是顶点数，E是边数。

五、拓扑排序的应用

拓扑排序在计算机中应用还是比较广泛的。常见的有：

1. 并行任务调度管理
2. 编译器构建工具
3. 包项目管理器

其实还有很多应用，大家可以分析一下身边有哪些模块使用了拓扑排序，用来加深印象。

六、例程

下面给出一个拓扑排序的例子：

#include<algorithm>#include<iostream>#include<queue>#include<vector>std::vector<int>topologicalSort(intn,conststd::vector<std::pair<int,int>>&edges){std::vector<std::vector<int>>adj(n);std::vector<int>inDegree(n,0);for(constauto&e:edges){intu=e.first;intv=e.second;adj[u].push_back(v);inDegree[v]++;}std::queue<int>q;for(inti=0;i<n;++i){if(inDegree[i]==0){q.push(i);}}std::vector<int>result;while(!q.empty()){intu=q.front();q.pop();result.push_back(u);for(intv:adj[u]){inDegree[v]--;if(inDegree[v]==0){q.push(v);}}}if(result.size()!=n){std::cout<<"error,has a cycle！"<<std::endl;return{};}returnresult;}intmain(){intcount=5;std::vector<std::pair<int,int>>edges={{0,1},{0,2},{1,3},{2,3},{3,4}};std::vector<int>sortedRet=topologicalSort(count,edges);if(!sortedRet.empty()){std::cout<<"Topological sort result: ";for(intn:sortedRet){std::cout<<n<<" ";}std::cout<<std::endl;}return0;}

上面是一个Kahn算法的拓扑排序的例子，可以上机试一下。

七、总结

数学中的拓扑学是一个较新的领域。不过对于开发者来说，如果没有特殊的需求，可以不必深入学习。简单了解即可。而且确实在大多数的应用场景下，对拓扑学的应用还是非常少的。