C++实现拓扑排序的栈基础代码解析

"拓扑排序的C++源代码是一个使用栈数据结构实现的算法，用于对有向无环图(DAG)进行排序。" 拓扑排序是图论中的一个重要概念，它对有向无环图的顶点进行线性排序，使得对于图中的每条有向边 (u, v)，顶点 u 的排序位置总是在顶点 v 之前。在实际应用中，拓扑排序常用于解决任务调度、依赖关系分析等问题。 在提供的源代码中，首先定义了一个静态大小的栈 `sqStack` 结构体，包含元素数组 `elem`，栈顶指针 `top` 和栈的大小 `stackSize`。接着定义了初始化栈、压栈和出栈的函数，分别对应 `initStack_Sq`，`push` 和 `pop`。 接下来，源码定义了表示图中边的结构体 `EdgeNode`，包含邻接顶点 `adjvex` 和指向下一个边的指针 `nextedge`。同时，定义了表示顶点的结构体 `VexNode`，包含顶点信息 `vex`，指向第一个边的指针 `firstedge`，以及入度 `indegree`（指向该顶点的边的数量）。 整个图由结构体 `LGraph` 表示，包含顶点数组 `vexs`，顶点数量 `vexnum` 和边的数量 `edgenum`。`CreateDG_AL` 函数用于创建有向图，读取输入的顶点数和边数，以及每个边的起始和结束顶点，然后构建边的链表结构。 拓扑排序的核心算法通常包括以下步骤： 1. 初始化一个空栈，并计算所有顶点的入度。 2. 将所有入度为0的顶点压入栈中。 3. 当栈不为空时，弹出一个顶点并访问它。将其所有相邻顶点的入度减一。如果某个相邻顶点的入度变为0，则将它压入栈中。 4. 如果能够完成所有顶点的访问，那么就得到了一个有效的拓扑排序；否则，说明图中存在环，拓扑排序无法执行。 源代码中没有给出完整的拓扑排序实现，但根据描述，可以补充以下拓扑排序的函数： ```cpp void topologicalSort(LGraph& G, sqStack& S) { for (int i = 0; i < G.vexnum; i++) { if (G.vexs[i].indegree == 0) { push(S, i); } } while (!isEmpty(S)) { int currVex = pop(S); cout << G.vexs[currVex].vex << " "; EdgeNode* p = G.vexs[currVex].firstedge; while (p != NULL) { G.vexs[p->adjvex].indegree--; if (G.vexs[p->adjvex].indegree == 0) { push(S, p->adjvex); } p = p->nextedge; } } // 如果此时栈为空，说明成功进行了拓扑排序 // 否则，说明图中存在环 } ``` 这个函数首先将所有入度为0的顶点压入栈，然后循环处理栈中的顶点，每次弹出一个顶点并更新其相邻顶点的入度。当栈为空时，表示完成了拓扑排序，输出排序后的顶点顺序。如果在此过程中栈仍为空，说明图中可能存在环，拓扑排序无法执行。