演算法作业.pdf

演算法作業 Reporter : Ying-Hong Wang E-mail :inhon@.tw Date : June 7, 2015 指定作業一  實作DFS與BFS演算法 – 請依據課程的演算法實作DFS與BFS程式 – 程式語言限使用C或C++或Java三種之一 – 程式須內建一個圖形結構，如次頁所示 – 程式輸出為DFS 、BFS Traversal圖形結構節點的編號順序 – Due Date: Source Code and Executing Results, April 8, 21:00前 – 上傳的FTP Server 23:8080 ，選擇演算法資料 夾，帳號Algorithm ，密碼E509 ，限用校內IP – 上傳檔名需以學號開頭，如402410000_source.txt – 遲交者，每24小時內扣本次作業10分，扣至0分為止，以本FTP Server時間為基準 inhon@.tw June 7, 2015 指定作業一 (續)  實作DFS與BFS演算法 – 處理之圖形結構 – 起始節點為b inhon@.tw June 7, 2015 分組指定作業一  實作Biconnected Component演算法 – 請依據自我學習教材的演算法實作Biconnected component程式 – 程式語言限使用C或C++或Java三種之一 – 程式需可輸入G=(V, E)的格式，參考範例如次頁 – Due Date: 至少3個Test Cases與預期輸出，April 17, 08:00前 – Due Date: Source Code and Executing Results, April 26, 23:00前 – Test Cases佔本次作業成績的20% – Source Code Executing Results佔本作業成績的80% – 請依組別上傳對應資料夾 – 繳交細節依助教指示 – 分組作業逾時零分計，以FTP Server時間為基準 inhon@.tw June 7, 2015 分組指定作業一 (續)  實作Biconnected Component演算法 – 圖形結構輸入範例，如左圖 – 輸入順序為 – G = 9 ，表示共有9個節點 – V = {0, 1, 2, 3, 4, 5, 6, 7, 8, } ，節點代號 – E = {(0, 1), (0, 3), (0, 4), (1, 3), (1, 4), (2, 4), (2, 5), (3, 4), (4, 5), (4, 7), (5, 8), (6, 7). (7, 8)} ，邊的代號 – 因為是無向圖，所以，程式的資料結構，使用Adjacency Matrix 或Adjacency List時要記得自動補上對稱的邊，例如，Edge (1, 3) 同時也表示有(3, 1)的edge 。 inhon@.tw June 7, 2015 Agile Method 作業時程  Agile Method 作業說明請參閱 – AgileMethodProjectDescription  三個工具請參閱台灣敏捷苗圃提供的說明與四個Lab範例說明 – Lab03 04 – Lab22 – Lab27  三個子作業繳交時間分別為 1) User manual Acceptance test cases (.do