Download presentation
Presentation is loading. Please wait.
1
第二專長學分班第三次作業
2
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)
3
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, BFS:0,1,4,2,3 Step3:圖形如右 DFS BFS
4
DFS,BFS----第二題範例(1) Step1:運用上題相鄰矩陣與範例圖 Step3:找出最低本路徑 成本:9
2 1 5 4 3 2 1 5 4
5
DFS,BFS----第二題範例(2) Step1:依照上題產生之圖，於各節點增加成本(紅色為節點成本 1~10)
Step2:找出在有限成本下可走的最多節點(有限成本:(上述最小邊 成本)+所有節點成本/2，ex: /2 = 12) 此圖最多可走3個點 成本為: = 12 3 2 1 5 4 3 2 1 5 4 8 7 3 2 1 5 4 7 8
6
Send code and result (printscreen) Deadline 2018/1/15 12:00
Deadline 2018/1/15 12:00 (HW1) 學號 系級 名字 (with rar format) 抄襲嚴懲 , 請打上註解不然斟酌扣分
Similar presentations
