考研笔记

板子：拓扑排序（2024）

反复做两件事：找一个入度为 0 的顶点输出；删掉它的所有出边，也就是让它指向的顶点入度减 1。最后输出不满 个，说明图里有环。

代码：邻接表（教材写法）

bool TopologicalSort(ALGraph &G, int print[]) {   // 拓扑序列存进 print[]；有环返回 false
    int indegree[MAXV] = {0};                // 每个顶点当前的入度
    for (int i = 0; i < G.vexnum; i++)       // 扫一遍所有边表，统计入度
        for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->nextarc)
            indegree[p->adjvex]++;
    int st[MAXV], top = -1;                  // 栈里放入度为 0 的顶点（换成队列也可以）
    for (int i = 0; i < G.vexnum; i++)
        if (indegree[i] == 0) st[++top] = i;
    int cnt = 0;                             // 已经输出的顶点个数
    while (top != -1) {
        int v = st[top--];
        print[cnt++] = v;                    // 输出 v
        for (ArcNode *p = G.vertices[v].firstarc; p != NULL; p = p->nextarc)
            if (--indegree[p->adjvex] == 0)  // 删掉 v 的出边；邻接点的入度减到 0 就入栈
                st[++top] = p->adjvex;
    }
    return cnt == G.vexnum;                  // 没输出完所有顶点：剩下的顶点在环上
}

代码：判断拓扑序列是否唯一（2024，邻接矩阵）

int uniquely(MGraph G) {                     // 拓扑序列存在而且唯一时返回 1，否则返回 0
    int n = G.numVertices, indegree[MAXV];
    for (int j = 0; j < n; j++) {            // 第 j 列非零元素的个数就是 j 的入度
        indegree[j] = 0;
        for (int i = 0; i < n; i++)
            if (G.Edge[i][j] != 0) indegree[j]++;
    }
    for (int k = 0; k < n; k++) {            // 每轮输出一个顶点，一共 n 轮
        int v = -1, zero = 0;                // zero：当前入度为 0（而且还没输出）的顶点个数
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0) { zero++; v = i; }
        if (zero != 1) return 0;             // 0 个：有环，不存在拓扑序列；2 个以上：不唯一
        indegree[v] = -1;                    // 标记 v 已经输出，以后不会再被当成入度为 0
        for (int j = 0; j < n; j++)          // 删掉 v 的出边
            if (G.Edge[v][j] != 0) indegree[j]--;
    }
    return 1;
}

复杂度：邻接表版时间 ；邻接矩阵版时间 。空间都是 。

关键边界

位置为什么
cnt == G.vexnum环上每个顶点都有一个在环上的前驱，它们的入度永远减不到 0，所以输出个数不够
用栈还是队列都可以。只影响同时有多个入度为 0 的顶点时先输出哪个，得到的都是合法的拓扑序列
唯一性：每轮入度为 0 的顶点恰好 1 个0 个说明有环；2 个以上说明这一步可以任选，序列就不唯一
indegree[v] = -1用 表示「已经输出」，省掉一个标记数组

易错点

  • 删边时要让 指向的顶点入度减 1，不是 自己。
  • 「各顶点排成一条线性序列」只是拓扑序列唯一的充分条件，不是必要条件。判断唯一性就按每一轮入度为 0 的顶点是否唯一来判。
  • 逆拓扑排序每次输出出度为 0 的顶点。另一种得到逆拓扑序列的方法是 DFS：按「顶点访问完」的先后顺序输出。

链接

反向链接