基于稀疏二分图的极大二分团并行枚举方法

1.一种基于稀疏二分图的极大二分团并行枚举方法，其特征在于，所述稀疏二分图包括由用户与购买物品所组成的二分图G，所述方法包括：步骤一、初始化所述二分图G对应的任务栈St与计算参数，所述计算参数包括候选集P、验证集Q、所述二分图G对应二分团的右部R与左部L；所述初始化所述二分图G对应的任务栈St与计算参数之前，还包括：对候选集P中每一节点增加一标志位，构成二元组(v,bit)，v表示节点，bit表示标志位，在bit＝1时，表示节点v可被访问；否则，表示节点v不被访问；步骤二、在线程t内遍历候选集P，所述候选集P包括若干个节点；步骤三、从所述任务栈St的栈顶获取任务x；步骤四、基于所述任务x、所述二分图G及预置的存储区域Dt，确定当前任务所需要处理的节点v，以及当前任务所需要的候选集P1、验证集Q1、所述二分图G对应二分团的右部R1与左部L1；步骤五、根据所述二分图G、节点v及所述左部L1，计算所述节点v在所述左部L1中的邻居L’；步骤六、判断所述节点v的flag属性是否为false，若为false，则返回执行步骤三；若为true，则继续执行步骤七；步骤七、遍历验证集Q1，生成孩子检测集Q’，并在搜索到的子任务中判断是否存在极大二分团，若不存在极大二分团，则返回执行步骤三，若存在极大二分团，则继续执行步骤八；步骤八、遍历候选集P1中的各个节点p，如果p在所述邻居L’中的邻居个数大于0，则将节点p加入候选集P1，生成新的候选集P’，并输出极大二分团<L’，R’>；其中，R’表示节点v在所述右部R1中的邻居；步骤九、判断候选集P’是否为空，若候选集P’为非空，则根据逆序遍历候选集P’，生成新任务加入任务栈St，再根据候选集P’、孩子检测集Q’、邻居L’、R’更新所述存储区域Dt，并返回执行步骤三；若候选集P’为空，则继续执行步骤十；步骤十、判断所述任务栈St是否为空，若所述任务栈St为空，则确定所述线程t执行结束。 2.如权利要求1所述的方法，其特征在于，所述初始化所述二分图G对应的任务栈St与计算参数的步骤，包括：基于所述二分图G的线程总数，对所述二分图G的各个线程进行取模操作，得到各个线程初始化后的任务栈与计算参数。 3.如权利要求1所述的方法，其特征在于，所述若所述任务栈St为空，则确定所述线程t执行结束的步骤，包括：若所述任务栈St为空，则通过预置的负载均衡装置请求新任务；当所述负载均衡装置未接收到响应消息时，确定所述线程t执行结束。 4.如权利要求3所述的方法，其特征在于，所述通过预置的负载均衡装置请求新任务的步骤之后，还包括：若所述负载均衡装置接收到响应消息，则返回执行步骤三。