作者Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)
看板Grad-ProbAsk
标题Re: [理工] 台大107资演 图论题
时间Thu Jan 23 18:46:29 2020
想请问关於这题的(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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579776392.A.515.html
1F：→ zuchang: 我是觉得当线性 虽然E的确有可能到n^2 但顶多走一次而已 01/23 18:54
2F：→ Moderator: 好 谢谢 01/23 22:05