问答题 阅读下列说明和C代码,回答问题1至问题3,将解答写在对应栏内。
[说明]
对有向图进行拓扑排序的方法如下。
(1)初始时拓扑序列为空。
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧。
(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列,则完成拓扑排序;否则,由于有向图中存在回路无法完成拓扑排序)。
函数int* TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的项点从1开始依次编号,顶点序列为v1,v2,…,vn,图G采用邻接表表示,其数据类型定义如下:
#define MAXVNUM 50 /*最大顶点数*/
typedef struct ArcNode /*表结点类型*/
int adjvex; /*邻接顶点编号*/
Struct ArcNode *nextarc; /*指示下一个邻接顶点*/
ArcNode;
typedef struct AdjList /*头结点类型*/
char vdata; /*顶点的数据信息*/
ArcNode *firstarc; /*指向邻接表的第一个表结点*/
AdjList;
typedef struct LinkedDigraph /*图的类型*/
int n; /*图中顶点个数*/
AdjList Vhead[MAXVNUM]; /*所有顶点的头结点数组*/
LinkedDigraph;
例如,某有向图G如图21-13所示,其邻接表如图21-14所示。

问答题 根据以上说明和C代码,填充C代码中的空(1)~(5)。
【正确答案】(1)InitQueue(&Q)
(2)DeQueue(&Q,&w)
(3)inDegree[p->adjvex],或其等价形式
(4)inDegree[p->adjvex],或其等价形式
(5)k<Gn
【答案解析】
问答题 对于图21-13所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈,写出函数TopSort执行后得到的拓扑序列。
【正确答案】队列方式:v1 v2 v5 v4 v3 v7 v6(或1 2 5 4 3 7 6)
栈方式:v1 v2 v5 v4 v7 v3 v6(或1 2 5 4 7 3 6)
【答案解析】
问答题 设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度为 (6)
若有向图采用邻接矩阵表示(例如,图21-13所示的有向图的邻接矩阵如图21-15所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时间复杂度为 (7)
[*]
【正确答案】(6)O(n+e)
(7)O(n2)
【答案解析】