數(shù)據(jù)結構實驗六

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

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

3、ode arc2020;int vex nu m,arc num;AdjMatrix;void Create(AdjMatrix *G) /*創(chuàng)建一個有向網(wǎng) */ 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(請輸入有關聯(lián)的兩個頂點的

4、下標:n);for (k=0;karc nu m;k+) scan f(%d%d,&i,&j);G-arcij.adj=1;G-arcji.adj=1;void DepthFristSearch(AdjMatrix g, int i)/* 圖 g 為鄰接矩陣類型AdjMatrix */ int j;prin tf(%d,g.vertexi);visitedi=1;for (j=0;jvg.vex nu m;j+)if (!visitedj&g.arcij.adj=1) DepthFristSearch(gj);void TraverseGraph(AdjMatrix g) int i;for(i=0;ig.vex nu m;i+) visitedi=0;for(i=0;ig.vex nu m;i+) if(!visitedi) DepthFristSearch(g,i);int mai n() /主函數(shù) int i,j;AdjMatrix g;Create(&g);printf(”輸出關系二維矩陣:);for(i=0;ig.vex nu m;i+)for (j=0;jg.vex nu m;j+)prin tf(%d,g.arcij.adj);prin tf(t);printf(無向