数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在无向图中查找大小为 K 的所有团
在无向图中查找特定大小的所有团是一个基本的图论问题，在社交网络研究、生物学和数据挖掘中有着广泛的应用。团是指图的一个子集，其中所有顶点之间都相互连接。递归回溯法将每个顶点视为一个潜在的候选者，并根据邻域连接更新候选集和排除集。回溯法可以快速找到指定大小的所有团。
使用的方法
回溯法
回溯
递归回溯法是查找无向图中特定大小的团的常用方法。它在给定约束条件下验证所有可能的顶点组合，以查找团。该方法将每个顶点视为一个空团中的候选者。它迭代地将顶点添加到团中，并根据邻域连接更新候选集和排除集。当没有候选者或所有顶点都被排除时，算法结束。回溯法有效地搜索了指定大小的团的解空间。
算法
创建一个具有三个参数的递归函数：起始节点、当前节点长度和目标节点长度。
节点不能在起始索引以下添加。它循环最多 n 次。
如果添加节点可以保持团的性质。如果是，则添加该节点，并使用以下参数运行递归函数：当前集合长度 + 1、所需长度和新节点索引 + 1。
当达到所需长度时打印节点。
示例
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Stores the vertices
int store[MAX], n;
// Graph
int graph[MAX][MAX];
// Degree of the vertices
int d[MAX];
// Function to check if the given set of vertices
// in store array is a clique or not
bool is_clique(int b)
{
// Run a loop for all the set of edges
// for the select vertex
for (int i = 1; i < b; i++) {
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to print the clique
void print(int n)
{
for (int i = 1; i < n; i++)
cout << store[i] << " ";
cout << ", ";
}
// Function to find all the cliques of size s
void findCliques(int i, int l, int s)
{
// Check if any vertices from i+1 can be inserted
for (int j = i + 1; j <= n - (s - l); j++)
// If the degree of the graph is sufficient
if (d[j] >= s - 1) {
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k
// then it cannot be a clique
// by adding another edge
if (is_clique(l + 1))
// If the length of the clique is
// still less than the desired size
if (l < s)
// Recursion to add vertices
findCliques(j, l + 1, s);
// Size is met
else
print(l + 1);
}
}
// Driver code
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 算法。每种方法都具有一套独特的优势，可以用来解决手头的问题。递归回溯法通过考虑所有可能的连接顶点集，提供了一种简单易懂的解决方案。它最适合较小的图或所需团大小较小的情况，因为它有效地利用回溯来缩小搜索空间。
更新于: 2023年7月14日
269 次浏览
广告