資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告