https://i.imgur.com/5vO858Y.jpg
https://i.imgur.com/FHjB1fG.jpg
請問這一題我這樣寫可以嗎？
有什麼bug嗎？
感謝～
作者:
s06i06 (三條魚)
2017-12-31 14:50:00If那行沒講怎麼找的 如果linear search 是O(|V|^2)
作者:
TWkobe (中華柯比)
2017-12-31 15:04:00If 那段應該寫成迴圈一個一個比對最簡易
所以我要假設G是一個adjancency matrixV€adj.[B]就去測那個欄位是不是1就好不過他的input只有A B不是應該要有個G嗎？不管是用什麼來存那個圖？
作者:
s06i06 (三條魚)
2017-12-31 15:07:00我覺得可以用hash? A相鄰點的丟進hash table,再檢測B相鄰的點有沒有在table裡,有個話count++
我原本也想用迴圈，不過他的input沒有讓我傳矩陣，寫起來毛毛的XD
作者:
s06i06 (三條魚)
2017-12-31 15:08:00這樣O(|V|)用adjMatrix是O(|V|^2)題目要求要最佳化運算量
作者:
TWkobe (中華柯比)
2017-12-31 15:11:00也可以用bfs喔用bfs code超簡單只要將a,b兩個node各別作一次的enqueue adj vertex然後dequeue兩個queue來比對
用bfs的前提是不是要把相鄰node由小到大enqueue?
作者:
TWkobe (中華柯比)
2017-12-31 15:20:00謝謝樓上補充 忘了假設這前題反正他題目要儘量優化 這樣假設應該ok
那我直接假設用adjacency matrix存然後跑for i = 1 to |v|If G(i,a)=1 and G(i,b)=1 then count++這樣好像更快？就O(v)
作者:
TWkobe (中華柯比)
2017-12-31 15:29:00可是你a,b兩個graph這樣只有scan一點吧
作者:
TWkobe (中華柯比)
2017-12-31 15:44:00我的意思是你用舉陣是二維 你給了i只有一維阿噢我誤會了 應該可以
用matrix跟你一樣 或是用adj list 但是點由大到小存在裡面應該也可以八 應該八@@
作者:
moneylon (bencool)
2016-01-02 10:48:00有大大能分享 用bfs的寫法嗎 小弟太菜了