test.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"

void CalClique(int i)
{// 计算最大完备子图的回溯代码
	int j,OK = 1;
	if (i > n) {// 在叶子上
		// 找到一个更大的完备子图，更新
		for (int j = 1; j <= n; j++)
			bestx[j] = x[j];
		bestn = cn;
		return ; 
	}
	// 在当前完备子图中检查顶点i是否与其它顶点相连
	for (j = 1; j < i; j++)
		if (x[j] && a[i][j] == NoEdge) {
			// i 不与j 相连
			OK = 0;
			break ; 
		}
	if (OK) {// 尝试x[i] = 1
		x[i] = 1; // 把i 加入完备子图
		cn++;
		CalClique( i + 1 ) ;
		x[i] = 0;
		cn--; 
	}
	if(cn + n - i >bestn) 
	{// 尝试x[i] = 0
		x[i] = 0;
		CalClique( i + 1 ); 
	}
}
int AdjacencyGraph::MaxClique(int v[])
{// 返回最大完备子图的大小
// 完备子图的顶点放入v [ 1 : n ]
// 初始化
	int	x[n+1];
	cn = 0;
	bestn = 0;
	bestx = v;
	// 寻找最大完备子图
	CalClique(1) ;
	return bestn;
}