应用题
对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。
问答题
16.给出完成上述功能的图的邻接表定义。
【正确答案】邻接表定义：
typedef struct ArcNode{
int adjvex；
struct ArcNode * next；
}ArcNode;
typedef struct VNode{
vertype data；
ArcNode * firstarc；
}VNode，AdjList[MAX]；
【答案解析】
问答题
17.定义在算法中使用的全局辅助数组。
【正确答案】全局数组定义：
int visited[]=0；finished[]=0；flag=1； ／／flag测试拓扑排序是否成功
ArcNode * final=null； ／／final是指向顶点链表的指针，初始化为0
【答案解析】
问答题
18.写出在遍历图的同时进行拓扑排序的算法。
【正确答案】算法
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);
}
【答案解析】