2023 年 10 月 26 日，神舟十七号载人飞船发

第1题

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;
}