algorithm - 找到图中度数小于其邻居的所有顶点

Question

我正在尝试编写一种算法，该算法将找到图中度数小于其邻居的所有顶点的集合。我最初的方法是找到每个顶点的度数，然后遍历列表，将每个顶点的度数与其邻居的度数进行比较。不幸的是，这看起来可能非常耗时。有没有更有效的方法来找到这个集合？

Answer 1

一个评论 - 如果你正在使用无向图(谢谢，Brian R. Bondy)，一旦你确定一个顶点的度数小于它所有邻居的度数，你就不会不需要检查邻居，因为他们都不会拥有该属性(property)。考虑使用这些知识来帮助您解决问题并加快速度。