1、第7章圖(基礎知識)習題練習答案7.1 在圖7.23所示的各無向圖中：(1)找出所有的簡單環。(2)哪些圖是連通圖?對非連通圖給出其連通分量。(3)哪些圖是自由樹(或森林)?答:(1)所有的簡單環：(同一個環可以任一頂點作為起點)(a)1231(b)無(c)1231、2342、12341(d)無(2)連通圖：(a)、(c)、(d)是連通圖，(b)不是連通圖，因為從1到2沒有路徑。具體連通分量為：(3)自由樹(森林)：自由樹是指沒有確定根的樹，無回路的連通圖稱為自由樹：(a)不是自由樹，因為有回路。(b)是自由森林，其兩個連通分量為兩棵自由樹。(c)不是自由樹。(d)是自由樹。 7.2 在圖7.

2、24(下圖)所示的有向圖中： (1) 該圖是強連通的嗎? 若不是，則給出其強連通分量。(2) 請給出所有的簡單路徑及有向環。(3) 請給出每個頂點的度，入度和出度。(4) 請給出其鄰接表、鄰接矩陣及逆鄰接表。答：(1)該圖是強連通的，所謂強連通是指有向圖中任意頂點都存在到其他各頂點的路徑。(2)簡單路徑是指在一條路徑上只有起點和終點可以相同的路徑：有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向環,有向環如下：v1v2v3v1、v1v4v3v1(這兩個有向環可以任一頂點作為起點和終點)(3)每

3、個頂點的度、入度和出度：D(v1)=3 ID(v1)=1 OD(v1)=2D(v2)=2 ID(v2)=1 OD(v2)=1D(v3)=3 ID(v3)=2 OD(v3)=1D(v4)=2 ID(v4)=1 OD(v4)=1(4)鄰接表：(注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標值-1)   vertex firstedge  next    0v1 1 3               1v2 2 

4、60;           2v3 0             3v4 2          逆鄰接表：         0v1 2         1v2 0        &#

5、160;  2v3 1 3           3v4 0        鄰接矩陣：    0 1 0 1    0 0 1 0    1 0 0 0    0 0 1 0 7.3 假設圖的頂點是A,B.，請根據下述的鄰接矩陣畫出相應的無向圖或有向圖。          

6、0;  | 0 1 1 0 0 |  | 0 1 1 1 |   | 0 0 0 1 0 |   | 1 0 1 1 |   | 0 0 0 1 0 |   | 1 1 0 1 |   | 1 0 0 0 1 |   | 1 1 1 0 |   | 0 1 0 1 0 |               

7、60;     (a)               (b) 答:    7.4 假設一棵完全二叉樹包括A,B,C.等七個結點，寫出其鄰接表和鄰接矩陣。解：  鄰接表如下：    0A 1  2             1B 0 3 4  &

8、#160;          2C 0 5 6             3D 1         4E 1         5F 2         6G 2        鄰接矩陣如下：    &#

9、160;   0 1 1 0 0 0 0        1 0 0 1 1 0 0        1 0 0 0 0 1 1         0 1 0 0 0 0 0        0 1 0 0 0 0 0      

10、0;  0 0 1 0 0 0 0        0 0 1 0 0 0 07.5 對n個頂點的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時，如何判別下列有關問題?  (1) 圖中有多少條邊?  (2)任意兩個頂點i和j是否有邊相連?  (3) 任意一個頂點的度是多少?答：    對于n個頂點的無向圖和有向圖，用鄰接矩陣表示時：  (1)設m為矩陣中非零元素的個數 無向圖的邊數=m/2有向圖的邊數=m(2)無論是有向圖還是無向圖，在矩陣中

11、第i行,第j列的元素若為非零值，則該兩頂點有邊相連。(3)對于無向圖，任一頂點i的度為第i行中非零元素的個數。對于有向圖，任一頂點i的入度為第i列中非零元素的個數，出度為第i行中非零元素的個數，度為入度出度之和。當用鄰接表表示時：(1)對于無向圖，圖中的邊數=邊表中結點總數的一半。對于有向圖，圖中的邊數=邊表中結點總數。(2)對于無向圖，任意兩頂點間是否有邊相連，可看其中一個頂點的鄰接表，若表中的adjvex域有另一頂點位置的結點，則表示有邊相連。對于有向圖，則表示有出邊相連。(3)對于無向圖，任意一個頂點的度則由該頂點的邊表中結點的個數來決定。對于有向圖，任意一個頂點的出度由該頂點的邊表中結

