姜老师：您好！我似乎发现了您的算法中的一点小问题。
以下是一个反例：
2--5
|
1--3--6
|
4--7
如图，1连接234,2连5,3连6,4连7，最小覆盖集是234，大小为3。然而根据您的算法，由于点1的“关联度”为3，比另外的点都要大，1会先被选中，然而之后无论如何都还需要再选择3个点才能满足要求，这样就不是最小覆盖集了。您的描述中提到了“连接单边的顶点优先”，但我不太明白。是指“关联度”相同的情况下优先选择“连接单边的顶点”吗？但如果是这样，我的反例还是有效的。
还有一个问题：如果有许多点的“关联度”相同怎么办呢？随机选一个点似乎是不可以的。但如果进行搜索，时间复杂度就会增加了。
希望您能解决这两个问题，并设计出更加有效的算法。

你提到的问题很好，我那里提到了“单边优先”，大概没说清楚。一定是和叶顶点相连的点优先。

你提到的问题很好，我那里提到了“单边优先”，大概没说清楚。一定是和叶顶点相连的点优先。

第2个问题也是可以的，要注意消去点边之后的单边。

为你回答详细点：http://blog.sciencenet.cn/blog-340399-1029435.html