【正确答案】邻接表定义
typedef struct ArcNode{
int adjvex；
struct ArcNode*next；
}ArcNode；
typedef struct VNode{
vertype data；
ArcNode * firstarc；
}VNode，AdjList[MAX]；

【正确答案】全局数组定义
int visited[]=0；finished[]=0；flag=1； ／／flag测试拓扑排序是否成功
ArcNode * final=null； ／／final是指向顶点链表的指针，初始化为0

【正确答案】算法
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(Adjlist 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所指的链表中，链表中的结点就是一个正常的拓扑序列。