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的写法吗 小弟太菜了