1、習題八 圖編程。有向圖如下，請按深度優先和廣度優先兩種方式設計 c 語言的遍歷函數，程序輸出遍歷圖所得的頂點序列。功能要求如下：（1）輸入并生成一個圖；（2）深度優先遍歷；（3）廣度優先遍歷；char letter;/頂點數據域EDGE *out;/指向邊表的指針NODE;void graphinput(NODE *,);/輸入并生成一個圖pop(*,&,);/出棧函數push(*,); /入棧、入隊函數void DFS(NODE *,);/深度優先遍歷void BFS(NODE *,);/廣度優先遍歷main (void)NODE nistMaxLen;i,n=0;coutn;graphin

2、put(nist,n);coutendl深度優先遍歷結果:endl;Dist,n);for (i=0;in;i+)/清除標記，為廣度優先遍歷做準備nisti.mark=false;coutendl廣度優先遍歷結果:endl;Bist,n);return (0);void graphinput (NODE *nist,n)i,j,m;EDGE *q,*p;for(i=0;in;i+)/以下輸入頂點數據cout輸入頂點i+1nisti.letter;nisti.mark=false;/設置標志初始為falsenisti.out=NULL;/邊表初始置空;for(i=0;in;i+)/以下設置頂點的

3、邊表cout輸入第i+1m;if(m)nisti.out=(EDGE *)malloc(sizeof(EDGE);coutt 輸入第i+1個頂點的第1nisti.out-no;/與第 i 個頂點相鄰的圖頂點nisti.out-link=NULL;nisti.out-mark=false;p=nisti.out;for(j=1;jm;j+)q=(EDGE *)malloc(sizeof(EDGE);coutt 輸入第i+1個頂點的第j+1q-no;q-link=NULL;q-mark=false;p-link=q;p=q;pop (*stack,&i,top)if (top-1)i=stackt

4、op;top-;return(top);push (*stack,i,top)if (topMaxLen)top+;stacktop=i-1;return(top);void DFS (NODE *nist,n)i,k,top=-1,p;bool notfinished;stackMaxLen;EDGE *nextMaxLen;/nexti是每個頂點邊表要檢查的下一條邊for (i=0;in;i+)nexti=nisti.out;/nexti初始化指向各頂點邊表第一條邊for (k=0;kn;k+)/搜索頂點集合中未被的頂點 k，并從此出發遍歷該頂點生成if (nistk.mark=false

5、) /此頂點未i=k;coutnisti.letter ; /此頂點nisti.mark=true;/該頂點已標記notfinished=true;while (notfinished)/從此出發遍歷該頂點的生成while (nexti=NULL) /如果邊表空則可以回溯頂點if (top=-1)/若棧空則該頂點生成遍歷結束跳出循環notfinished=false;coutno;/指向邊的另一端鄰接頂點 pp-=1;/因為頂點從 1 開始而數組下標從 0開始if (nistp.mark=false)/順此頂點的深度方向遍歷top=push(stack,i,top);/當前頂點的前趨進棧nex

6、ti-mark=true;/前趨邊過標記coutnistp.letterlink;/指向頂點 i 邊表的下一節點（邊）i=p;/更換到鄰接頂點 p 的邊表else nexti=nexti-link; /此頂點已經標記過，更換邊;void BFS (NODE *nist,n)i,head,rear,queenMaxLen;for (i=1;i=n;i+)if (nisti-1.mark=false)head=rear=-1;rear=push(queen,i,rear);while (headrear)head+;/ 查看隊列中下一個頂點coutnistqueenhead.letterno)-1.mark=false)/未被就入隊rear=push(queen,temp-no,rear);nist(temp-n