一、實驗名稱:圖的遍歷算法設計與實現
二、實驗目的:
1.掌握圖的深度優先遍歷的算法。
2.掌握圖的廣度優先遍歷的算法。
3.實驗章節:算法設計與分析 第四章
三、實驗內容。實驗問題和程序運行結果
第一部分 廣度優先遍歷算法
1. 分析Graph類,畫出Graph類初始化以後的Graph對象的數據結構圖。
2. 分析BFS函數,畫出流程圖。
3. 上述程序 int data[7][7]={{ 1,-1,-1,-1,-1,-1,-1},
{ 6, 3, 2,-1,-1,-1,-1},
{ 0,-1,-1,-1,-1,-1,-1},
{ 2, 0,-1,-1,-1,-1,-1},
{ 6, 5,-1,-1,-1,-1,-1},
{ 1,-1,-1,-1,-1,-1,-1},
{ 5, 3,-1,-1,-1,-1,-1}};
是對課本圖4-1的輸入,從0開始的廣度優先的順序是:
4. 若上圖從節點4開始遍歷的話,廣度優先的順序應該是什麼。
5. 分析當Graph類對象,在輸入以下圖1的時候,從0開始的廣度優先順序是什麼。自己設計data[][]數據進行輸入,並給出該種輸入情況下的遍歷順序。
6. 改寫程序,輸出parent數組值,並根據parent畫出圖1的廣度優先深林。
第二部分 深度優先遍歷算法
四、實驗小結和心得: