1、實驗報告學院（系）名稱： 計算機與通信工程學院姓名*學號*專業計算機科學與技術班級2015級*班實驗項目實驗四：圖的深度優先與廣度優先遍歷課程名稱數據結構與算法課程代碼0661013實驗時間2017年5月12日第5-6節實驗地點7-216考核 標準實驗過程25分程序運行20分回答問題15分實驗報告30分特色 功能5分考勤違 紀情況5分成績成績 欄其它批改意見：教師簽字：考核 內容評價在實驗 課堂中的表 現，包括實 驗態度、編 寫程序過程 等內容等。功能完善，功能不全有小錯無法運行O正確o基本正確O有提示o無法回答o完整o較完整o般o內容極少o無報告o有o無o有o無一、實驗目的理解圖的邏輯特點；

2、掌握理解圖的兩種主要存儲結構（鄰接矩陣和鄰接表），掌握圖的構造、深度優先遍歷、廣度優先遍歷算法二、實驗題目與要求1.每位冋學按下述要求實現相應算法：根據從鍵盤輸入的數據創建圖（圖的存儲結構可采用 鄰接矩陣或鄰接表），并對圖進行深度優先搜索和廣度優先搜索1）問題描述：在主程序中提供下列菜單：1圖的建立2深度優先遍歷圖3廣度優先遍歷圖0結束2）實驗要求：圖的存儲可采用鄰接表或鄰接矩陣；定義下列過程：CreateGraph（）:按從鍵盤的數據建立圖 DFSGrahp（）:深度優先遍歷圖BFSGrahp（）:廣度優先遍歷圖3）實驗提示:圖的存儲可采用鄰接表或鄰接矩陣；圖存儲數據類型定義（鄰接表存儲）#

3、 define MAX_VERTEX_NUM 8頂點最大個數typedef struct ArcNode int adjvex;struct ArcNode *nextarc;int weight; / 邊的權 ArcNode; / 表結點 # define VertexType int II 頂點元素類型 typedef struct VNode int degree,indegree; II頂點的度，入度 VertexType data;ArcNode *firstarc; Vnode I* 頭結點 *I; typedef structVnode verticesMAX_VERTEX_NU

4、M;int vexnum,arcnum;頂點的實際數，邊的實際數 ALGraph;4）注意問題： 注意理解各算法實現時所采用的存儲結構。 注意區別正、逆鄰接。2.拓撲排序：給出一個圖的結構，輸出其拓撲排序序列（頂點序列用空格隔開），要求在同等條件下，編號小的頂點在前。3 利用最小生成樹算法解決通信網的總造價最低問題1） 問題描述：若在n個城市之間建通信網絡，架設n-1條線路即可。如何以最低的經濟代價建設這個通信網，是一個網絡的最小生成樹問題。2） 實驗要求：利用Prim算法求網的最小生成樹。3）實現提示：通信線路一旦建立，必然是雙向的。因此，構造最小生成樹的網一定是無向網。為簡單起見，圖的頂點

5、數不超過10個，網中邊的權值設置成小于100。三、實驗過程與實驗結果應包括如下主要內容：數據結構定義圖是由定點集合及定點間的關系集合組成的一種數據結構，其形式化定義為Graph =（V,E）其中，V = x|x 某個數據對象是定點的有限非空集合； E = （x,y） |x,y V A Path（x,y）是頂點之間關系的有限集合，叫做便集。集合E中的Path （x,y）表示頂點x和頂點y之間有一條直接連線，即（x,y）表示一條邊，它是有方向的。算法設計思路簡介算法描述：可以用自然語言、偽代碼或流程圖等方式1、圖的深度優先搜索：在訪問圖中某一起始點V后，由V出發，訪問它的任一鄰接頂點w1;再從w1

6、;出發，訪問與w1鄰接但還沒有訪問過得頂點w2 ;然后再從w2出發，進行類似的訪問，,如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止；接著退回一步，回溯到 u的前一個鄰接頂點，看它是否還有其他沒有被訪問過的鄰接點。如果有，則訪問此鄰接點，之后再從 此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程， 直至圖中所有和 V連通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則說明該圖不是連通圖，另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被 訪問過為止。圖的廣度優先搜索：使用廣度優先搜索（BFS）在訪問了起始頂點V之后，由V出發，依次

