python3回溯找最大团

最近学习图论的一串小结之三

数学概念见上上篇：最大完全子图和极大连通子图

最大团问题分析可以移步这篇博文：回溯、图论——最大团问题（求最大完全子图）

代码一部分参考了这篇博文：最大团问题

本篇博文的问题描述：对于无向图graph，循环删除最大团所包含的节点和边，直到剩余各节点独立

图graph

主函数：

if __name__ == '__main__':global v, e, graph  # nodes为顶点数，edges为边数，graph为邻接矩阵global cn, bestn  # cn当前团的顶点数，bestn最大团的顶点数global corder, bestorder  # corder已选的顶点集，bestorder最大团的顶点集global ori_nodes, delnodes # ori_nodes原始节点列表，delnodes被删除的节点列表global nodes, r_nodesori_nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']delnodes = []nodes = {}for i, item in enumerate(ori_nodes):nodes[item] = iedges = [['a', 'b', 1], ['a', 'e', 1], ['a', 'd', 1], ['b', 'a', 1], ['b', 'd', 1], ['b', 'e', 1],['e', 'a', 1], ['e', 'b', 1], ['e', 'd', 1], ['d', 'a', 1], ['d', 'b', 1], ['d', 'e', 1],['c', 'f', 1], ['c', 'g', 1], ['f', 'c', 1], ['f', 'g', 1], ['g', 'c', 1], ['g', 'f', 1],['c', 'e', 1], ['h', 'i', 1], ['i', 'h' ,1]]bestorder = [0 for i in range(len(ori_nodes))]while(len(bestorder)>2):load_data(edges)backtrack(0)delnodes = delnodes + bestorder.copy()print('maximum clique:',bestorder)edges = del_clique(edges)print('delete nodes:',delnodes)print('remain nodes:',ori_nodes)

核心回溯找最大团

def backtrack(cur):global v, cn, bestn, corder, bestorder, r_nodesif (cur > v):#最后一个点纳入计算if (cn > bestn):bestn = cnfor i in range(v + 1):if corder[i] != 0:bestorder.append(r_nodes[i])returnif (istuan(cur)):#点i与装入的节点满足构成完全图cn += 1#个数加1corder[cur] = 1#标记1backtrack(cur + 1)#向下递推cn -= 1#向上回溯corder[cur] = 0# 回溯到iif ((cn + v - cur) > bestn):  # 界限条件，进入右子树，不能加入团backtrack(cur + 1)def istuan(cur):global corder, graphfor i in range(cur):if ((corder[i] == 1) and (graph[i][cur] == 0)):return 0return 1

删除最大团

#删除最大团
def del_clique(edges):global bestorder, ori_nodes, nodes, r_nodesfor item in bestorder:ori_nodes.remove(item)nodes = {}for i, item in enumerate(ori_nodes):nodes[item] = ir_nodes = {i: k for k, i in nodes.items()}newedges = []for line in edges:if line[0] not in bestorder and line[1] not in bestorder:newedges.append(line)return newedges

刷新全局变量

def load_data(edges):global v, e, graphglobal cn, bestnglobal corder, bestorderglobal nodes, r_nodesr_nodes = {i: k for k, i in nodes.items()}v = len(nodes)e = len(edges)graph = [[0 for i in range(v + 1)] for i in range(v + 1)]cn = 0bestn = 0corder = [0 for i in range(v + 1)]bestorder = []for line in edges:graph[nodes[line[0]]][nodes[line[1]]] = 1graph[nodes[line[1]]][nodes[line[0]]] = 1return

运行结果