12、點的個數來決定，入度則需遍歷各頂點的邊表。(用逆鄰接表可容易地得到其入度。)7.6 n個頂點的連通圖至少有幾條邊?強連通圖呢?答：n個頂點的連通圖至少有n-1條邊，強連通圖至少有2(n-1)條邊。7.7 DFS和BFS遍歷各采用什么樣的數據結構來暫存頂點?當要求連通圖的生成樹的高度最小，應采用何種遍歷?答：DFS遍歷采用棧來暫存頂點。BFS采用隊列來暫存頂點。當要求連通圖的生成樹的高度最小時，應采用BFS遍歷。7.8 畫出以頂點v1為初始源點遍歷圖7.25（下圖）所示的有向圖所得到的DFS 和BFS生成森林。答：7.9 按順序輸入頂點對：(1，2)，(1，6)，(2，6)，(1，4)，(6，4

13、)，(1，3)，(3，4),(6，5)，(4，5)，(1,5),(3,5),根據第7.2.2節中算法CreatALGraph畫出相應的鄰接表。并寫出在該鄰接表上，從頂點4開始搜索所得的DFS和BFS序列，及DFS和BFS生成樹。 答：相應的鄰接表如下：           11 5 3 4 6 2               22 6 1             &#

14、160; 33 5 4 1                 44 5 36 1                 55 3 1 4 6                 66 5 4 2 1        

15、60;       根據上面的鄰接表畫出的圖見下圖:          從頂點4開始搜索所得的DFS序列是：453162    從頂點4開始搜索所得的BFS序列是：453612    相應的生成樹見上圖。7.10 什么樣的圖其最小生成樹是唯一的?用PRIM 和Kruskal求最小生成樹的時間各為多少?它們分別適合于哪類圖?答：當候選輕邊集中的輕邊數始終等于1條時，其最小生成樹是唯一的。用Prim和Kruskal求最小

16、生成樹的時間復雜度分別為O(n2)和O(elge),前者適合于稠密圖，后者適合于稀疏圖.7.11 對圖7.26（下圖）所示的連通圖，請分別用Prim和Kruskal算法構造其最小生成樹。 答：7.12 對圖7.27(下圖)所示的有向圖，試利用Dijkstra算法求出從源點1到其它各頂點的最短路徑，并寫出執行算法過程中擴充紅點集的每次循環狀態(見表7.2). 答：循環狀態表如下：循環      紅點集  K D1 D2 D3 D4 D5 D6 P1 P2 P3 P4 P5 P6 初始化  

17、0;    1  -   0   20   15            -1    1    1   -1   -1   -1      1         1,3

18、60; 3   0   19   15         25   -1    3    1   -1   -1    3      2       1,3,2  2   0 

19、60; 19   15      29   25   -1    3    1   -1    2    3      3     1,3,2,6  6   0   19   15 

20、0; 29   29   25   -1    3    1    6    2    3      4   1,3,2,6,4  4   0   19   15   29   29   2

21、5   -1    3    1    6    2    3      5 1,3,2,6,4,5  5   0   19   15   29   29   25   -1    3 &#

22、160;  1    6    2    3      6          同上  -                 同上     &#

23、160;                同上 從源點1到各點的路徑如下所示：    1到2：1321到3：131到4：13641到5：13251到6：136整個執行算法過程中的擴充紅點集的每次循環狀態見上表。7.13 試寫出圖7.28(下圖)所示有向圖的所有拓撲序列，并指出就用7.6節給出的NonPreFirstTopSort算法求得的是哪個序列，設鄰接表的邊表結點中的鄰接點序號是遞增有序的。 &

24、#160;   答：    上圖中所有拓撲序列如下：  v0v1v5v2v3v6v4 *  v0v1v5v2v6v3v4  v0v1v5v6v2v3v4  v1v0v5v6v2v3v4  v1v0v5v2v3v6v4  v1v0v5v2v6v3v4  v1v5v0v2v3v6v4  v1v5v0v2v6v3v4  v1v5v0v6v2v3v4  v5v1v0v2v3v6v4  v5v1v0v2v6v3v4  v5v1v0v6v

