问答题

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

函数T0pSon中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如表15—2所示：
【C代码】 int *TopSort(LinkedDigraph G) { ArcNode*P； ／*临时指针，指示表节点*／ Queue Q；／*临时队列，保存入度为0的顶点编号*／ int k=0； ／*临时变量，用作数组元素的下标*／ int j=0，W=0； ／*临时变量，用作顶点编号*／ int*toporder，*inDegree； toporder=(int*)malloc((G．n+1)*Si zeof(int))； ／*存储拓扑序列中的顶点编号*／ inDegree=(int*)malloc((G．n+1)*sizeof(int))； ／*存储图G中各顶点的入度*／ if(!inDegree I I!toporder)return NULL； (1)； ／*构造一个空队列*／ for(j=1；J＜=G．n；J++)( ／*初始化*／ toporder[J]=0； inDegree[j]=0； } for(J=1；J＜=G．n；J++) ／*求图G中各项点的入度*／ for(P=G．Vhead[j]．firstarc；P；P=p一＞nextarc) inDegree[p一＞adjvex]+=1； for(j=1；J＜=G．n；j++) ／*将图G中入度为0的顶点保存在队列中*／ if(0==inDegree[j])EnQueue(&Q，j)； whi le(!IsEmpty(Q))( (2) ； ／*队头顶点出队列并用W保存该顶点的编号*／ toporder[k++]=W； ／*将顶点W的所有邻接顶点的入度减1(模拟删除顶点w及从该项点出发的弧的操作)*／ for(p=G．Vhead[w]．firstarc；P；P=P一＞nextarc)( (3)一=1；if(0==(4))EnQueue(＆Q，P一＞adjvex)； }／*for*／ }／*while*／ free(inDegree)； if( (5) ) return NULL； return topOrder； }／*TopSort*／ 设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSo~的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如，图15—3所示有向图的邻接矩阵如图15—5所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是(7)。