數(shù)據(jù)結(jié)構(gòu)實驗六

1、實驗六實驗名稱圖及其應(yīng)用實驗性質(zhì)設(shè)計性實驗學(xué)時數(shù) 6學(xué)時、實驗?zāi)康?. 掌握圖的存儲結(jié)構(gòu)及其實現(xiàn)。2. 掌握圖的深度和廣度遍歷算法及其實現(xiàn)。3掌握圖的常見算法的思想及應(yīng)用。、實驗內(nèi)容1. 實現(xiàn)對無向圖的存儲和遍歷等操作。2. 最小生成樹問題。Z三、實 驗 過 程1、實驗題目 問題描述以下題目根據(jù)自己興趣和能力可選作一道作為實驗題目：（1） 使用鄰接表或鄰接矩陣存儲一個無向圖，實現(xiàn)對其進(jìn)行深度和廣度遍歷的 操作；（2）n個城市之間建立通信聯(lián)絡(luò)網(wǎng)，最多可能設(shè)置 n（n-1）/2 條線路，那么, 如何在這些可能的線路中選擇 n-1條，以使總的耗費最少。使用最小生成樹實 現(xiàn)解決此問題。（3）根據(jù)一張自

2、駕游旅游路線圖，可以知道城市間的高速公路長度以及該公路 要收取的過路費?，F(xiàn)在編寫一個程序，找出一條出發(fā)地和目的地之間的最短路 徑。如果有若干條路徑都是最短的，那么需要輸出過路費最少的一條路徑?；疽螅?）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、源程序(1)#in clude#in cludevstdio.hin t visited20;typ edef struct ArcNodeint adj; ArcNode;typ edef structin t vert

3、ex20;ArcNode arc2020;int vex nu m,arc num;AdjMatrix;創(chuàng)建一個有向網(wǎng)*/void Create(AdjMatrix *G) /* int i,j,k, n,e;printf(請輸入圖中頂點的個數(shù)和邊數(shù):);scan f(%d%d,&n,&e);G-vex num=n;G-arc num=e;printf(請輸入各頂點的值:);for (i=0;ivex nu m;i+)sca nf(%d,&G-vertexi);for (i=0;ivex nu m;i+) for(j=0;jvex nu m;j+) G-arcij.adj=0;printf(請

4、輸入有關(guān)聯(lián)的兩個頂點的下標(biāo):n);for (k=0;karc nu m;k+)scan f(%d%d,&i,&j);G-arcij.adj=1;G-arcji.adj=1;/*圖g為鄰接矩陣類型void De pthFristSearch(AdjMatrix g, i nt i) AdjMatrix */ int j;prin tf(%d,g.vertexi);visitedi=1;for (j=0;jvg.vex nu m;j+)if (!visitedj&g.arcij.adj=1)Dep thFnstSearch(g,j);void TraverseGra ph(AdjMatrix g) int i;for(i=0;ig.vex nu m;i+) visitedi=0;for(i=0;ig.vex nu m;i+) if(!visitedi)Dep thFristSearch(g,i);int mai n() / 主函數(shù) int i,j;AdjMatrix g;Create(&g);printf(輸出關(guān)系二維矩陣:);for(i=0;ig.vex nu m;i+)for (j=0;jg.vex nu m;j+)prin tf(%d,g.arcij.adj);prin