【正确答案】(1)邻接表定义： typedef struct ArcNode{ int adjvex; struet ArcNode *next; }ArcNode; typedef struct VNode{ vertype data; ArcNode *firstarc; }VNode, AdjList[MAX]; (2)全局数组定义： int visited[]=0; finished[]=0; flag=1; //flag测试拓扑排序是否成功 ArcNode *final=null; //final是指向顶点链表的指针，初始化为0 (3)算法 void dfs(AdjList g, vertype v){ //以顶点v开始深度优先遍历有向图g，顶点信息就是顶点编号 ArcNode *t; //指向边结点的临时变量 printf("%d",v); visited[v]=1; p=g[v].firstarc; while(p != null){ j=p-＞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= (ArcNode*)malloc(sizeof(ArcNode)); //申请边结点 t-＞adjvex=v; t-＞next=final; final=t; //将该顶点插入链表 }//dfs结束_ int dfs_Topsort(ndjlist g){ //对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回1，否则返回0 i=1; while(flag&&i＜=n) if(visited. [i]==0){ dfs(g,i); finished[i]=1; }//if return(flag); }

【答案解析】此题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。