實(shí)驗(yàn)四圖的深優(yōu)先與廣優(yōu)先遍歷

1、實(shí)驗(yàn)報(bào)告學(xué)院（系）名稱：計(jì)算機(jī)與通信工程學(xué)院姓名* *學(xué)號* *專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級2015級*班實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)四：圖的深度優(yōu)先與廣度優(yōu)先遍歷 課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程代碼0661013實(shí)驗(yàn)時(shí)間2017年5 月 12日第5-6節(jié)實(shí)驗(yàn)地點(diǎn)7-216考核標(biāo)準(zhǔn)實(shí)驗(yàn)過程25分程序運(yùn)行20分回答問題15分實(shí)驗(yàn)報(bào)告30分特色功能5分考勤違紀(jì)情況5分成績成績欄其它批改意見: 教師簽字：考核內(nèi)容評價(jià)在實(shí)驗(yàn)課堂中的表現(xiàn)，包括實(shí)驗(yàn)態(tài)度、編寫程序過程等內(nèi)容等。功能完善, 功能不全有小錯(cuò)無法運(yùn)行正確基本正確有提示無法回答完整較完整一般內(nèi)容極少無報(bào)告有無有無 一、 實(shí)驗(yàn)?zāi)康?理解圖的邏輯特點(diǎn)；掌握理解圖的兩種主要存

2、儲結(jié)構(gòu)（鄰接矩陣和鄰接表），掌握圖的構(gòu) 造、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法二、 實(shí)驗(yàn)題目與要求1. 每位同學(xué)按下述要求實(shí)現(xiàn)相應(yīng)算法： 根據(jù)從鍵盤輸入的數(shù)據(jù)創(chuàng)建圖（圖的存儲結(jié)構(gòu)可采用鄰接矩陣或鄰接表），并對圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索 1）問題描述：在主程序中提供下列菜單： 1圖的建立 2深度優(yōu)先遍歷圖 3廣度優(yōu)先遍歷圖 0結(jié)束 2）實(shí)驗(yàn)要求：圖的存儲可采用鄰接表或鄰接矩陣；定義下列過程： CreateGraph(): 按從鍵盤的數(shù)據(jù)建立圖 DFSGrahp()：深度優(yōu)先遍歷圖 BFSGrahp()：廣度優(yōu)先遍歷圖 3）實(shí)驗(yàn)提示: 圖的存儲可采用鄰接表或鄰接矩陣； 圖存儲數(shù)據(jù)類型定義 （鄰接

3、表存儲） # define MAX_VERTEX_NUM 8 /頂點(diǎn)最大個(gè)數(shù) typedef struct ArcNode int adjvex; struct ArcNode *nextarc; int weight; /邊的權(quán) ArcNode; /表結(jié)點(diǎn) # define VertexType int /頂點(diǎn)元素類型 typedef struct VNode int degree,indegree; /頂點(diǎn)的度，入度 VertexType data; ArcNode *firstarc; Vnode /*頭結(jié)點(diǎn)*/; typedef struct Vnode verticesMAX_VER

4、TEX_NUM; int vexnum,arcnum;/頂點(diǎn)的實(shí)際數(shù)，邊的實(shí)際數(shù) ALGraph; 4）注意問題: 注意理解各算法實(shí)現(xiàn)時(shí)所采用的存儲結(jié)構(gòu)。 注意區(qū)別正、逆鄰接。 2. 拓?fù)渑判颍航o出一個(gè)圖的結(jié)構(gòu)，輸出其拓?fù)渑判蛐蛄校旤c(diǎn)序列用空格隔開），要求在同等 條件下，編號小的頂點(diǎn)在前。 3利用最小生成樹算法解決通信網(wǎng)的總造價(jià)最低問題 1）問題描述：若在 n 個(gè)城市之間建通信網(wǎng)絡(luò)，架設(shè) n-1 條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建 設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)絡(luò)的最小生成樹問題。 2）實(shí)驗(yàn)要求：利用 Prim 算法求網(wǎng)的最小生成樹。 3) 實(shí)現(xiàn)提示：通信線路一旦建立，必然是雙向的。因此，構(gòu)造最小生

