第 41 题
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) 给出算法的基本设计思想（4 分）
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释（9 分）
[tag_link]
1）算法基本设计思想输出拓扑序列的过程如下：依次从图中选取入度为 0 的点进行输出。确保拓扑序列唯一需要保证如下条件：在输出拓扑序列时，每一次有且仅有一个入度为 0 的顶点。所以这题最直观的思路就是进行 numEdges 轮遍历，如果每轮遍历只有一个顶点的入度为 0，则图中存在唯一的拓扑序列；否则不存在唯一的拓扑序列。
2）算法实现
int uniquely(MGraph g)
{
int n = g.numVertices;
int inDegrees[MAXV];
/* 计算所有顶点的入度 */
for (int v = 0; v < n; v++) {
inDegrees[v] = 0;
for (int i = 0; i < n; i++) {
if (g.Edge[i][v] != 0)
inDegrees[v] += g.Edge[i][v];
}
}
/* 进行 n 轮拓扑删除 */
for (int k = 0; k < n; k++) {
int count0 = 0; // 入度为 0 的顶点个数
int v0 = -1; // 本轮唯一可以选择的顶点
/* 找所有入度为 0 的顶点 */
for (int i = 0; i < n; i++) {
if (inDegrees[i] == 0) {
count0++;
v0 = i;
}
}
/* 若不是唯一一个，则拓扑序列不唯一 */
if (count0 != 1) {
return 0;
}
/* “删除”该顶点：将其入度设为 -1，避免重复选取 */
inDegrees[v0] = -1;
/* 更新其所有后继节点的入度 */
for (int j = 0; j < n; j++) {
if (g.Edge[v0][j] != 0)
inDegrees[j]--;
}
}
/* 所有步骤都唯一，拓扑序唯一 */
return 1;
}