試題四
閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在對應(yīng)欄內(nèi)。
[說明]
對有向圖進(jìn)行拓?fù)渑判虻姆椒ㄊ牵?br />①初始時拓?fù)湫蛄袨榭眨?br />②任意選擇一個入度為0的頂點，將其放入拓?fù)湫蛄兄?，同時從圖中刪除該頂點以及從該頂點出發(fā)的弧；
③重復(fù)②，直到不存在入度為0的頂點為止(若所有頂點都進(jìn)入拓?fù)湫蛄袆t完成拓?fù)渑判?，否則由于有向圖中存在回路無法完成拓?fù)渑判?。
函數(shù)int* TopSort(LinkedDigraphG.的功能是對有向圖G中的頂點進(jìn)行拓?fù)渑判?，返回拓?fù)湫蛄兄械捻旤c編號序列，若不能完成拓?fù)渑判?，則返回空指針。其中，圖G中的頂點從1開始依次編號，頂點序列為v1，v2，…，vn，圖G采用鄰接表表示，其數(shù)據(jù)類型定義如下：
#define MAXVNUM 50    /*最大頂點數(shù)*/
typedef struct ArcNode{    /*表結(jié)點類型*/
int adjvex;    /*鄰接頂點編號*/
struct ArcNode *nextarc;    /*指示下一個鄰接頂點*/
}ArcNode;
typedef struct AdjList {    /*頭結(jié)點類型*/
char vdata;    /*頂點的數(shù)據(jù)信息*/
ArcNode *fimstarc;    /*指向鄰接表的第一個表結(jié)點*/
}AdjList;
typedef struct LinkedDigraph {    /*圖的類型*/
int n;    /*圖中頂點個數(shù)*/
AdjList Vhead[MAXVNUM];    /*所有頂點的頭結(jié)點數(shù)組*/
}LinkedDigraph;
例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。

[C代碼]
int *TopSort(LinkedDigraphG.  {
ArcNode *p;    /*臨時指針，指示表結(jié)點*/
Queue Q;        /*臨時隊列，保存入度為0的頂點編號*/
int k=0;    /*臨時變量，用作數(shù)組元素的下標(biāo)*/
intj=0，w=0;    /*臨時變量，用作頂點編號*/
int *topOrder，*inDegree;
topOrder=(int *)malloc((G.n+1) *sizeof(int));
/*存儲拓?fù)湫蛄兄械捻旤c編號*/
inDegree=(int *)malloc((G.n+1) *sizeof(int));
/*存儲圖G中各頂點的入度*/
if(!inDegree || !topOrder) return NULL;
(1)  ;    /*構(gòu)造一個空隊列*/
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);
while(!IsEmpty(Q)){
(2)  ;    /*隊頭頂點出隊列并用w保存該頂點的編號*/
topOrder[k++]=w;
/*將頂點w的所有鄰接頂點的入度減1(模擬刪除頂點w及從該頂點出發(fā)的弧的操作)*/
for(p=G.Vhead[w].firstarc;P; p=p-＞nextarc){
(3)  -=1;
if(0==  (4)  )  EnQueue(＆Q，P-＞adjvex);
1/{for$/
}/*while*/
free(inDegree);
if(  (5)  )
return NULL;
return topOrder;
}/*TopSort*/
【問題1】根據(jù)以上說明和C代碼，填充C代碼中的空（1）～（5）。
【問題2】對于圖4-1所示的有向圖G，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄?。若將函?shù)TopSort中的隊列改為棧，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小?br />設(shè)某有向無環(huán)圖的頂點個數(shù)為n、弧數(shù)為e，那么用鄰接表存儲該圖時，實現(xiàn)上述拓?fù)渑判蛩惴ǖ暮瘮?shù)TopSort的時間復(fù)雜度是  （6） 。
若有向圖采用鄰接矩陣表示(例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示)，且將函數(shù)TopSort中有關(guān)鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點、e條弧的有向無環(huán)圖，實現(xiàn)上述拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是  （7）  。