首页 > 试题广场 >

一个大型的项目组成通常是由多个模块共同构成的。在项目编译阶段

[问答题]

一个大型的项目组成通常是由多个模块共同构成的。在项目编译阶段各个模块之间可能存在着依赖关系,现有一个二维数组depend[num][num+1]分别记录了模块0-num-1)的依赖项,数组每一行的首个元素为该模块的依赖数量n。接下来的n个元素为所依赖模块的ID。列如,depend[0]={3,2,3,4}表示模块0依赖3个其他模块,分别是模块2,3,4。试设计算法输出编译系统所有可能的编译顺序到控制台;若模块存在循环依赖,则输出错误信息到控制台;并对算法时间和控件复杂度进行分析。

函数原型:int dependAnalysis(int arr[num][num])

    这个问题其实就是一个涉及到图论的问题,二维数组表示的是一个有向图,depend[0]={3,2,3,4}表示节点2,3,4分别有一条边通向节点0,把这整一个图用邻接矩阵或者邻接表表示出来后,找出这个图所有可能的拓扑排序,就是这个编译系统所有可能的编译顺序。在拓扑排序的过程中如果检测到环,就输出错误信息。
    具体代码就不贴出来了,去百度搜索如何找到有向图的所有拓扑排序就能看到很多具体解法
编辑于 2017-03-04 15:36:18 回复(0)