假设你正在寻找，你必须要查看所有的边缘，所以我们有一个 lower bound 的Ω（| E |）算法 . 找到每个顶点的度数需要时间O（| E |）（因为你只看一次每个边缘;另一个证明是使用Σd（v）= 2 | E |的事实） . 比较每个顶点与其所有邻居的程度也只需要O（| E |）时间（同样，对于每个边，只进行一次比较） . 这意味着您的算法在O（| E |）时间内运行（大约2 | E | "steps"，但CPU指令的精确数量取决于您的实现），这符合下限 . 因此，在最坏的情况下，你的"brute-force"算法基本上（达到一个很小的常数） as fast as possible ，因此不值得进一步优化 .
一条评论 - 如果您正在使用无向图（谢谢，Brian R. Bondy），一旦您需要检查邻居，因为它们都不具备该属性 . 考虑使用这些知识来帮助你加快速度 .
2
我想象一个无向图的贪婪方法如下：
let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
let minDeg be the minimum degree of all v's neighbors
if degree(v) < minDeg
add v to Q*
remove all neighbors of v from Q
remove v from Q
set v = new arbitrary node, v in Q
else
remove v from Q
set v = v's neighbor in Q of minimum degree
3 回答
也许“看起来这可能非常耗时”，但有更好的方法可以找到:-)
假设你正在寻找，你必须要查看所有的边缘，所以我们有一个 lower bound 的Ω（| E |）算法 . 找到每个顶点的度数需要时间O（| E |）（因为你只看一次每个边缘;另一个证明是使用Σd（v）= 2 | E |的事实） . 比较每个顶点与其所有邻居的程度也只需要O（| E |）时间（同样，对于每个边，只进行一次比较） . 这意味着您的算法在O（| E |）时间内运行（大约2 | E | "steps"，但CPU指令的精确数量取决于您的实现），这符合下限 . 因此，在最坏的情况下，你的"brute-force"算法基本上（达到一个很小的常数） as fast as possible ，因此不值得进一步优化 .
如果您正在为实际应用程序执行此操作，并且确实发现您的算法花费了太多时间，那么请使用分析器来查找要优化的部分 . 优化算法的第二阶段至关重要，这一点并不明显 .
一条评论 - 如果您正在使用无向图（谢谢，Brian R. Bondy），一旦您需要检查邻居，因为它们都不具备该属性 . 考虑使用这些知识来帮助你加快速度 .
我想象一个无向图的贪婪方法如下：
该算法可能稍微更有效，因为在每次迭代时，它要么找到满意的节点，要么检查较低程度的新节点并从图中移除节点 .
在最坏的情况下，它将等同于您的强力算法 . 不过，平均而言，我认为应该表现得更好 .