2023 年 10 月 26 日，神舟十七号载人飞船发
2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G 采用邻接矩阵存储，类型定义如下。
typedef struct //图的类型定义
{
int numVertices, numEdges;//图的顶点数和有向边数
char VerticesList[MAXV];//顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;请设计算法
int uniquely(MGraph G)
，判定G 是否存在唯一的拓扑序列，若是，则返回1，否则返回 0。要求如下。
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
答案
1）算法基本设计思想
建立图 G 各顶点的入度表indegree[]。选择入度为0的顶点 v，将v 的所有邻接点的入度减1，重复执行这个过程。若每次选中的入度为0的顶点有且仅有一个，且共进行了 G.numVertices 次，则意味着存在唯一的拓扑序列，返回 1，否则不存在拓扑序列，或者存在多个拓扑序列，返回0。
2）算法实现
int uniquely(MGraph g)
{
// 表示每个顶点的入度
int inDegrees[g.numVertices];
for (int v = 0; v < g.numVertices; v++) {
for (int i = 0; i < g.numVertices; i++) {
inDegrees[v] += g.Edge[i][v];
}
}
// 遍历 numVertices 轮，每一轮判断是否 有且仅有 唯一的入度为 0 的顶点
for (int v = 0; v < g.numVertices; v++) {
// 入度为 0 的顶点个数
int count0 = 0;
// 来记录这一轮入度为 0 的顶点编号
int targetv = -1;
for (int i = 0; i < g.numVertices; i++) {
if (inDegrees[i] == 0) {
targetv = i;
count0++;
}
}
// 不存在唯一的拓扑序列
if (count0 != 1) {
return 0;
}
// 进行入度修改
for (int j = 0; j < g.numVertices; j++) {
inDegrees[j] -= g.Edge[targetv][j];
}
}
// 存在唯一的拓扑序列
return 1;
}