在無向圖中查詢大小為 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 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

立即開始
廣告