PTA：jmu-ds-拓扑排序
给定一个有向图，求其拓扑序列，若有环路，输出error!
注意：本题用栈结构实现入度为0结点存储，否则拓扑序列输出顺序会和测试数据不一致。本题栈结构建议用数组实现，不用栈类。
###你要实现的 函数接口定义：
void TopSort(AdjGraph *G);//邻接表拓扑排序。注：需要在该函数开始计算并初始化每个节点的入度，然后再进行拓扑排序裁判测试程序样例：
#define MAXV 20
#include <iostream>
using namespace std;
typedef struct ANode
{ int adjvex; //该边的终点编号struct ANode *nextarc; //指向下一条边的指针int info; //该边的相关信息，如权重
} ArcNode; //边表节点类型
typedef int Vertex;
typedef struct Vnode
{ Vertex data; //顶点信息int count; //入度ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV];
typedef struct
{ AdjList adjlist; //邻接表int n,e; //图中顶点数n和边数e
} AdjGraph;
void CreateAdj(AdjGraph *&G,int n,int e); //创建图邻接表
void TopSort(AdjGraph *G); //邻接表拓扑排序
void DispAdj(AdjGraph *G); //输出邻接表，供测试
int main()
{int n,e,i,v;AdjGraph *G;cin>>n>>e;CreateAdj(G,n,e);//DispAdj(G);cout<<"拓扑序列:";TopSort(G);
}
void DispAdj(AdjGraph *G)
//输出邻接表G，可以供测试用
{int i;ArcNode *p;for (i=0;i<G->n;i++){p=G->adjlist[i].firstarc;if (p!=NULL) printf("%3d: ",i);while (p!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("\n");}
}
void CreateAdj(AdjGraph *&G,int n,int e) //创建图邻接表
{ int i,j,a,b;ArcNode *p;G=new AdjGraph;for (i=0;i<n;i++) G->adjlist[i].firstarc=NULL;for (i=1;i<=e;i++) //根据输入边建图 { cin>>a>>b; //有向图 p=new ArcNode; //创建一个结点pp->adjvex=b; //存放邻接点p->nextarc=G->adjlist[a].firstarc; //采用头插法插入结点pG->adjlist[a].firstarc=p;}G->n=n; G->e=n;
}
/* 请在这里填写答案 */输入样例1：
5 7
1 0
4 3
2 1
2 0
3 2
4 1
4 2
输出样例1：
顶点编号空格隔开，尾部不带空格。
拓扑序列:4 3 2 1 0
输入样例2：
5 8
0 3
1 0
4 3
2 1
2 0
3 2
4 1
4 2
输出样例：
error!先说说拓扑排序的实现思想：
因为 a ，b两个顶点是没有前驱的顶点的，所以说先用a（或b也一样）入栈，然后擦除 a 指出去的箭头（相当于独立出来了），然后再看剩下的没有前驱顶点的顶点，重复这个操作，直到图空。
详细流程就是：
因为这道题有说到需要用栈，那用栈的算法思想就在这里了：
CountInDegree(G,indegree); // 对各顶点求入度。
InitStack(S);
for ( i=0; i<G.vexnum; ++i)if (!indegree[i]) Push(S, i); // 入度为零的顶点入栈
count=0; // 对输出顶点计数
while (!EmptyStack(S)) {Pop(S, v); ++count; printf(v);for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){--indegree(w); // 弧头顶点的入度减一if (!indegree[w]) Push(S, w);// 新产生的入度为零的顶点入栈}
}
if ( count<G.vexnum )printf("图中有回路");整理一下，那这道题的最终代码在这，，
代码如下：
void TopSort(AdjGraph *G) {// 初始化入度数组for (int i = 0; i < G->n; i++) {G->adjlist[i].count = 0;}// 计算每个节点的入度for (int i = 0; i < G->n; i++) {ArcNode *p = G->adjlist[i].firstarc;while (p != NULL) {G->adjlist[p->adjvex].count++;p = p->nextarc;}}// 使用数组实现栈结构存储入度为0的节点int stack[MAXV];int top = -1;// 将初始入度为0的节点压入栈for (int i = 0; i < G->n; i++) {if (G->adjlist[i].count == 0) {stack[++top] = i;}}// 拓扑排序结果计数int count = 0;// 存储拓扑序列int result[MAXV];// 处理栈中的节点while (top != -1) {int u = stack[top--]; // 弹出栈顶节点result[count++] = u; // 记录拓扑序列// 遍历u的所有邻接节点ArcNode *p = G->adjlist[u].firstarc;while (p != NULL) {int v = p->adjvex;G->adjlist[v].count--; // 邻接节点入度减1if (G->adjlist[v].count == 0) {stack[++top] = v; // 新的入度为0的节点入栈}p = p->nextarc;}}// 判断是否存在环路if (count < G->n) {cout << "error!";} else {// 输出拓扑序列for (int i = 0; i < count; i++) {if (i > 0) cout << " ";cout << result[i];}}
}