[理工] [資結] 98 政大

[stevenwin (袋哥)]

8. Which of the following is FALSE concerning a graph with v vertices

   and e edges?

   (B) There exist algorithms in which finding the shortest path from the

       source to another vertex is any faster (by more than a constant factor)

       than finding the shortest paths from the source to all the other

       vertices

   (D) It is possible to depth first traversal a graph in linear time


   我用刪去法大概知道(B)是錯的,不知道為什麼?

   (D)是對的，因為用adajacency list表示是O(V+E)嗎?

PART III

2.(1)  洪x解答的array[13]應該是75，不是空的吧?


感謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.63.154
推 assassin88:8.答案是C？
→ stevenwin:答案是B  C是對的
推 assassin88:喔喔~請問b錯在哪邊呢
→ stevenwin:這就是我的問題啦
推 pigbo:我是覺得可能不管是哪一個都必須把所有邊走過一遍 所以沒有
→ pigbo:所以比較快   我也不知道這樣說對不對 有錯請指教
推 wassili:我也覺得是出在"比較快"<=頂多一樣快而已...
推 abc73021:嚴格講的話dijkstra 會在找到點後停止
→ abc73021:可能沒有強調在沒有nagetive edge下吧  若是negative edg
→ abc73021:應該就相同速度了吧
推 strangehead:我想問題出在any那個字。       AVL Tree那題的確少75
推 FRAXIS:針對b 應該是現在不存在.. 還是說有證明是不可能？
推 zeowo:標題錯誤
※ 編輯: stevenwin       來自: 219.85.159.52        (03/06 16:49)