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

一、拓扑学拓扑学topology是数学中一个重要的分支。它源于几何学是用来研究几何图形在连续变形下保持不变的性质。拓扑学有三个关键的概念拓扑空间即研究的基本对象指具有最基本的结构的一组数学对象。可看作一个定义了“邻接”关系的点的集合连续变形指不撕裂打孔、不粘合的拉伸、扭曲变化拓扑不变量在连续变形的过程中保持不变的全局变量拓扑学发展到现在可以划分成几个不同的分支如点集拓扑、代数拓扑、微分拓扑以及几何拓扑等等。网上有一个甜甜圈和咖啡杯的例子非常好理解。二、计算机与拓扑学基础学科的发展最终影响到的是应用科学拓扑学也是如此。随着计算机技术的发展拓扑学与其也紧密的结合起来。现代的计算机技术中应用到拓扑学的方向有机器人领域通过拓扑学对机器人的运动空间规划来进行处理从中发现最可行的运动路径AI拓扑数据的处理可以引入到机器学习的模型中现在也提出了拓扑机器学习等新方向计算机图形学它属于直观的体现拓扑学在计算机技术中应用的一个场景。通过拓扑学的性质实现3D建模等的生成简化、拓扑修复以及相关的映射展开等数据分析这是一个比较热门的前沿技术将代数拓扑与机器学习结合在一起进行高维数据、生物信息等的分析网络及分布式系统这是个传统的拓扑学应用的场景对于路由算法、拓扑设计及Overlay Network设计都有着重要的作用基础理论拓扑学可以用在新算法的研究、新的编程范式等等拓扑学在量子计算和芯片设计与EDA中也有着重要作用。所以说掌握一些拓扑学的知识还是非常必要的。正所谓“山不厌高海不厌深”。三、拓扑排序说了这么多还是要把拓扑落实到具体的一个技术点。在学习排序时大家可能接触过各种排序比如分组、快速以及堆排序等等。但可能没有接触过拓扑排序。拓扑排序与上面的排序明显不同它不是用来对数据进行大小排序的而是用来解决依赖关系顺序的。可以理解为另外一种抽象的排序。举一个简单的例子启动一台机器一般需要几个步骤上电检查状态启动运行结束。有没有发现它的一些特性所以在计算机图论中拓扑排序是对有向无环图DAG的顶进行线性排序的算法。明白了这个立刻就明白了前面分析过很多回的并行系统下的任务统筹机制或者说并行任务算法的分配和调度恰好可以体现这个拓扑排序。但这也恰恰限定了拓扑排序只适合于有向无环图的排序而不是如快排等排序算法的普适性排序。四、分析实现拓扑排序常见的方式有两种Kahn算法卡恩算法它有点类似于剥洋葱先找到入度为0的节点然后把它们及从其出的边删除。不断重复直到所有节点取出。如果出现剩余节点则表示有环这就不对了DFS算法深度优先搜索对节点进行深度优先的遍历递归到最深的叶子节点然后将当前节点加入结果栈的栈顶。保证在递归展开时父节点与子节点保持先后顺序这样其实就可以很明显的看出拓扑排序具可能存在着多可能。这也符合在实际应用中的特点。一般来说其时间复杂度O(VE)其中V是顶点数E是边数。五、拓扑排序的应用拓扑排序在计算机中应用还是比较广泛的。常见的有并行任务调度管理编译器构建工具包项目管理器其实还有很多应用大家可以分析一下身边有哪些模块使用了拓扑排序用来加深印象。六、例程下面给出一个拓扑排序的例子#includealgorithm#includeiostream#includequeue#includevectorstd::vectorinttopologicalSort(intn,conststd::vectorstd::pairint,intedges){std::vectorstd::vectorintadj(n);std::vectorintinDegree(n,0);for(constautoe:edges){intue.first;intve.second;adj[u].push_back(v);inDegree[v];}std::queueintq;for(inti0;in;i){if(inDegree[i]0){q.push(i);}}std::vectorintresult;while(!q.empty()){intuq.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::couterror,has a cyclestd::endl;return{};}returnresult;}intmain(){intcount5;std::vectorstd::pairint,intedges{{0,1},{0,2},{1,3},{2,3},{3,4}};std::vectorintsortedRettopologicalSort(count,edges);if(!sortedRet.empty()){std::coutTopological sort result: ;for(intn:sortedRet){std::coutn ;}std::coutstd::endl;}return0;}上面是一个Kahn算法的拓扑排序的例子可以上机试一下。七、总结数学中的拓扑学是一个较新的领域。不过对于开发者来说如果没有特殊的需求可以不必深入学习。简单了解即可。而且确实在大多数的应用场景下对拓扑学的应用还是非常少的。