25、2v3v4  v5v0v1v2v3v6v4  v5v0v1v2v6v3v4  v5v0v1v6v2v3v4  v0v5v6v1v2v3v4  v1v5v6v0v2v3v4  v5v6v1v0v2v3v4  v5v6v0v1v2v3v4  v5v0v6v1v2v3v4  v5v1v6v0v2v3v4    用NonPreFirstTopSort算法求得的是v0v1v5v2v3v6v4也就是上面帶*號的那個。7.14 什么樣的DAG的拓撲序列是唯一的? 答： 

26、   確定了排序的源點，DAG圖中無前趨頂點只有一個且從該點到終點只有一條路徑時，它的拓撲序列才是唯一的。7.15 請以V0為源點，給出用DFS搜索圖7.28(下圖)得到的逆拓撲序列。      答：    逆拓撲序列是：V4 V2 V1 V0 V1 V6 V57.16 試在無向圖的鄰接矩陣和鄰接鏈表上實現如下算法：(1)往圖中插入一個頂點(2)往圖中插入一條邊(3)刪去圖中某頂點(4)刪去圖中某條邊解：(一)用鄰接矩陣表示#define MaxVertexNum l00 /最大頂點數，應由用戶

27、定義typedef char VertexType； /頂點類型應由用戶定義typedef int EdgeType； /邊上的權值類型應由用戶定義typedef structVextexType vexsMaxVertexNum /頂點表EdeType edgesMaxVertexNumMaxVertexNum;/鄰接矩陣，可看作邊表int n，e； /圖中當前的頂點數和邊數MGragh；(1)往圖中插入一個頂點 void AddVertexMGraph(MGraph *G,VertexType x)/往無向圖的鄰接矩陣中插入頂點if (G->n>=MaxVertexN

28、um)Error("頂點數太多")；G->vexsG->n=x;/將新頂點輸入頂點表G->n+；/頂點數加1(2)往圖中插入一條邊void AddedgeMGraph(MGraph *G,VertexType x,VertexType y)/往無向圖的鄰接矩陣中插入邊(x,y)int i,j,k;i=-1;j=-1;for(k=0;k<G->n;k+)/查找X，Y的編號 if (g->vexsk=x) i=k;if (g->vexsk=y) j=k;if (i=-1|j=-1) Error("結點不存在");el

29、se /插入邊(x,y)g->vexij=1;g->vexji=1;G->e+;/邊數加1(3)刪去圖中某頂點void DeleteVertexMGraph(MGraph *G,VertexType x)/無向圖的鄰接矩陣中刪除頂點xint i,k,j;i=-1;for(k=0;k<G->n;k+)/查找X的編號if (g->vexsk=x) i=k;if (i=-1) Error("結點不存在");else /刪除頂點以及邊k=0;/求出與x結點相關聯的邊數kfor (j=0;j<G->n;j+)if (g->vexs

30、ij=0) k+;G->e=G->e-k;/設置新的邊數for (k=i+1;k<G->n;k+)/在鄰接矩陣中刪除第i行for(j=0;j<G->n;j+)g->vexsk-1j=g->vexskj;for (k=i+1;k<G->n;k+)/在鄰接矩陣中刪除第i列for(j=0;j<G->n;j+)g->vexsjk-1=g->vexsjk;G->n-;/總結點數-1 (4)刪去圖中某條邊void DeleteedgeMGraph(MGraph *G,VertexType x,VertexT

31、ype y)/無向圖的鄰接矩陣中刪除邊(x,y)int i,j,k;i=-1;j=-1;for(k=0;k<G->n;k+)/查找X，Y的編號 if (g->vexsk=x) i=k;if (g->vexsk=y) j=k;if (i=-1|j=-1) Error("結點不存在");else if (g->vexsij!=1)/刪除邊(x,y)g->vexij=0;g->vexji=0;G->e-;/邊數加1(二)用鄰接表表示 typedef struct node/邊表結點int adjvex； /鄰接點域stru

32、ct node *next； /鏈域/若要表示邊上的權，則應增加一個數據域EdgeNode;typedef struct vnode /頂點表結點 VertexType vertex； /頂點域EdgeNode *firstedge；/邊表頭指針 VertexNode；typedef VertexNode AdjListMaxVertexNum；/AdjList是鄰接表類型typedef struct AdjList adjlist；/鄰接表 int n，e； 圖中當前頂點數和邊數 ALGraph； /對于簡單的應用，無須定義此類型，可直接使用AdjList類型。 (1)往

