对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。

问答题给出完成上述功能的图的邻接表定义。

【正确答案】正确答案：邻接表定义： 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结束 intdfx_Topsort(Adjlist g){ ／／对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回1，否则返回0 i=1； while(flag&&i<=n) if(visited．[i]==0){ dfs (g，i)；finished[i]=1；}／／if return(flag); }

【答案解析】