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

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. 有一个很重要的错误：set 没有被复制。通常情况下，这没问题，但在这里就不行。让我们看看你的代码。在计算 without_i 后，原来的 set 值可能会被修改。在这种情况下，计算 with_i 时使用的就是错误的 set 值。我能想到的最简单的例子是 tab = [[0,1,0],[1,0,0],[1,0,0]]。

2. 一些小错误：flag 没有被使用？而且 numcalls 似乎是为了简化调试而创建的。所以我在我的代码示例中把它排除了。

3. 我觉得你的函数接口不太方便。用户需要自己创建一个 set 变量，并手动指定问题的大小。所以在我的代码示例中，我把原来的函数封装成了一个我想要使用的接口。实际上，你可以进一步探索邻接声明的方式。例如，邻接列表可能比矩阵更方便。

我的代码示例：

def maxset( tab ):
    def maxset_detail(tab, i, set):
        if any( tab[i][s] for s in set ):
            return i and maxset_detail(tab, i-1, set) or 0
        if (i == 0):
            set.append(i)
            return len(set)
        set_copy = set[:] + [i]
        without_i = maxset_detail(tab, i-1, set)
        with_i = maxset_detail(tab, i-1, set_copy)
        if ( with_i > without_i ):
            set[:] = set_copy
            return with_i
        else:
            return without_i
    set = []
    maxset_detail(tab, len(tab)-1, set )
    return set

Answer 2

有一个大家都知道的简单算法可以解决这个问题：

1. 一开始，把所有的点都涂成绿色。
2. 找到一个绿色的点，把它的邻居涂成红色。
3. 对于每一个红色的点，把它的绿色邻居也涂成红色。（这就是递归的部分）
4. 当没有红色的点有绿色邻居时，这些红色的点就形成了一个最大连通的部分。
5. 从第2步开始重复，直到所有的点都变成红色，所有的部分都被找到。

现在你知道所有的部分了，可以选择那个点最多的部分（也就是最大的连通子图）。