→ zuchang: 我是覺得當線性 雖然E的確有可能到n^2 但頂多走一次而已 01/23 18:54
→ Moderator: 好 謝謝 01/23 22:05
想請問關於這題的(b)小題的(1)
大家公認好像答案都是BFS
我的疑惑是當問題是問要linear time演算法
BFS的O(V+E)可以直接被當成linear嗎?
畢竟b小題沒提到有多少road(edge)存在
a小題更是假設為complete graph
謝謝
※ 引述《me1996017 (DotYo)》之銘言：
: 想請問一下這題的b小題, 題目寫說不知道edge的方向,
: 那要怎麼去確認這條edge我到底能不能走...
: https://imgur.com/3bLm9Ik.jpg
: 如果知道的話第一小題應該只是BFS
: 第二小題隨便帶一個Shortest-path演算法應該就行了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.28.142 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579776392.A.515.html