第一篇：圖的應(yīng)用 實(shí)驗(yàn)
圖的應(yīng)用 實(shí)驗(yàn)日志
實(shí)驗(yàn)題目：圖的建立及輸出
實(shí)驗(yàn)?zāi)康模航D的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。實(shí)驗(yàn)主要步驟： 1.編輯源程序；
2.編寫有向圖的實(shí)現(xiàn)程序； 3.編寫實(shí)現(xiàn)無向圖的源程序；
4.連接—編譯—運(yùn)行該程序，并在過程中調(diào)試。源程序：
#include
typedef struct{ int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum;int arcnum;char vexs[MAX_VERTEX_NUM];}MGraph;
int LocateVex(MGraph G,char v){ int i;for(i=0;i if(G.vexs[i]==v) return i;} return 0;} int CreateUDG(MGraph G){ int i,j,k,w;char v1,v2;printf(“請輸入頂點(diǎn)和邊：n”);scanf(“%d%d”,&G.vexnum,&G.arcnum);for(i=0;i int CreateDG(MGraph G){ int i,j,k,w;char v1,v2;printf(“請輸入頂點(diǎn)和邊：n”);scanf(“%d%d”,&G.vexnum,&G.arcnum);for(i=0;i n”);} printf(“輸出的領(lǐng)接矩陣是：n”);for(i=0;i printf(“ %d ”,G.arcs[i][j]);printf(“n”);} return 0;} void main(){ char kind[5];MGraph G;printf(“請輸入要建立的圖的類型(UDG或DG)：n”); scanf(“%s”,kind);if(strcmp(“UDG”,kind)==0) CreateUDG(G);if(strcmp(“DG”,kind)==0) CreateDG(G);} 實(shí)驗(yàn)結(jié)果： 心得體會(huì)：通過實(shí)驗(yàn)掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu)； 數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)六 實(shí)驗(yàn)內(nèi)容:圖的基本操作 實(shí)驗(yàn)要求: 1)圖的遍歷與基本操作要作為函數(shù)被調(diào)用.2)把自己使用的圖結(jié)構(gòu)明確的表達(dá)出來.3)基本上實(shí)現(xiàn)每個(gè)實(shí)驗(yàn)題目的要求.分組要求：可單獨(dú)完成，也可兩人一組。 實(shí)驗(yàn)?zāi)康? 1)熟悉C/C++基本編程,培養(yǎng)動(dòng)手能力.2)通過實(shí)驗(yàn),加深對圖的理解.評分標(biāo)準(zhǔn)： 1)只完成第一和第二題，根據(jù)情況得4，5分； 2）完成前3題，根據(jù)情況得5至7分； 3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。 題目: 一)建立一個(gè)無向圖+遍歷+插入 (1)以數(shù)組表示法作為存儲(chǔ)結(jié)構(gòu)，從鍵盤依次輸入頂點(diǎn)數(shù)、弧數(shù)與各弧信息建立一個(gè)無向圖； (2)對（1）中生成的無向圖進(jìn)行廣度優(yōu)先遍歷并打印結(jié)果； (3)向（1）中生成的無向圖插入一條新弧并打印結(jié)果； 二)建立一個(gè)有向圖+遍歷+插入+刪除 (1)以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，從鍵盤輸入圖的頂點(diǎn)與弧的信息建立一個(gè)有向圖； (2)對（1）中生成的有向圖進(jìn)行深度優(yōu)先遍歷并打印結(jié)果； (3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結(jié)果； (4)在（1）中生成的有向圖中，分別插入與刪除一個(gè)頂點(diǎn)并打印結(jié)果； (5)在（1）中生成的有向圖中,各頂點(diǎn)的入度與出度并打印結(jié)果； 三）基本應(yīng)用題 （1）編寫算法，判斷圖中指定的兩個(gè)頂點(diǎn)是否連通。 （2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個(gè)數(shù) （3）編寫算法，判斷圖中任意兩個(gè)頂點(diǎn)的連通性 （4）編寫算法，判斷圖中是否存在回路。 （5）實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法。 四）高級應(yīng)用題 （1）實(shí)現(xiàn)Prim算法 （2）實(shí)現(xiàn)Kruskal算法 （3）實(shí)現(xiàn)迪杰斯特拉算法 （4）實(shí)現(xiàn)拓?fù)渑判蛩惴?/p> （5）實(shí)現(xiàn)關(guān)鍵路徑算法 北京郵電大學(xué)信息與通信工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二——圖 學(xué)生姓名： 佘晨陽 班 級： 2014211117 班內(nèi)序號： 20 學(xué) 號： 2014210491 日 期： 2015年12月05日 1．實(shí)驗(yàn)要求 根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個(gè)圖。圖的基本功能： 1、圖的建立 2、圖的銷毀 3、深度優(yōu)先遍歷圖 4、廣度優(yōu)先遍歷圖 5、使用普里姆算法生成最小生成樹 6、使用克魯斯卡爾算法生成最小生成樹 7、求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑 8、其他：比如連通性判斷等自定義操作 編寫測試main()函數(shù)測試圖的正確性 2.程序分析 本實(shí)驗(yàn)要求掌握圖基本操作的實(shí)現(xiàn)方法，了解最小生成樹的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)習(xí)使用圖解決實(shí)際問題的能力。 2.1 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)：1.不帶權(quán)值的無向圖鄰接矩陣 2.帶權(quán)值的無向圖鄰接矩陣 3.帶權(quán)值的有向圖鄰接矩陣 1．不帶權(quán)值的無向圖鄰接矩陣 第1頁 北京郵電大學(xué)信息與通信工程學(xué)院 2帶權(quán)值的無向圖鄰接矩陣.3.帶權(quán)值的有向圖鄰接矩陣 [備注]： 1.在使用打印元素、BFS、DFS 采用無權(quán)值的無向圖鄰接矩陣存儲(chǔ)方式 2.在使用PRIM、KRUSKAL、3.在使用最短路徑的算法時(shí)采用具有權(quán)值的有向圖鄰接矩陣存儲(chǔ)方式 2.2 關(guān)鍵算法分析 第2頁 北京郵電大學(xué)信息與通信工程學(xué)院 一．圖的鄰接矩陣構(gòu)造函數(shù)： 1.關(guān)鍵算法： template //帶權(quán)值的圖的構(gòu)造函數(shù) { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];} //初始化頂點(diǎn) for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化權(quán)值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化邊 { cout << “請輸入線性鏈接節(jié)點(diǎn):”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用無向圖帶權(quán)值的鄰接矩陣 } cout << endl;cout << “所得鄰接矩陣為：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印鄰接矩陣的格式 } cout << endl; } cout << endl 2.算法的時(shí)間復(fù)雜度 第3頁 北京郵電大學(xué)信息與通信工程學(xué)院 有構(gòu)造可知，初始化時(shí)其時(shí)間復(fù)雜度：O(n2) 二．深度優(yōu)先便利DFS: 1.關(guān)鍵算法 ①從某頂點(diǎn)v出發(fā)并訪問 ②訪問v的第一個(gè)未訪問的鄰接點(diǎn)w，訪問w的第一個(gè)未訪問的鄰接點(diǎn)u，…… ③若當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問過，則回溯，從上一級頂點(diǎn)的下一個(gè)未訪問過的頂點(diǎn)開始深度優(yōu)先遍歷 ④直到所有和v路徑相通的頂點(diǎn)都被訪問到； 2.代碼圖解： 深度優(yōu)先遍歷示意圖 3.代碼詳解： template for(int j = 0;j < vnum;j++) //連通圖 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//當(dāng)存在回路時(shí)，則連通深一層遍歷 } 4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度：O(n2) 空間復(fù)雜度：棧的深度O(n) 輔助空間O(n) 第4頁 北京郵電大學(xué)信息與通信工程學(xué)院 三．廣度遍歷BFS 1.關(guān)鍵算法 ①訪問頂點(diǎn)v ②依次訪問v的所有未被訪問的鄰接點(diǎn)v1,v2,v3… ③分別從v1,v2,v3…出發(fā)依次訪問它們未被訪問的鄰接點(diǎn) ④反復(fù)①②③，直到所有和v路徑相通的頂點(diǎn)都被訪問到； 2.代碼圖解 3.代碼詳解 1.初始化隊(duì)列Q 2.訪問頂點(diǎn)v，visited[v]=1 3.while(隊(duì)列非空) 3.1 v=隊(duì)頭元素出隊(duì) 3.2 訪問隊(duì)頭元素的所有未訪問的鄰接點(diǎn) 4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度：O(n2) 空間復(fù)雜度：輔助空間O(n) 四.最小生成樹——普里姆算法 1,關(guān)鍵思路 一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹上的結(jié)點(diǎn))和V-U(尚未落在生成樹上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。主數(shù)據(jù)結(jié)構(gòu)： 鄰接矩陣 輔助數(shù)據(jù)結(jié)構(gòu)： int adjvex[MAXSIZE];// U集中的頂點(diǎn)序號 第5頁 北京郵電大學(xué)信息與通信工程學(xué)院 int lowcost[MAXSIZE]; // U?(V-U)的最小權(quán)值邊 2.代碼圖解 第6頁 北京郵電大學(xué)信息與通信工程學(xué)院 第7頁 北京郵電大學(xué)信息與通信工程學(xué)院 3;代碼詳解 template //輔助數(shù)組存儲(chǔ)所有到的V0邊 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循環(huán)n-1次 { int k = Mininum(lowcost); //求下一個(gè)頂點(diǎn) cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //設(shè)置輔助數(shù)組 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8頁 北京郵電大學(xué)信息與通信工程學(xué)院 } } 4,時(shí)間復(fù)雜度： 時(shí)間復(fù)雜度O(n2)，適合稠密圖 五.最小生成樹----克魯斯卡爾算法 1,關(guān)鍵思路 先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。2.代碼圖解： 3.代碼詳解 template //最小生成樹—kruskal算法 { cout<<“Krusal算法結(jié)果為：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //兩個(gè)頂點(diǎn)分屬 第9頁 北京郵電大學(xué)信息與通信工程學(xué)院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度O(nlogn)，適合稀疏圖 六．最短路徑——Dijkstra算法 1.關(guān)鍵代碼 ? 按路徑長度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。? 1)設(shè)置集合s存儲(chǔ)已求得的最短路徑的頂點(diǎn)，? 2)初始狀態(tài)：s=源點(diǎn)v ? 3)疊代算法： ? 直接與v相連的最近頂點(diǎn)vi,加入s ? 從v經(jīng)過vi可以到達(dá)的頂點(diǎn)中最短的，加入s …… 2.代碼圖解 第10頁 北京郵電大學(xué)信息與通信工程學(xué)院 3.代碼詳解 emplate //關(guān)于最短路徑的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路徑和點(diǎn) { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反復(fù)經(jīng)過從該點(diǎn)到其他點(diǎn)的路徑 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11頁 北京郵電大學(xué)信息與通信工程學(xué)院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路徑長度和遍歷 } 4.時(shí)間復(fù)雜度 時(shí)間復(fù)雜度為：n^2 七．判斷連通圖算法 template { cout<<“該圖為連通圖！*******輸入成功！”< return false; } else { cout<<“該圖不為連通圖！*******請重新輸入”< return true; } } 時(shí)間復(fù)雜度：n^2 3.程序運(yùn)行結(jié)果 1.測試主函數(shù)流程： 第12頁 北京郵電大學(xué)信息與通信工程學(xué)院 函數(shù)流程圖： 1.輸入圖的連接邊并打印 構(gòu)造下面所示圖的鄰接矩陣： 第13頁 北京郵電大學(xué)信息與通信工程學(xué)院 2.判斷圖連通是否成功 3.BFS DFS PRIM算法的實(shí)現(xiàn) 第14頁 北京郵電大學(xué)信息與通信工程學(xué)院 4.克魯斯卡爾算法實(shí)現(xiàn)過程 4.有向圖鄰接矩陣的構(gòu)建 第15頁 北京郵電大學(xué)信息與通信工程學(xué)院 插入V0位置后打印距離并開始回溯 總結(jié) 1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法 問題一：prim算法中 解決方法：調(diào)整循環(huán)條件，修正函數(shù)體注意有無Next的區(qū)別 第16頁 北京郵電大學(xué)信息與通信工程學(xué)院 問題二：BFS和DFS同時(shí)在一個(gè)類里作用時(shí)會(huì)輸出錯(cuò)誤 解決方案：每次BFS/DFS使用時(shí)都把visited數(shù)組初始化一遍 問題三：在最短路徑，經(jīng)常出現(xiàn)了停止輸入的情況 解決方法：改return為continue，并修改打印算法 2.心得體會(huì) 通過本次實(shí)驗(yàn)，基本熟練掌握了c++基本語句，尤其對圖的結(jié)構(gòu)及應(yīng)用有了較深了解；調(diào)試代碼時(shí)盡量做到完成一個(gè)代碼段調(diào)試一次，可以最快檢測出錯(cuò)誤所在；類的封裝和調(diào)用，類的共有成員和私有成員的設(shè)置。 3.下一步的改進(jìn) 第一，設(shè)置增加圖節(jié)點(diǎn)和邊的函數(shù) 第二，實(shí)現(xiàn)圖形化輸出圖的路徑的功能 第三，主函數(shù)設(shè)計(jì)簡單，不要過于累贅 4.程序中出現(xiàn)的亮點(diǎn) 1)利用dfs算法衍生生成判斷是否為連通圖的連通算法 2)采用graph類實(shí)現(xiàn)所有圖的所有算法，所需的數(shù)據(jù)類型均在私有成員內(nèi)，封裝 3)利用convert函數(shù)采取象意輸入，采用ABCD的節(jié)點(diǎn)輸入方式而并非轉(zhuǎn)化成01234再輸入。 4)BFS中采用c++標(biāo)準(zhǔn)庫的。 5)打印鄰接矩陣時(shí)，打印出非鏈接的∞符號和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯(cuò)誤，重新輸入圖元素 第17頁 “數(shù)據(jù)結(jié)構(gòu)和算法II”課程實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)名稱：圖及其應(yīng)用 班級 姓名 學(xué)號 實(shí)驗(yàn)日期： 實(shí)驗(yàn)機(jī)時(shí)：2 學(xué)時(shí) 實(shí)驗(yàn)成績： -----------------一.實(shí)驗(yàn)?zāi)康模?/p> 1.熟練掌握圖的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法 2.掌握圖的基本運(yùn)算及應(yīng)用 3.加深對圖的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力 二.實(shí)驗(yàn)內(nèi)容：（1）基本實(shí)驗(yàn)內(nèi)容： 采用鄰接表或鄰接矩陣方式存儲(chǔ)圖，實(shí)現(xiàn)圖的深度遍歷和廣度遍歷； 用廣度優(yōu)先搜索方法找出從一頂點(diǎn)到另一頂點(diǎn)邊數(shù)最少的路徑。三.程序及注釋： #include “stdio.h” #include “l(fā)imits.h” //INT_MAX頭文件 #include “windows.h” //boolean頭文件 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW-1 #define OK 1 #define ERROR 0 typedef int Status;typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;typedef char* InfoType;typedef int QElemType;//邊信息 typedef struct ArcCell{ VRType adj;//1或0表示是否鄰接,對帶權(quán)圖，則為權(quán)值類型 InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖結(jié)構(gòu) typedef struct { VertexType vexs[MAX_VERTEX_NUM];//定點(diǎn)向量 AdjMatrix arcs; //鄰接矩陣，為一二維數(shù)組 //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int vexnum,arcnum;GraphKind kind; //圖的種類標(biāo)志 }MGraph;//輔助隊(duì)列 typedef struct QNode{ QElemType data;//數(shù)值域 struct QNode *next;//指針域 }QNode, *QueuePtr;typedef struct{ QueuePtr front;//隊(duì)頭 QueuePtr rear;//隊(duì)尾 }LinkQueue;//初始化隊(duì)列 Status InitQueue(LinkQueue &Q){ Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front){ printf(“內(nèi)存分配失敗!”);exit(OVERFLOW);} Q.front->next = NULL;return OK;} //插入元素到隊(duì)尾 Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p =(QueuePtr)malloc(sizeof(QNode));if(!p){printf(“n內(nèi)存分配失敗!”);exit(OVERFLOW);} p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;} //隊(duì)列判空 Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear;} //銷毀隊(duì)列 Status DestroyQueue(LinkQueue &Q){ while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;} return OK;} //刪除隊(duì)頭元素 Status DeQueue(LinkQueue &Q,QElemType &e){ if(QueueEmpty(Q)){printf(“n隊(duì)列為空！”);return ERROR;} QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK;} //對頂點(diǎn)v定位，返回該頂點(diǎn)在數(shù)組的下標(biāo)索引，若找不到則返回-1 int LocateVex(MGraph G,char v){ for(int i=0;i G.kind = UDN;printf(“輸入頂點(diǎn)個(gè)數(shù)和邊數(shù)(如：4,3):”);int vexnum,arcnum;scanf(“%d,%d”,&vexnum,&arcnum);G.vexnum=vexnum;G.arcnum=arcnum;//判斷是否超過頂點(diǎn)最大個(gè)數(shù) while(G.vexnum>MAX_VERTEX_NUM){printf(“最大頂點(diǎn)為20，重新輸入(如：4,3):”);scanf(“%d,%d”,&G.vexnum,&G.arcnum);} printf(“n依次輸入頂點(diǎn)向量值n”);int i;for(i=0;i //清空緩沖區(qū) fflush(stdin);printf(“第%d個(gè):”,i+1);scanf(“%c”,&G.vexs[i]);} //初始化鄰接矩陣 for(i=0;i int values;printf(“n輸入依附兩個(gè)頂點(diǎn)的邊及其權(quán)值<如，a,b,1>n”);for(i=0;i printf(“第%d條：”,i+1);//清空緩沖區(qū) fflush(stdin);scanf(“%c,%c,%d”,&rear,&front,&values);int m,n;//定位兩頂點(diǎn)在vexs數(shù)組中的索引 m = LocateVex(G,rear);n = LocateVex(G,front);if(m==-1||n==-1){ printf(“輸入頂點(diǎn)或不在此圖中，請重新輸入！n”);i--;continue;} //賦予對應(yīng)矩陣位置的權(quán)值，以及對稱弧的權(quán)值 G.arcs[m][n].adj = values;G.arcs[n][m].adj = values;} return OK;} //CreateUDG //矩陣輸出 void printArcs(MGraph G){ int i;printf(“ ”);//輸出第一行的頂點(diǎn)向量 for(i=0;i for(int j=0;j else printf(“ %d”,G.arcs[i][j].adj);}} printf(“ ∞”); printf(“n”);} //訪問頂點(diǎn)v輸出 Status printAdjVex(MGraph G,int v){ printf(“%c ”,G.vexs[v]);return OK;} //查找v頂點(diǎn)的第一個(gè)鄰接點(diǎn) Status FirstAdjVex(MGraph G,int v){ //查找與頂點(diǎn)v的第一個(gè)鄰接點(diǎn)，找到后立即返回其索引，若找不到，則返回-1 for(int i=1;i return i;} return-1;} //查找基于v頂點(diǎn)的w鄰接點(diǎn)的下一個(gè)鄰接點(diǎn) Status NextAdjVex(MGraph G,int v,int w){ //查找基于頂點(diǎn)v的w鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)，找到之后立即返回其索引，若找不到，則返回-1 for(int i=w+1;i boolean visited[MAX_VERTEX_NUM];//函數(shù)指針變量 Status(* VisitFunc)(MGraph G,int v);//DFS,從第v個(gè)頂點(diǎn)出發(fā)遞歸深度優(yōu)先遍歷圖G void DFS(MGraph G,int v){ visited[v] = TRUE;//訪問第v個(gè)頂點(diǎn) VisitFunc(G,v);for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}} //深度優(yōu)先遍歷 void DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //將函數(shù)復(fù)制給全局的函數(shù)指針變量，待調(diào)用DFS時(shí)使用 VisitFunc = Visit;int v;//將訪問標(biāo)記初始化為false for(v=0;v void BFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //按廣度優(yōu)先非遞歸遍歷圖G，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組Visited int v;int u;//將訪問標(biāo)記數(shù)組初始化為false for(v = 0;v //判斷頂點(diǎn)V是否被訪問 if(!visited[v]){//將第一次訪問的頂點(diǎn)對應(yīng)的訪問標(biāo)記數(shù)組位置賦值為TRUE visited[v] = TRUE;//輸出頂點(diǎn)v Visit(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){//按入隊(duì)序列取出頂點(diǎn)，便于查找此頂點(diǎn)的鄰接點(diǎn) DeQueue(Q,u);//查找當(dāng)前頂點(diǎn)鄰接點(diǎn) for(int w=FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) if(!visited[w]){visited[w] =TRUE;Visit(G,w);EnQueue(Q,w);}}} //銷毀隊(duì)列 DestroyQueue(Q);} int main(){ printf(“====圖的創(chuàng)建及其應(yīng)用====n”);//創(chuàng)建一個(gè)圖 MGraph G;CreateUDN(G);//用鄰接矩陣輸出圖 printf(“n圖的鄰接矩陣輸出如下:n”);printArcs(G);//深度優(yōu)先遍歷 printf(“n深度優(yōu)先遍歷序列:n”);DFSTraverse(G,printAdjVex);printf(“n”);//廣度優(yōu)先遍歷 } printf(“n廣度優(yōu)先遍歷序列:n”);BFSTraverse(G,printAdjVex);printf(“n”);四.運(yùn)行結(jié)果： 五.實(shí)驗(yàn)心得： 通過本次課程設(shè)計(jì)，對圖的概念有了一個(gè)新的認(rèn)識，在學(xué)習(xí)離散數(shù)學(xué)的時(shí)候，總覺得圖是很抽象的東西，但是在學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)與算法》這門課程之后，我慢慢地體會(huì)到了其中的奧妙，圖能夠在計(jì)算機(jī)中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說權(quán)值、頂點(diǎn)個(gè)數(shù)等，這也就說明了想要把生活中的信息轉(zhuǎn)化到計(jì)算機(jī)中必須用數(shù)字來完整的構(gòu)成一個(gè)信息庫，而圖的存在，又涉及到了頂點(diǎn)之間的聯(lián)系。圖分為有向圖和無向圖，而無向圖又是有向圖在權(quán)值雙向相等下的一種特例，如何能在計(jì)算機(jī)中表示一個(gè)雙向權(quán)值不同的圖，這就是一件很巧妙的事情。有了這次課程設(shè)計(jì)的經(jīng)驗(yàn)和教訓(xùn)，我能夠很清楚的對自己定一個(gè)合適的水平。 一、實(shí)驗(yàn)項(xiàng)目： 實(shí)驗(yàn)項(xiàng)目一：平面圖測繪實(shí)習(xí) 實(shí)驗(yàn)?zāi)康模和ㄟ^實(shí)習(xí)使學(xué)生掌握平面圖測繪的基本原理，學(xué)會(huì)小平板與皮尺配合測繪大比例尺平面圖的方法和過程。 實(shí)驗(yàn)任務(wù)：學(xué)生分成每組4-5人，每組完成校園內(nèi)部分地物的平面圖測繪。 實(shí)驗(yàn)器材：小平板儀、皮尺、三角板、比例尺、分規(guī)、大頭針、花桿、工具包 實(shí)驗(yàn)要求： 1、掌握平板儀的安置方法； 2、掌握碎部點(diǎn)的測繪方法； 3、會(huì)用地形圖圖式符號表示地物。 實(shí)驗(yàn)項(xiàng)目二：掃描矢量化成圖 實(shí)驗(yàn)?zāi)康模菏箤W(xué)生了解掃描矢量化的基本原理，學(xué)會(huì)用矢量化軟件進(jìn)行地圖數(shù)字化。 實(shí)驗(yàn)任務(wù)：先由指導(dǎo)教師進(jìn)行演示與操作，學(xué)生認(rèn)真觀察，指導(dǎo)完成后，學(xué)生方可進(jìn)行地圖數(shù)字化。 實(shí)驗(yàn)器材：微機(jī)、掃描矢量化軟件、地形圖一幅 實(shí)驗(yàn)要求： 1、地圖掃描成柵格圖形； 2、柵格圖形矢量化。實(shí)驗(yàn)項(xiàng)目三：數(shù)字化測圖系統(tǒng)認(rèn)識實(shí)習(xí) 實(shí)驗(yàn)?zāi)康模菏箤W(xué)生對數(shù)字化測圖系統(tǒng)的構(gòu)成有較為深刻的認(rèn)識，從而理解數(shù)字化測圖系統(tǒng)的全過程。 實(shí)驗(yàn)任務(wù)：實(shí)驗(yàn)時(shí)，以指導(dǎo)教師進(jìn)行演示與操作為主，學(xué)生認(rèn) 真觀察，指導(dǎo)完成后，學(xué)生方可進(jìn)行相應(yīng)適當(dāng)?shù)牟僮鳌?/p> 實(shí)驗(yàn)器材：全站儀、數(shù)字化儀、繪圖儀、繪圖軟件、掃描儀。實(shí)驗(yàn)要求： 1、演示現(xiàn)有地圖數(shù)字化方法（掃描數(shù)字化）； 2、演示全站儀外業(yè)數(shù)據(jù)向微機(jī)傳送； 3、演示內(nèi)業(yè)成圖的方法，使學(xué)生了解成圖軟件； 4、演示繪圖儀繪圖的過程，使學(xué)生初步認(rèn)識繪圖儀。 實(shí)驗(yàn)項(xiàng)目四：全站儀的認(rèn)識與使用 實(shí)驗(yàn)?zāi)康模毫私馊緝x的基本結(jié)構(gòu)，全站儀的基本操作方法。實(shí)驗(yàn)任務(wù)：實(shí)驗(yàn)時(shí)，先由指導(dǎo)教師進(jìn)行演示與操作，學(xué)生認(rèn) 真觀察，指導(dǎo)完成后，學(xué)生方可進(jìn)行相應(yīng)的操作。 實(shí)驗(yàn)器材：每組全站儀1臺，腳架2個(gè)，花桿2根，反光鏡2個(gè)，記錄板，鉛筆。 實(shí)驗(yàn)要求： 1、熟悉全站儀測角模式、測距模式和坐標(biāo)模式下的基本操作； 2、一個(gè)測站上已知數(shù)據(jù)的輸入和碎部點(diǎn)坐標(biāo)的測量方法。 實(shí)驗(yàn)項(xiàng)目五：野外數(shù)據(jù)采集測量實(shí)習(xí) 實(shí)驗(yàn)?zāi)康模菏箤W(xué)生學(xué)會(huì)使用全站儀進(jìn)行野外大比例尺數(shù)字測圖的基本方法。 實(shí)驗(yàn)任務(wù)：先由指導(dǎo)教師進(jìn)行演示與操作，學(xué)生認(rèn)真觀察，指導(dǎo)完成后，學(xué)生方可進(jìn)行相應(yīng)的操作。 實(shí)驗(yàn)器材：每組全站儀一臺、腳架兩個(gè)、花桿兩個(gè)、反光鏡兩個(gè)、記錄板、鉛筆 實(shí)驗(yàn)要求： 1、熟悉全站儀在數(shù)據(jù)采集模式下的基本操作； 2、了解外業(yè)數(shù)據(jù)文件的記錄格式； 3、學(xué)會(huì)“一步測量法”野外數(shù)據(jù)測圖的基本方法； 4、學(xué)會(huì)野外工作草圖的繪制和記錄方法； 5、根據(jù)具體條件每組完成老師指定范圍內(nèi)的地形測量任務(wù)。 實(shí)驗(yàn)項(xiàng)目六：地形圖的內(nèi)業(yè)編繪和輸出 實(shí)驗(yàn)?zāi)康模菏箤W(xué)生學(xué)會(huì)地形圖的內(nèi)業(yè)編繪和輸出方法。實(shí)驗(yàn)任務(wù)：先由指導(dǎo)教師進(jìn)行演示與操作，學(xué)生認(rèn)真觀察，指導(dǎo)完成后，學(xué)生方可進(jìn)行地形圖的編繪。實(shí)驗(yàn)器材：微機(jī)、繪圖儀、成圖軟件 實(shí)驗(yàn)要求： 1、將實(shí)習(xí)5中預(yù)處理過的數(shù)據(jù)，利用成圖軟件繪成地形圖； 2、對所繪地形圖進(jìn)行編輯修改（包括注記）； 3、學(xué)會(huì)地形圖分幅及圖廓的繪制和注記； 4、將所繪圖形在繪圖儀上輸出。 二、實(shí)驗(yàn)課考核方式： （1）實(shí)習(xí)報(bào)告：每位參加實(shí)驗(yàn)的同學(xué)必須提交實(shí)習(xí)報(bào)告。實(shí)習(xí)報(bào)告主要內(nèi)容包括：實(shí)習(xí)的目的、要求及內(nèi)容，實(shí)驗(yàn)原理、方法、步驟，技術(shù)參數(shù)，實(shí)驗(yàn)結(jié)果及實(shí)驗(yàn)結(jié)果分析，實(shí)習(xí)體會(huì)等。（2）實(shí)驗(yàn)課考核方式 考核方式：評閱實(shí)習(xí)報(bào)告與儀器操作測驗(yàn)相結(jié)合。第二篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)--圖
第三篇：數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)一 圖[推薦]
第四篇：湘潭大學(xué) 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)5 實(shí)驗(yàn)報(bào)告 源代碼 圖的應(yīng)用
第五篇：數(shù)字測圖實(shí)驗(yàn)指導(dǎo)書
點(diǎn)擊咨詢 