在无向图中查找所有大小为 K 的团
data structurec++programming
在无向图中查找所有特定大小的团是一个基本图论问题，在社交网络研究、生物学和数据挖掘中有许多应用。团是所有顶点都链接在一起的图子集。递归回溯将每个顶点视为潜在候选者，并根据邻域连接更新候选集和排除集。回溯可以快速找到所有适当大小的团。
使用的方法
回溯方法
回溯
递归回溯是在无向图中查找特定大小团的常用方法。它在提供的约束下验证团的所有可能的顶点组合。该方法将每个顶点视为空团中的候选者。它迭代地将顶点添加到团块中，并根据邻域连接更新候选集和排除集。没有候选集或消除的顶点将结束算法。回溯有效地在解决方案空间中搜索指定大小的团块。
算法
使用三个参数创建递归函数：初始节点、当前节点的长度和目标节点的长度。
不能在起始索引以下添加节点。它最多循环 n 次。
如果添加节点会保留团块。如果是，则添加节点，并使用参数当前集合的长度 + 1、所需长度和新节点的索引 + 1 运行递归函数。
达到长度后，将打印节点。
示例
// 该方法的 C++ 实现
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// 存储顶点
int store[MAX], n;
// 图形
int graph[MAX][MAX];
// 顶点的度数
int d[MAX];
// 用于检查给定的顶点集
// 是否为团的函数
bool is_clique(int b)
{
// 对所有边集运行循环
// 针对选定顶点
for (int i = 1; i < b; i++) {
for (int j = i + 1; j < b; j++)
// 如果任何边缘缺失
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// 打印团的函数
void print(int n)
{
for (int i = 1; i < n; i++)
cout << store[i] << " ";
cout << ", ";
}
// 查找所有大小为 s 的团的函数
void findCliques(int i, int l, int s)
{
// 检查是否可以插入来自 i+1 的任何顶点
for (int j = i + 1; j <= n - (s - l); j++)
// 如果图的度足够
if (d[j] >= s - 1) {
// 将顶点添加到存储
store[l] = j;
// 如果图不是大小为 k 的团
// 那么它就不能成为团
// 通过添加另一条边
if (is_clique(l + 1))
// 如果团的长度
// 仍然小于所需大小
if (l < s)
// 递归添加顶点
findCliques(j, l + 1, s);
// 尺寸符合要求
else
print(l + 1);
}
}
// 驱动代码
int main()
{
int edges[][2] = { { 1, 2 },
{ 2, 3 },
{ 3, 1 },
{ 4, 3 },
{ 4, 5 },
{ 5, 3 } },
k = 3;
int size = sizeof(edges) / sizeof(edges[0]);
n = 5;
for (int i = 0; i < size; i++) {
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
findCliques(0, 1, k);
return 0;
}
输出
1 2 3 , 3 4 5
结论
在无向网络中寻找所有特定大小的团是一个难题，可以通过多种方式解决，包括递归回溯技术和 Bron-Kerbosch 算法。每种方法都有其独特的优势来解决手头的问题。递归回溯方法考虑了所有可能的连接顶点集，提供了一个简单易懂的答案。它最适合较小的图或所需团大小适中的情况，因为它可以有效利用回溯来缩小搜索空间。
