20192305 2020-2021-1 《數據結構與面向對象程序設計》實驗九報告

課程：《程序設計與數據結構》
班級： 1923
姓名： 王梓全
學號：20192305
實驗教師：王志強
實驗日期：2020年12月25日
必修/選修： 必修

1.實驗內容、

(1)初始化：根據屏幕提示（例如：輸入1為無向圖，輸入2為有向圖）初始化無向圖和有向圖（可用鄰接矩陣，也可用鄰接表），圖需要自己定義（頂點個數、邊個數，建議先在草稿紙上畫出圖，然后再輸入頂點和邊數）（2分）
(2)圖的遍歷：完成有向圖和無向圖的遍歷（深度和廣度優先遍歷）（4分）
(3)完成有向圖的拓撲排序，并輸出拓撲排序序列或者輸出該圖存在環（3分）
(4) 完成無向圖的最小生成樹（Prim算法或Kruscal算法均可），并輸出（3分）
(5) 完成有向圖的單源最短路徑求解（迪杰斯特拉算法）（3分）

2. 實驗過程及結果

(1)初始化：根據屏幕提示（例如：輸入1為無向圖，輸入2為有向圖）初始化無向圖和有向圖（可用鄰接矩陣，也可用鄰接表），圖需要自己定義（頂點個數、邊個數，建議先在草稿紙上畫出圖，然后再輸入頂點和邊數）
(2)圖的遍歷：完成有向圖和無向圖的遍歷（深度和廣度優先遍歷）
(3)完成有向圖的拓撲排序，并輸出拓撲排序序列或者輸出該圖存在環
(4) 完成無向圖的最小生成樹（Prim算法或Kruscal算法均可），并輸出
(5) 完成有向圖的單源最短路徑求解（迪杰斯特拉算法）

3. 實驗過程中遇到的問題和解決過程

• 問題1：圖加權等內容輸入錯誤
• 問題1解決方案：在紙上畫出相應的構建圖，根據圖來設計。

其他（感悟、思考等）

本次實驗內容理解的還算可以，但用編程來實現還是有點困難，仍需要多多練習。

參考資料

• 《Java程序設計與數據結構教程（第二版）》

• 《Java程序設計與數據結構教程（第二版）》學習指導![](htt![![]