数据结构
2024-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分）
答案
【答案】
(1) 算法的基本设计思想
首先计算图 G 所有顶点的入度，并记录入度为 0 的顶点。然后重复以下步骤：若当前入度为 0 的顶点有且仅有一个，则将其删除（即将其所有邻接点的入度减 1），并更新入度表。若在整个过程中，每次都有且仅有一个入度为 0 的顶点，且最终删除了所有顶点，则存在唯一的拓扑序列；否则，不存在或存在多个拓扑序列。
(2) 算法的 C 语言描述
int uniquely(MGraph G) {
int *degree, i, j, count = 0;
degree = (int *)malloc(G.numVertices * sizeof(int));
for (j = 0; j < G.numVertices; j++) {
degree[j] = 0;
for (i = 0; i < G.numVertices; i++) {
degree[j] += G.Edge[i][j];
}
} // 建立入度表degree[]
int zero_count, zero_vertex;
while (count < G.numVertices) {
zero_count = 0;
zero_vertex = -1;
for (j = 0; j < G.numVertices; j++) {
if (degree[j] == 0) {
zero_count++;
zero_vertex = j;
if (zero_count > 1) break; // 超过一个入度为0的点，退出
}
}
if (zero_count != 1) { // 有多个或没有入度为0的结点
free(degree);
return 0;
}
count++;
degree[zero_vertex] = -1;
for (j = 0; j < G.numVertices; j++) {
if (G.Edge[zero_vertex][j] > 0) {
degree[j]--;
}
}
}
free(degree);
return 1;
}关键注释： 每轮必须恰好存在一个入度为 0 的顶点；若为 0 个，说明有环，若多于 1 个，说明拓扑序列不唯一，两种情况都返回 0。