5、成樹的網(wǎng)一定是無向網(wǎng)。 為簡單起見，圖的頂點(diǎn)數(shù)不超過 10 個(gè)，網(wǎng)中邊的權(quán)值設(shè)置成小于 100。三、 實(shí)驗(yàn)過程與實(shí)驗(yàn)結(jié)果 應(yīng)包括如下主要內(nèi)容： 數(shù)據(jù)結(jié)構(gòu)定義 圖是由定點(diǎn)集合及定點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)，其形式化定義為Graph = （V，E）其中，V = x|x某個(gè)數(shù)據(jù)對象是定點(diǎn)的有限非空集合；E = （x,y）|x,yVPath(x,y)是頂點(diǎn)之間關(guān)系的有限集合，叫做便集。集合E中的Path（x,y）表示頂點(diǎn)x和頂點(diǎn)y之間有一條直接連線，即（x,y）表示一條邊，它是有方向的。 算法設(shè)計(jì)思路簡介 算法描述：可以用自然語言、偽代碼或流程圖等方式 1、 圖的深度優(yōu)先搜索： 在訪問圖中某一起

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

7、BFS）在訪問了起始頂點(diǎn)V之后，由V出發(fā)，依次訪問V的各個(gè)未曾被訪問過的鄰接點(diǎn)w1,w2,wt,然后再順序訪問w1,w2,wt，的所有還為訪問過的鄰接點(diǎn)。再從這些頂點(diǎn)出發(fā)，訪問它們還未訪問過的鄰接點(diǎn)，如此做下去，直到圖中所有頂點(diǎn)都被訪問過為止。 2、 （1）將沒有前驅(qū)（入度為零）的頂點(diǎn)進(jìn)棧。 （2）從棧中退出棧頂元素輸出，并把該頂點(diǎn)引出的所有弧刪去，即把它的各個(gè)鄰接點(diǎn)的入度減1，同時(shí)將當(dāng)前已輸出的頂點(diǎn)個(gè)數(shù)加1. （3）將新的入度為零的頂點(diǎn)再進(jìn)棧。 （4）重復(fù)（2）、（2）兩步，直到棧為空為止。此時(shí)或者已經(jīng)輸出前部頂點(diǎn)，或者剩下的頂點(diǎn)中沒有入度為零的頂點(diǎn)。 3、 設(shè)置一個(gè)n*n的矩陣A（k），其

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

9、i到j(luò)的最短路徑的長度。 算法的實(shí)現(xiàn)和測試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問題及解決辦法等 1、 2、 3、 算法時(shí)間復(fù)雜度分析 1、 深度優(yōu)先遍歷：O（n*n）. 廣度優(yōu)先遍歷：O（n*n）. 2、 O（n+e）. 3、 O(n*n*n).四、收獲與體會不想說什么，這章的程序太難了，每次一想起來數(shù)據(jù)結(jié)構(gòu)還沒做就煩，前兩個(gè)題基本上一天能做一道題，第三題也就是騙騙OJ，實(shí)際上還有個(gè)小BUG，等有空再寫個(gè)真正符合題意的程序吧。五、源代碼清單1、#includeusing namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_

10、NUM 20/typedef enum DG,DN,AG,ANGraphKind;typedef int Elemtype;typedef struct QueueNodeElemtype data;struct QueueNode *next;QueueNode;typedef struct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (Queu

11、eNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-next = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)return true;elsereturn false;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-next = NULL;Q-rear-next

12、 = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-next;*e = temp-data;Q-front-next = temp-next;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(tem

13、p-next != NULL)temp = temp-next;cout data endl;typedef struct Arc int adj;Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct int vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;/GraphKind kind;Graph;void CreateAG(Graph &G,int n,int m)int i,j;G.vexnum = n;G.arcnum = m;for(i = 0;i n;i+)G.v

