最大团问题分支限界伪代码

以下是最大团问题分支限界算法的伪代码：

maxClique(G):
    bestClique = []
    clique = []
    nodes = G.nodes()
    sortedNodes = sortNodesByDegree(nodes, G)
    expandCliques(clique, sortedNodes, G, bestClique)
    return bestClique

expandCliques(clique, sortedNodes, G, bestClique):
    if no nodes left to add:
        if len(clique) > len(bestClique):
            bestClique = clique
        return
    if len(clique) + len(sortedNodes) <= len(bestClique):
        return
    node = sortedNodes.pop(0)
    expandCliques(clique + [node], getNextNodes(node, sortedNodes, G), G, bestClique)
    expandCliques(clique, sortedNodes, G, bestClique)

getNextNodes(node, sortedNodes, G):
    return [n for n in sortedNodes if G.has_edge(node, n)]

sortNodesByDegree(nodes, G):
    return sorted(nodes, key=lambda x: G.degree[x], reverse=True)

其中，`maxClique` 函数接收一个无向图 `G` 作为输入，返回最大团。该函数首先初始化 `bestClique` 和 `clique` 两个空列表，分别代表当前最优解和当前搜索路径中的节点。然后，按照节点度数从大到小排序，调用 `expandCliques` 函数进行搜索，并返回 `bestClique`。

`expandCliques` 函数接收当前搜索路径中的节点列表 `clique`、按度数排序后的节点列表 `sortedNodes`、无向图 `G` 和当前最优解 `bestClique`。如果当前节点列表中已经没有可以添加的节点，则判断是否是最优解，并返回。如果添加当前节点后的团大小不足以超过当前最优解，则剪枝。否则，将当前节点添加到搜索路径中，更新 `sortedNodes` 列表，继续搜索。然后，回溯到上一层搜索。

`getNextNodes` 函数接收当前节点和按度数排序后的节点列表 `sortedNodes`、无向图 `G`，返回与当前节点相邻且尚未添加到搜索路径中的节点。

`sortNodesByDegree` 函数按照节点度数从大到小排序，并返回排序后的节点列表。