7、訪問 V的各個未曾被訪問過的鄰接點 w1,w2,wt,然后再順序訪問 w1,w2,wt，的所有還為訪問過的鄰接點。再從這些頂點出發，訪問它們還未訪問過的鄰接點，如此做下去，直到圖中所有頂點都被訪問過為止。2、（1）將沒有前驅（入度為零）的頂點進棧。（2）從棧中退出棧頂元素輸出，并把該頂點引出的所有弧刪去，即把它的各個鄰接點的入度減1,同時將當前已輸出的頂點個數加1.（3）將新的入度為零的頂點再進棧。（4）重復（2）、（ 2）兩步，直到棧為空為止。此時或者已經輸出前部頂點，或者剩下的頂 點中沒有入度為零的頂點。3、設置一個n*n的矩陣A（ k ），其中除對角線元素為0夕卜，其他元素 A（k）ij

8、表示頂點i到頂點j的路徑長度，k表示運算步驟。開始時k = -1,A（-1）ij = arcsij,即A為圖的鄰接矩陣。以后逐步嘗試在原路徑中加入其他頂點作為中間點，如果增加中間點頂點后，得到的路徑比 原來的路徑短，則以此新路徑代替原來路徑，修改矩陣元素。具體做法為：第0步讓所有路徑上加入中間點 0,去Aij與Ai0 + Aoj中較小的值作 Aij的新值，完成后得到 A（0） 如此進行下去，當第n-1步完成后，得到 A（n-1）,A（n-1）即為所求的結果，A（n-1）ij表示從i到j路徑上的中間頂點的序號小于或等于n-1的最短路徑的長度，即A（n-1）ij表示從i到j的最短路徑的長度。算法的

