c++ - 图中最大独立集的递归程序

Question

我在为上述问题编写程序时遇到困难..我有下图....

A-----B------C       D
A is connected to B
B is connected to C
D is connected with no body!! 
The maximum Independent set in this is {A,C, D}... 

该图的邻接矩阵如下:-

为了解决这个问题，我画了以下决策树:-

• 每个节点的第一个元素是索引。

• 每个节点的第二个元素是存储图中独立元素的集合。

• 左分支表示我不会考虑该元素，右分支表示我将考虑节点的第一个元素指定的索引处的元素。

所以你可以清楚地看到，在每个节点上，我没有考虑该节点的第一个元素索引指定的元素，而是考虑了该元素是否可以插入到独立集中。

我想用Python为此编写一个程序!我是一个新手，还处于通过递归实现该程序的早期阶段。

请帮忙!!

我写了以下代码:-但它对我来说看起来不太好..它以某种方式工作..请经验人们可以发表您的评论..我仍在递归学习..

def maxset(tab, i, set):
    global numcalls
    numcalls += 1
    if i == 0:
        flag = 0
        for s in set:
            if tab[i][s]:
                return 0
        if i not in set:
            set.append(i)
        return len(set)

    without_i = maxset(tab, i-1, set)

    flag = 0
    for s in set:
        if tab[i][s]:
            return without_i
    if i not in set:
        set.append(i)
    with_i = maxset(tab,i-1,set)
    return max(without_i, with_i)


tab = [[0,1,0,0],[1,0,1,0],[0,1,0,0],[0,0,0,0]]
#tab = [[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]
set = []
numVertIndex = 3 #### 0,1,2,3
numcalls = 0
print(maxset(tab, numVertIndex, set))
print(set)
print (numcalls)

Answer 1

有一个众所周知且简单的算法可以解决这个问题:

1. 最初将所有顶点着色为绿色。
2. 找到一个绿色顶点。将它的邻居涂成红色。
3. 对于每个红色顶点，将其绿色邻居着色为红色。 (这里是递归部分)
4. 当不再有具有绿色邻居的红色顶点时，红色顶点集确定最大连通分量。
5. 从 2 开始重复，直到所有顶点都变成红色并且发现所有组件。

现在您已经了解了所有组件，您可以选择具有最多顶点的组件(即最高阶最大连通子图)。