第二專長學分班第三次作業
DFS,BFS 第一題(60%) 隨機產生nxn的無向圖的相鄰矩陣(adjacency matrix),如下: 第二題(40%) 1.輸入有幾個節點 2.(10%)隨機產生nxn的鄰接矩陣,顯示可得有幾條邊 3.(10%)請顯示是哪幾個點互相配對(ex:(0,1),(0,2)…..) 4.(DFS:20%,BFS:20%)DFS,BFS的程式追蹤 第二題(40%) 1.(20%)依照第一題所給的方式建出隨機鄰接矩陣 ,此次的邊須隨機給上成本, 然後找出可遊歷各點的最低成本路徑 (不須走回原點,不可往回走,孤立點可不算,但須標明有幾個孤立點,起點為第一個節點) 2.(20%)依照上題所給出的圖和各邊的成本,此次每個點也隨機給上成本,並在 有限的成本下找出可走最多節點的數量 (起點成本為0)
DFS,BFS----第一題範例 Step1:假設輸入:5 Step4:配對邊長 (0,1)(0,4)(1,2)(1,3)(1,4)(2,3)(3,4) Step2:建立相鄰矩陣 Step5:DFS:0,1,2,3,4 BFS:0,1,4,2,3 Step3:圖形如右 DFS BFS
DFS,BFS----第二題範例(1) Step1:運用上題相鄰矩陣與範例圖 Step3:找出最低本路徑 成本:9 2 1 5 4 3 2 1 5 4
DFS,BFS----第二題範例(2) Step1:依照上題產生之圖,於各節點增加成本(紅色為節點成本 1~10) Step2:找出在有限成本下可走的最多節點(有限成本:(上述最小邊 成本)+所有節點成本/2,ex: 9 + 24/2 = 12) 此圖最多可走3個點 成本為:0+2+5+1+4 = 12 3 2 1 5 4 3 2 1 5 4 8 7 3 2 1 5 4 7 8
Send code and result (printscreen) Deadline 2018/1/15 12:00 a1193223911@gmail.com Deadline 2018/1/15 12:00 (HW1) 學號 系級 名字 (with rar format) 抄襲嚴懲 , 請打上註解不然斟酌扣分