9、實現和測試結果：包括算法運行時的輸入、輸出，實驗中出現的問題及解決辦法等1、6 61 21 32 43 44 54 61 2 4 5 6 31 2 3 4 5 6請按任意鍵繼續.C :WI N DOWSsystc m 3 2c md. cxe1 61 22 33 41 55 66 712 3 15 6 712 5 3 6 4 了請按任靈犍繼續.C3B C:QVINDOW£syyt(?nn32(:mdcc62 3 4 5 62 3 4 5 6請按仟竜鍵紳續.”3J C AWIN D 0V/Ssyste m 32c m d >exe7 67 45 44 22 11 31 65 7

10、4 2 1 3 6請按任豈鍵繼續一SB 匚:WI N DOWStyste m i 2c m d. exe5 41 22 33 44 51 2 3 4 5請按任薫憔綻綻.SS C:WINDOWSsystem3cnnd.exe3 66 56 45 14 23 6 4 2 5 l請按任意健繼續.31 C AWI IM D O WSsy s te in 3 2c md. exe6 5C 44 34 23 12 56 4 2 3 1 "青按任意腱醴續Sfl C :WI N DOWSsyste m 32c m d .cxe5 41 22 35 44 312 5 4 3請按任意鍵繼續.3、|SB

11、C :WI N DOWStyste m 3 2c m d.«4 41 2 11 3 23 4 3E 4 46請按仟袁錦樂續311 C:WI N DOWSsystem32c md.c4 41 2 11 2 21 3 61 4 714請按ft意健繼續.SB C :WI N D OWSsyste m 3 2c md. exc1 2 12 3 23 4 34 5 45 6 53 7 17 4 114詩按任意譴窒換.C AWIN D OWSsyste m 3 2c md. exe4 51 2 92 4 83 4 71 3 63 2 619請按仕意遵繼續1 0u請按任意鍵繼續.算法時間復雜度分析

12、1、深度優先遍歷：0 (n*n ).廣度優先遍歷：0 (n*n ).2、0 (n+e).3、O(n*n*n).四、收獲與體會不想說什么，這章的程序太難了，每次一想起來數據結構還沒做就煩，前兩個題基本上一天能做一道題, 第三題也就是騙騙 0J,實際上還有個小 BUG，等有空再寫個真正符合題意的程序吧。五、源代碼清單1、#in clude<iostream> usingn amespacestd;#defi ne INFINITY INT_MAX#defi ne MAX_VERTEX_NUM 20/typedef e num DG,DN,AG,ANGraphK ind; typedef

13、i nt Elemtype;typedefstruct QueueNodeElemtype data; struct QueueNode *n ext;QueueNode; typedefstruct QueueList QueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue() QueueList *Q;QueueNode *p;Q = (QueueList*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->fron

14、t = Q->rear = p;Q->fro nt->n ext = NULL; return Q;bool QueueEmpty(QueueList *Q)if(Q->fro nt = Q->rear) returntrue;elsereturnfalse;QueueList *En Queue(QueueList *Q, int eleme nt)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear-

15、>n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp; if(!QueueEmpty(Q)Jtemp = Q->fro nt->next;*e = temp->data;Q->fro nt->n ext = temp->next;if (Q->rear = temp)Q->rear = Q->fro nt; free(temp);return Q;void display(QueueList *Q

16、)QueueNode *temp; temp = Q->fro nt; if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext; cout << temp->data << en dl;typedefstruct Arc int adj; Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedefstruct in t vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;/ Gr

17、aphKi nd kind;Graph;void CreateAG(Graph &G, int n,int m)int i,j;G.vex num = n;G.arc num 二 m;for(i = 0;i < n ;i+)G.vertexi = i + 1;for(i = 0;i < n ;i+)for(j = 0;j < n;j+) G.arcsij.adj = 0;for(int k = 0;k < m;k+)cin >> i >> j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool vis

18、itedMAX_VERTEX_NUM;int count = 0;void DFS(Graph G,i nt v)visitedv-1 = true; coun t+; cout << v;if (count < G.vexnum)cout <<""for(i nt i = v;i < G.vex nu m;i+)if (G.arcsv-1i.adj != 0 && !visitedi) DFS(G,G.verte xi);void DFSTraverse(Graph G)int v = 0;for(v = 0;v <

19、; G.vex nu m;v+) visitedv = false;v = 1;/遍歷入口點DFS(G,v);void BFS(Graph G)int i,j;int k = 0;int v = 0;int u = 0;for(v = 0;v < G.vex nu m;v+) visitedv = false;QueueList *queue; queue = CreateQueue();v = 1;En Queue(queue,v); visitedv-1 = true; while(!QueueEmpty(queue) DeQueue(queue，&u);k+;cout &l

20、t;< u;if (k < G.vex num) cout <<""for(i nt i = u;i < G.vex nu m;i+) if(G.arcsu-1i.adj != 0 && !visitedi)En Queue(queue,G.vertexi); visitedi = true;int mai n()Graph G1;int m = 0;/ 邊數int n二0;/頂點數cin >> n >> m;CreateAG(G1, n,m); DFSTraverse(G1); cout <<

21、; en dl;BFS(G1); return 0;2、#in clude<iostream> usingn amespacestd;#defi ne INFINITY INT_MAX#defi ne MAX_VERTEX_NUM 20 typedefi nt Elemtype; typedefstruct QueueNode Elemtype data; struct QueueNode *n ext;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *Cre

22、ateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->front = Q->rear = p;Q->fro nt->n ext = NULL; return Q;bool QueueEmpty(QueueList *Q)if (Q->fro nt 二二 Q->rear)returntrue;elsereturnfalse;QueueList *En Queue(Que

23、ueList *Q, int eleme nt) QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear- >n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp;if(!QueueEmpty(Q)temp = Q->fro nt->next;*e = temp->data;Q-

24、>fro nt->n ext = temp->next;if (Q->rear = temp)Q->rear = Q->fro nt; free(temp);return Q;void display(QueueList *Q)QueueNode *temp; temp = Q->fro nt;if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext;cout << temp->data << en dl; typedefstruct ArcNod

25、e int adjvex;struct ArcNode *n extarc;ArcNode;typedefstruct VNode int data;ArcNode *firstarc;VNode,AdjListMAX VERTEX NUM:typedefstruct AdjList vertex;int vex nu m,arc num;/GraphKi nd kind;Graph;void CreateDN(Graph &G, int ejnt n)int i,j;G.vex num = n;G.arc num 二 e;for(i = 0;i <n ;i+)G.vertexi

26、.data = i+1; G.verte xi .firstarc = NULL;for(i nt k = 0;k < e;k+)cin >> i >> j;ArcNode *s,*p;s = (ArcNode*)malloc( sizeof(ArcNode); s->adjvex = j-1;s->n extarc = NULL;if (G.verte xi-1.firstarc = NULL)G.vertexi-1.firstarc = s;elsep = G.vertexi-1.firstarc; while (p ->n extarc!=

27、 NULL) p =p->n extarc;p->n extarc = s;void Findln Degree(Graph G,i nt in degree)int i;ArcNode *p;for(i = 0;i < G.vex nu m;i+)in degreei = 0;for(i = 0;i < G.vex nu m;i+)p = G.vertexi.firstarc;while(p)in degreep->adjvex+:p = p->n extarc;void TopologicalSort(Graph G)int i,k,count,inde

28、greeMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;for(i = 0;i < G.vex nu m;i+) visitedi = false;ArcNode *p;count = 0;Findln Degree(G,i ndegree); while(co unt < G.vex num) for(i = 0;i < G.vex nu m;i+)if(i ndegreei = 0 && visitedi = false) cout << G.vertexi.data;if (count < G.vex

29、num-1) cout <<""coun t+;visitedi = true;for(p = G.vertexi.firstarc;p;p = p->n extarc) k = p->adjvex;in degreek-; break;int mai n()int n;/節點數int m;/關系數cin >> n >> m;Graph G1;CreateDN(G1,m, n);TopologicalSort(G1); return 0;#in clude<iostream>3、usingn amespacestd

30、; #defi ne INFINITY 1000 #defi ne MAX_VERTEX_NUM 20 typedefi nt Elemtype; typedefi nt Elemtype; typedefstruct QueueNodeElemtype data; struct QueueNode *n ext;QueueNode; typedefstruct QueueList QueueNode *front;QueueNode *rear; QueueList;QueueList *CreateQueue() QueueList *Q;QueueNode *p;Q = (QueueLi

31、st*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->front = Q->rear = p;Q->fro nt->n ext = NULL;return Q;bool QueueEmpty(QueueList *Q) if(Q->fro nt = Q->rear) returntrue;elsereturnfalse;QueueList *En Queue(QueueList *Q, int eleme nt) QueueNode *p;p = (QueueN

32、ode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear- >n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp;if(!QueueEmpty(Q)temp = Q->fro nt->n ext; *e 二 temp->data:Q->fro nt->n ext = temp->next;if (Q->

33、rear = temp) Q->rear = Q->fro nt;free(temp);return Q;void display(QueueList *Q)QueueNode *temp; temp = Q->fro nt; if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext; cout << temp->data << en dl;typedefstruct Arc int adj; Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_N

34、UM; typedefstruct in t vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;/ GraphKi nd kind;Graph;void CreateAN(Graph &G, int n,int m)int i,j;int w = 0;G.vex num = n;G.arc num 二 m;for(i = 0;i < n ;i+)G.vertexi = i+1;for(i = 0;i < n ;i+)for(j = 0;j < n;j+) G.arcsij.adj = INFINIT Y;

35、for(int k = 0;k < m;k+)cin >> i >> j >> w;if (G.arcsi-1j-1.adj > w)G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = w;void Floyd(Graph G,i nt n ,i nt m)int i,j;int max = 0;int AMAX_VERTEX_NUMMAX_VERTEX_NUM;int pathMAX_VERTEX_NUMMAX_VERTEX_NUM; for(i = 0;i < n ;i+)for(j = 0;j < n;j

36、+)Aij = G.arcsij.adj;if(Aij < INFINIT Y) pathij = i; else pathij = 0;int t;int sum;for(i = 0;i < n;i+)t = 0;sum = 0;for(j = 0;j < n;j+) if(Aij < 1000) t+;sum = sum + Aij;if(t >= n-1 && sum < 20)cout << sum; exit(0);elsecon ti nue;for(i nt k = 0;k < n ;k+) for(i = 0

37、;i < n ;i+) for(j = 0;j < n;j+) if(Aik + Akj < Aij) Aij = Aik + Akj; pathij = pathkj;/cout << "處？理 O'a后 '?" << endl;for(i 二 0;i < n:i+)/ for(j = 0;j < n;j+)/if(Aij < INFINIT Y)/cout << Aij << "t"/else/cout << 0 << "t&