【正确答案】正确答案：对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。设visited访问数组乘finished数组为全局变量，若finished[i]=1，表示顶点i的邻接点已搜索完毕。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入final所指的链表中，链表中的结点就是一个正常的拓扑序列。拓扑排序算法的核心语句段如下： int visited[]=0；finished[]=0；flag=1； ／／flag测试拓扑排序是否成功 ArcNode*final=null； ／／final是指向顶点链表的指针，初始化为0 void dfs(AdjList g，vertype v) ／／从v开始深度优先遍历图g，顶点信息就是编号 (cout<adjvex； if(visited[j]==1&&finished[j]==0)flag=0； ／／dfs结束前出现回边 else if(visited[j]==0){dfs(g，j)；finished[j]=1；} p=p一>next； }／／while t=new(ArcNode)；t->adjvex=v；t->next=final；final=t； ／／将该顶点插入链表 }／／dfs结束 int dfs-Topsort(Adjlist g) ／／拓扑排序，拓扑排序成功返回1，否则返回0 {i=1； while(flag&&i<=n) if(visited[i]==0){dfs(g，i)；finished[i]=1；)／／if return(flag)； }／／dfs—Topsort