参考答案

正确答案：(1)邻接表定义：typedef struct ArcNode{int adjvex；struct ArcNode*next；}ArcNode；Typedef struct VNode{vertype data；ArcNode*firstarc；}VNodeAdjList[MAX]；(2)全局数组定义：int visited[]=0；finished[]=0；flag：=1；／／flag测试拓扑排序是否成功ArcNode*final=null；／／final是指向顶点链表的指针初始化为0(3)算法void dfs(AdjList gvertype 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(gj)；finished[j]=1；}／／ifP=P一>next；}／／whilet=(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(gi)；finished[i]=1；}／／ifreturn(flag)；}／／dfs-Topsort
此问题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。