2023年10月26日,神舟十七号载人飞船发射取得圆满成功,再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程,为了保证工程的有序开展,需要明确各子工程的前导子工程,以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G采用邻接矩阵存储,类型定义如下。

请设计算法:intuniquely(MGraqhG),判定G是否存在唯一的拓扑序列,若是,则返回1,否则返回0。要求如下。1)给出算法的基本设计思想。(4分)2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。(9分)

【正确答案】

算法的基本设计思想:

建立图G各顶点的入度表degree[]。

选择入度为0的顶点v,将v的所有邻接点的入度减1,重复执行这个过程。若每次选中的入度为0的顶点有且仅有一个,且共进行了GnumVertices次,则意味着存在唯一的拓扑序列,返回1,否则不存在拓扑序列,或者存在多个拓扑序列,返回0。

用C语言描述的算法如下:

【答案解析】