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

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

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

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

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

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

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

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

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

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