骨骼电面1题

jtzgz 发表于 2020-6-10 03:36
谢谢谢谢。虽然没看太明白。

vertex cover problem https://www.geeksforgeeks.org/ve ... ximate-algorithm-2/

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

LZ请问你的问题是要点亮所有path还是点亮所有room？如果是点亮所有path的话是mimum vertex cover问题，如果是点亮所有room的话就不是了

ddcfv 发表于 2020-6-10 13:02
vertex cover 是cover 所有edge，不知道LZ的问题是要cover所有edge还是所有vertex

对 我其实是觉得这题跟vertex cover不一样。

话说，两个 room 之间只有一条 path 就是 tree 吧。

需要证明吗

ddcfv 发表于 2020-6-10 13:02
vertex cover 是cover 所有edge，不知道LZ的问题是要cover所有edge还是所有vertex

感觉，cover了所有的edge，就等于vertex吧

ddcfv 发表于 2020-6-10 13:03
LZ请问你的问题是要点亮所有path还是点亮所有room？如果是点亮所有path的话是mimum vertex cover问题，如果 ...

room。但是，path也类似。一个room点亮，他的neighbor room也一样点亮。

vinf 发表于 2020-6-10 13:57
话说，两个 room 之间只有一条 path 就是 tree 吧。

也可以这样想呢。 对的。 就是如何把neighbor结构，先parse成tree结构。

EllenWang 发表于 2020-6-10 14:44
需要证明吗

不需要。