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 开始重复，直到所有顶点都变成红色，并且发现所有组件。

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