33、圖中插入一個頂點void AddVertexALGraPh(ALGrahp *G,VertexType x)/往無向圖的鄰接表表示中插入一個頂點if (G->n>=MaxVertexNum)Error("頂點數太多")；G->adjlistG->n.vertex=x;/將新頂點輸入頂點表G->adjlistG->n.firstedge=NULL;/邊表置為空表G->n+；/頂點數加1(2)往圖中插入一條邊void AddedgeALGraPh(ALGrahp *G,VertexType x,VertexType y)/往無向圖的鄰接

34、表中插入邊(x,y)int i,j,k;EdgeNode *s；i=-1;j=-1;for(k=0;k<G->n;k+)/查找X，Y的編號 if (G->adjlistk.vertex=x) i=k;if (G->adjlistk.vertex=y) j=k;if (i=-1|j=-1) Error("結點不存在");else s=G->adjlisti.firstedge;while (s)&&(s->adjvex!=j)/查看鄰接表中有無(x,y)s=s->next;if (!s)/當鄰接表中無邊(x,y),插入

35、邊(x,y) s=(EdgeNode *)malloc(sizeof(EdgeNode)； /生成邊表結點s->adjvex=j; /鄰接點序號為js->next=G->adjlisti.firstedge；G->adjlisti.firstedge=s；/將新結點*s插入頂點x的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode)；s->adjvex=i; /鄰接點序號為is->next=G->adjlistj.firstedge；G->adjlistj.firstedge=s； /將新結點*s插入頂點x

36、的邊表頭部G->e+;/邊數加1 (3)刪去圖中某頂點void DeleteVertexALGraPh(ALGrahp *G,VertexType x)/無向圖的鄰接表中刪除頂點xint i,k,j;EdgeNode *s,*p,*q；i=-1;for(k=0;k<G->n;k+)/查找X的編號if (G->adjlistk.vertex=x) i=k;if (i=-1) Error("結點不存在");else /刪除與x相關聯的邊s=G->adjlisti.firstedge;while (s)p=G->adjlists-&g

37、t;adjvex.firstedge;/刪除與i相關聯的其他結點邊表中表結點if (p)&&(p->adjvex=i)/是第一個邊表結點，修改頭指針G->adjlists->adjvex.firstedge=p->next;free(p);else/不是第一個 邊表結點，查找并刪除while (p)&&(p->next)&&(p->next->adjvex=i)p=p->next;q=p->next;p->next=q->next;free(q);q=s;s=s->next;

38、free(q);/在i結點的邊表中刪除表結點G->e-; /調整頂點表for (j=i;j<G->n-1;j+)G->adjlistj.firstedge=G->adjlistj+1.firstedge;G->adjlistj.vertex=G->adjlistj+1.vertex;G->n-; (4)刪去圖中某條邊void DeleteedgeALGraPh(ALGraph *G,VertexType x,VertexType y)/往無向圖的鄰接表中刪除邊(x,y)int i,j,k;EdgeNode *s,*p；i=-1

39、;j=-1;for(k=0;k<G->n;k+)/查找X，Y的編號 if (G->adjlistk.vertex=x) i=k;if (G->adjlistk.vertex=y) j=k;if (i=-1|j=-1) Error("結點不存在");else s=G->adjlisti.firstedge;/在i的邊表中刪除值為j的邊表結點if (s)&&(s->adjvex=j) G->adjlisti.firstedge=s->next;free(s); elsewhile (s)&

40、;&(s->next)&&(s->next->adjvex!=j)s=s->next;if (!s->next) Error("無此邊");else p=s->next;s=p->next;free(p);s=G->adjlistj.firstedge;/在j的邊表中刪除值為i的邊表結點if (s)&&(s->adjvex=i) G->adjlistj.firstedge=s->next;free(s); elsewhile (s)&