14、ertexi = i + 1;for(i = 0;i n;i+)for(j = 0;j n;j+)G.arcsij.adj = 0;for(int k = 0;k i j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool visitedMAX_VERTEX_NUM;int count = 0;void DFS(Graph G,int v)visitedv-1 = true;count+;cout v;if(count G.vexnum)cout ;for(int i = v;i G.vexnum;i+)if(G.arcsv-1i.adj != 0 & !

15、visitedi)DFS(G,G.vertexi);void DFSTraverse(Graph G)int v = 0;for(v = 0;v G.vexnum;v+)visitedv = false;v = 1;/遍歷入口點(diǎn)DFS(G,v);void BFS(Graph G)int i,j;int k = 0;int v = 0;int u = 0;for(v = 0;v G.vexnum;v+)visitedv = false;QueueList *queue;queue = CreateQueue();v = 1;EnQueue(queue,v);visitedv-1 = true;w

16、hile(!QueueEmpty(queue)DeQueue(queue,&u);k+;cout u;if(k G.vexnum)cout ;for(int i = u;i n m;CreateAG(G1,n,m);DFSTraverse(G1);cout endl;BFS(G1);return 0;2、#includeusing namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef int Elemtype;typedef struct QueueNodeElemtype data;struct Queu

17、eNode *next;QueueNode;typedef struct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-next = NULL;return Q;bool QueueEmpty(QueueList *Q)

18、if(Q-front = Q-rear)return true;elsereturn false;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-next = NULL;Q-rear-next = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q

19、-front-next;*e = temp-data;Q-front-next = temp-next;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-next != NULL)temp = temp-next;cout data endl;typedef struct ArcNode int adjvex;struct ArcNode *nextarc;ArcNod

20、e;typedef struct VNode int data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertex;int vexnum,arcnum;/GraphKind kind;Graph;void CreateDN(Graph &G,int e,int n)int i,j;G.vexnum = n;G.arcnum = e;for(i = 0;i n;i+)G.vertexi.data = i+1;G.vertexi.firstarc = NULL;for(int k = 0;k i j

21、;ArcNode *s,*p;s = (ArcNode*)malloc(sizeof(ArcNode);s-adjvex = j-1;s-nextarc = NULL;if(G.vertexi-1.firstarc = NULL)G.vertexi-1.firstarc = s;else p = G.vertexi-1.firstarc;while(p -nextarc!= NULL)p =p-nextarc;p-nextarc = s;void FindInDegree(Graph G,int indegree)int i;ArcNode *p;for(i = 0;i G.vexnum;i+

22、)indegreei = 0;for(i = 0;i adjvex+;p = p-nextarc;void TopologicalSort(Graph G)int i,k,count,indegreeMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;for(i = 0;i G.vexnum;i+)visitedi = false;ArcNode *p;count = 0;FindInDegree(G,indegree);while(count G.vexnum)for(i = 0;i G.vexnum;i+)if(indegreei = 0 & visited

23、i = false)cout G.vertexi.data;if(count G.vexnum-1)cout nextarc)k = p-adjvex;indegreek-;break;int main()int n;/節(jié)點(diǎn)數(shù)int m;/關(guān)系數(shù)cin n m;Graph G1;CreateDN(G1,m,n);TopologicalSort(G1);return 0;3、#includeusing namespace std;#define INFINITY 1000#define MAX_VERTEX_NUM 20typedef int Elemtype;typedef int Elemt

24、ype;typedef struct QueueNodeElemtype data;struct QueueNode *next;QueueNode;typedef struct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-fro

25、nt-next = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)return true;elsereturn false;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-next = NULL;Q-rear-next = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,

26、Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-next;*e = temp-data;Q-front-next = temp-next;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-next != NULL)temp = temp-next;cout data endl;typedef str

27、uct Arc int adj;Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct int vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;/GraphKind kind;Graph;void CreateAN(Graph &G,int n,int m)int i,j;int w = 0;G.vexnum = n;G.arcnum = m;for(i = 0;i n;i+) G.vertexi = i+1;for(i = 0;i n;i+)for(j = 0;j n;j+)

28、G.arcsij.adj = INFINITY;for(int k = 0;k 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,int n,int 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+)Aij = G.arcsij.adj;if(Aij INFINITY) 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 = n-1 & sum 20)cout sum;exit(0);elsecontinue;for(int k = 0;k n;k+)for(i = 0;i n;