實驗五 的基本操作.doc

《實驗五 的基本操作.doc》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、實驗五圖的基本操作一、實驗目的1、使學生可以鞏固所學的有關圖的基本知識。2、熟練掌握圖的存儲結構。3、熟練掌握圖的兩種遍歷算法。二、實驗內容本次實驗提供4個題目，難度相當，學生可以根據(jù)自己的情況選做，其中題目一是必做題，其它選作！題目一：圖的遍歷（必做）[問題描述]　　對給定圖，實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。[基本要求]　　　以鄰接表為存儲結構，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結點為起點，分別輸出每種遍歷下的結點訪問序列?！緶y試數(shù)據(jù)】　　由學生依據(jù)軟件工程的測試技術自己確定。題目二：在圖G中求一條從頂點i到頂點s的簡單路

2、徑［測試數(shù)據(jù)］自行設計[題目三]：在圖G中求一條從頂點i到頂點s且長度為K的簡單路徑［測試數(shù)據(jù)］自行設計三、實驗前的準備工作1、掌握圖的相關概念。2、掌握圖的邏輯結構和存儲結構。3、掌握圖的兩種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結果。3、結合運行結果，對程序進行分析。一．實驗內容定義結構體QueueNode，并完成隊列的基本操作，利用隊列先進先出的性質，在廣度優(yōu)先遍歷時將隊列作為輔助工具來完成廣度優(yōu)先遍歷。?l?void?EnQueue(QueueList*?Q,int?e)

3、函數(shù)實現(xiàn)進隊操作，if-else語句完成函數(shù)的具體操作?l?void?DeQueue(QueueList*?Q,int*?e)函數(shù)實現(xiàn)出隊操作，if-else語句完成函數(shù)的具體操作?l?void?CreatAdjList(Graph*?G)函數(shù)用來完成創(chuàng)建圖的操作，其中使用兩次for循環(huán)語句第一次用循環(huán)語句輸入頂點，第二次建立無向圖中的邊和表，流程圖如圖表1所示?l?void?dfs(Graph?*G,int?i,int?visit[])函數(shù)是從第i個頂點出發(fā)遞歸的深度優(yōu)先遍歷圖G深度優(yōu)先搜索：dfs()：尋找v的還沒有訪問過的鄰接點，循環(huán)找到v

4、的所有的鄰接點，每找到一個都以該鄰接點為新的起點遞歸調用深度優(yōu)先搜索，找下一個鄰接點。?voiddfs(vexsb,adjmata,intv,intvisited[],intn)??{intw;??cout<

5、w存放下一個鄰接點的變量序號和隊尾隊首的指針。?voidbfs(vexsb,adjmata,intv,intvisited[],intn)??{?intqueue[Max];?intw,rear,first;?rear=first=0;???cout<

6、??cout<

7、先遍歷時for循環(huán)判斷等。?void?main(){??int?n,m,i,j,k1,k2;???vexsb;??adjmata;??charv1,v2;??intvisited[Max];??cout<<"請輸入頂點數(shù):";??cin>>n;??for(i=0;i>b[i];??cout<<"請輸入弧的條數(shù):";??cin>>m;??cout<<"請依次

8、輸入各條弧:"<