41、;&(s->next)&&(s->next->adjvex!=j)s=s->next;p=s->next;s=p->next;free(p);G->e-; 7.17 下面的偽代碼是一個廣度優先搜索算法，試以圖7.29（下圖）中的v0為源點執行該算法，請回答下述問題：(1)對圖中頂點vn+1，它需入隊多少次？它被重復訪問多少次?(2)若要避免重復訪問同一個頂點的錯誤，應如何修改此算法?void BFS(ALGraph *G,int k)/以下省略局部變量的說明，visited各分量初值為假InitQueue(&Q

42、);/置空隊列EnQueue(&Q,k);/k入隊while(!QueueEmpty(&Q)i=DeQueue(&Q);/vi出隊visitedi=TRUE;/置訪問標記printf("%c",G->adjlisti.vertex;/訪問vifor(p=G->adjlisti.firstedge;p;p=p->next)/依次搜索vi的鄰接點vj(不妨設p->adjvex=j)if(!visitedp->adjvex)/若vj沒有訪問過EnQueue(&Q,p->adjvex);/vj入隊/endofwhi

43、le/BFS答：(1)對圖中頂點vn+1，它需入隊n次,它被重復訪問n次。(2)若要避免重復訪問同一個頂點的錯誤，應作如下修改：void BFS(ALGraph *G,int k)/以下省略局部變量的說明，visited各分量初值為假InitQueue(&Q);/置空隊列EnQueue(&Q,k);/k入隊visitedi=TRUE;/置訪問標記printf("%c",G->adjlisti.vertex;/訪問viwhile(!QueueEmpty(&Q)i=DeQueue(&Q);/vi出隊for(p=G->adjlisti.

44、firstedge;p;p=p->next)/依次搜索并訪問vi的未訪問鄰接點vj(不妨設p->adjvex=j)if(!visitedp->adjvex)/若vj沒有訪問過printf("%c",G->adjlisti.vertex;/訪問vjEnQueue(&Q,p->adjvex);/vj入隊/endofwhile/BFS7.18 試以鄰接表和鄰接矩陣為存儲結構，分別寫出基于DFS和BFS遍歷的算法來判別頂點vi和vj(i<>j)之間是否有路徑。答：(1)基于采用鄰接矩陣的DFSint pathDFSM(MGraph

45、*G，int i,int j) /以鄰接矩陣為存儲結構，判斷vi和vj之間是否有路徑，若有返回1，否則返回0int k;visitedi=TRUE；for(k=0；k<G->n；k+) /依次搜索vi的鄰接點if(G->edgesik=1&&!visitedk)if (k=j) return 1;/有路徑相通else return(pathDFSM(G,k,j);return 0;/無路徑相通/DFSM(2)基于采用鄰接表的DFS int PATHDFS(ALGraph *G，int i,int j) /以鄰接表為存儲結構，判斷vi和vj之

46、間是否有路徑，若有返回1，否則返回0EdgeNode *p；visitedi=TRUE； /標記vi已訪問p=G->adjlisti.firstedge； /取vi邊表的頭指針while(p)/依次搜索vi的鄰接點vk，這里k=p->adjvexif （!visitedp->adjvex)/若vk尚未被訪問if (p->adjvex=j)return 1;else ruturn PATHDFS(g，p->adjvex,j);/則以Vk為出發點向縱深搜索p=p->next； /找vi的下一鄰接點return 0;/PATHDFS(3)基于鄰接矩陣的BFS算法i

47、nt pathBFSM(MGraph *G，int i,int j)/以鄰接矩陣為存儲結構，判斷vi和vj之間是否有路徑，若有返回1，否則返回0int k；CirQueue Q； initQueue(&Q)；visitedi=TRUE；EnQueue(&Q，i)；while(!QueueEmpty(&Q)i=DeQueue(&Q)； /vi出隊for(k=0;k<G->n;k+)/依次搜索vi的鄰接點vkif(G->edgesik=1&&!visitedk)/vk未訪問if (k=j) return 1;visited

48、k=TRUE；EnQueue(&Q，k)；/訪問過的vk人隊/endwhilereturn 0;/pathBFSM(4)基于鄰接表為存儲結構的BFS算法int BFS(ALGraph *G，int i,int j)/以鄰接表為存儲結構，判斷vi和vj之間是否有路徑，若有返回1，否則返回0int i；CirQueue Q； /須將隊列定義中DataType改為intEdgeNode *p；InitQueue(&Q)；/隊列初始化visitedi=TRUE； EnQueue(&Q，i)；/vi已訪問，將其人隊。（實際上是將其序號人隊）while(!QueueEmp

49、ty(&Q)/隊非空則執行i=DeQueue(&Q)； /相當于vi出隊p=G->adjlisti.firstedge； /取vi的邊表頭指針    while(p)/依次搜索vi的鄰接點vk(令p->adjvex=k)if(!visitedp->adjvex) /若vk未訪問過if (p->adjvex=j)return 1;elsevisitedP->adjvex=TRUE； EnQueue(&Q，p->adjvex)；/訪問過的vk人隊    

50、60;                   p=p->next；/找vi的下一鄰接點                      /endwhile     

51、;       /endwhile          return 0;    /end of pathBFS7.19 試分別寫出求DFS和BFS生成樹(或生成森林)的算法，要求打印出所有的樹邊。答：  (1)求DFS生成樹typedef enumFALSE，TRUEBoolean；/FALSE為0，TRUE為1Boolean visitedMaxVertexNum； /訪問標志向量是全局量void DFS

52、TraverseTREE(ALGraph *G) /求深度優先生成樹(以鄰接表表示的圖G)，而以鄰接矩陣表示G時，/算法完全與此相同,只要將DFSTree(G，i)改為DFSMTree(G，i)即可int i；for(i=0;i<G->n;i+)visitedi=FALSE； /標志向量初始化for(i=0;i<G->n；i+)if(!visitedi) /vi未訪問過DFSTree(G，i)； /以vi為源點開始DFS搜索,求DFS生成樹的邊/DFSTraversevoid DFSTree(ALGraph *G，int i) /以vi為出發點對鄰接表表示的圖

53、G進行深度優先搜索,打印生成樹(生成森林)的邊EdgeNode *p；visitedi=TRUE； /標記vi已訪問p=G->adjlisti.firstedge； /取vi邊表的頭指針while(p)/依次搜索vi的鄰接點vj，這里j=p->adjvexif (!visitedp->adjvex)/若vj尚未被訪問printf("(%c,%c)n",G->adjlisti.vertex,G->adjlistp->adjvex.vertex) ；/ 打印邊DFSTree(g，p->adjvex);/則以Vj為出發點向縱深搜

54、索p=p->next； /找vi的下一鄰接點/DFSvoid DFSMTree(MGraph *G，int i) /以vi為出發點對鄰接矩陣表示的圖G進行深度優先搜索,打印生成樹(生成森林)的邊int j；visitedi=TRUE；for(j=0；j<G->n；j+) /依次搜索vi的鄰接點if(G->edgesij=1&&!visitedj)printf("(%c,%c)n",G->vexsi,G->vexsj);/ 打印邊DFSMTree(G，j);/(vi，vj)E，且vj未訪問過，故vj為新出發點/DFSMTre

55、e(2)求BFS生成樹typedef enumFALSE，TRUEBoolean；/FALSE為0，TRUE為1Boolean visitedMaxVertexNum； /訪問標志向量是全局量void BFSTraverseTREE(ALGraph *G) /求廣度優先生成樹(以鄰接表表示的圖G)，而以鄰接矩陣表示G時，/算法完全與此相同,只要將BFSTree(G，i)改為BFSMTree(G，i)即可      int i；      for(i=0;i<G->n;i+) 

56、;       visitedi=FALSE； /標志向量初始化      for(i=0;i<G->n；i+)if(!visitedi) /vi未訪問過BFSTree(G，i)； /以vi為源點開始BFS搜索,求BFS生成樹的邊/BFSTraversevoid BFSTree(ALGraph*G，int k)/ 以vk為源點對用鄰接表表示的圖G進行廣度優先搜索,并求出BFS生成樹邊int i；CirQueue Q； /須將隊列定義中DataType改為intEdgeNod

57、e *p；InitQueue(&Q)；/隊列初始化visitedk=TRUE； EnQueue(&Q，k)；/vk已訪問，將其人隊。（實際上是將其序號人隊）while(!QueueEmpty(&Q)/隊非空則執行i=DeQueue(&Q)； /相當于vi出隊p=G->adjlisti.firstedge； /取vi的邊表頭指針while(p)/依次搜索vi的鄰接點vj(令p->adjvex=j)if(!visitedp->adivex) /若vj未訪問過printf("(%c,%c)n"，G->adjlist

58、i.vertex,G->adjlistp->adjvex.vertex)；/打印邊visitedP->adjvex=TRUE； EnQueue(&Q，p->adjvex)；訪問過的vj人隊/endifp=p->next；/找vi的下一鄰接點/endwhile/endwhile/end of BFSTree void BFSMTree(MGraph *G，int k)/ 以vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索,并求出BFS生成樹邊int i，j；CirQueue Q；        InitQueue(&Q)；visitedk=TRUE；EnQueue(&Q，k)；while(!QueueEmpty(&Q)i=DeQueue(&