参考答案

正确答案：int flag[];count=0;success=1; ／*success：测试拓扑排序是否成功*／InitQueue(Q);voidDFSTopSort(ALGraphG){ ／*对以邻接表为存储结构的有向图G进行拓扑排序*／for(v=0jV<G．vexnum；v++) ／*标志位初始化*／{visited[v]=0;flag[v]=0;)for(V=0；v<G vexnum；V++){DFS(Gv);flag[v]=1;}if(count<G．vexnum)print f(“图中有环存在＼n”)；elseprint f(“该图是有向无环图＼n”);}voidDFS(ALGraphGint V){／*从第v个顶点出发深度优先遍历图G*／visit(v);visited[v]=1；EnQueue(Qv)；count++；for(P=G．vertice[v]．firstarc；p;P=P一>nextarc)if(visited[p->adjvex]&&flag[p一>adjvex]==0) ／*DFS结束前出现回边*／success=0；elseif(!visited[P一>adjvex]){DFS(GP一>adjvex);flaq[p一>adjvex]=1；}}
对有向图进行深度优先搜索，可以判定图中是否有回路。若从有向图的某个顶点v出发深度优先遍历，在DFS(v)结束前，出现顶点n到顶点v的回边，图中必有环。用数组flag[i]=1，表示其邻接点已全部被搜索完。由于深度优先搜索得到的序列是逆拓扑排序序列。因此用队列存放所访问的顶点。算法描述如下。