1.問題描述

最大團問題是圖論中一個經典的組合優化問題，也是一類NP完全問題。在Wikipedia中Clique Problem的描述如下：
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected. 其實說白了，最大團問題就是找出圖中的最大完全子圖。

而在解決最大團問題時使用最廣的算法是Bron-Kerbosch算法。

2.Bron-Kerbosch

在Wikipedia中有關于Bron-Kerbosch算法的詳細描述。Bron-Kerbosch算法是一種遞歸回溯算法，同時也是圖論中一個較難理解的算法（在下一小節會介紹一種基于Bron-Kerbosch的較簡單算法）。另外，該算法有兩種形式：一種是不選擇中心點的，一種是選擇中心點的。
輸入文件的內容如下：

1 4 4 0 1 0 2 1 2 2 3

2.1Without Pivot

對于without pivot形式的，偽代碼如下：

Bron-Kerbosch without Pivot (Pseudo Code) P = {V} //set of all vertices in Graph G R = {} X= {}proc BronKerbosch(P, R, X)if P ∪ X = {} thenprint set R as a maximal clique end iffor each vertex v in P doBronKerbosch(P ∩ {v}, R ∪ {V} , X \{v}) P = P \ {v} X = X ∪ {v}end for
Java代碼：

public class MaximalCliquesWithoutPivot {int nodesCount; ArrayList<Vertex> graph = new ArrayList<Vertex>(); class Vertex implements Comparable<Vertex> {int x; int degree; ArrayList<Vertex> nbrs = new ArrayList<Vertex>(); public int getX() {return x; } public void setX(int x) {this.x = x; } public int getDegree() {return degree; } public void setDegree(int degree) {this.degree = degree; } public ArrayList<Vertex> getNbrs() { return nbrs; } public void setNbrs(ArrayList<Vertex> nbrs) {this.nbrs = nbrs; } public void addNbr(Vertex y) {this.nbrs.add(y); if (!y.getNbrs().contains(y)) { y.getNbrs().add(this); y.degree++; } this.degree++; } public void removeNbr(Vertex y) {this.nbrs.remove(y); if (y.getNbrs().contains(y)) { y.getNbrs().remove(this); y.degree--; } this.degree--; } @Override public int compareTo(Vertex o) {if (this.degree < o.degree) {return -1; } if (this.degree > o.degree) {return 1;} return 0; } } void initGraph() { graph.clear(); for (int i = 0; i < nodesCount; i++) {Vertex V = new Vertex(); V.setX(i); graph.add(V); } } int readTotalGraphCount(BufferedReader bufReader) throws Exception {return Integer.parseInt(bufReader.readLine()); } // Reads Input void readNextGraph(BufferedReader bufReader) throws Exception {try { nodesCount = Integer.parseInt(bufReader.readLine()); int edgesCount = Integer.parseInt(bufReader.readLine());initGraph(); for (int k = 0; k < edgesCount; k++) {String[] strArr = bufReader.readLine().split(" "); int u = Integer.parseInt(strArr[0]);int v = Integer.parseInt(strArr[1]);Vertex vertU = graph.get(u); Vertex vertV = graph.get(v); vertU.addNbr(vertV); } } catch (Exception e) { e.printStackTrace(); throw e; } } // Finds nbr of vertex i ArrayList<Vertex> getNbrs(Vertex v) { int i = v.getX(); return graph.get(i).nbrs; } // Intersection of two sets ArrayList<Vertex> intersect(ArrayList<Vertex> arlFirst, ArrayList<Vertex> arlSecond) { ArrayList<Vertex> arlHold = new ArrayList<Vertex>(arlFirst); arlHold.retainAll(arlSecond); return arlHold; } // Union of two sets ArrayList<Vertex> union(ArrayList<Vertex> arlFirst, ArrayList<Vertex> arlSecond) { ArrayList<Vertex> arlHold = new ArrayList<Vertex>(arlFirst); arlHold.addAll(arlSecond); return arlHold; } // Removes the neigbours ArrayList<Vertex> removeNbrs(ArrayList<Vertex> arlFirst, Vertex v) { ArrayList<Vertex> arlHold = new ArrayList<Vertex>(arlFirst); arlHold.removeAll(v.getNbrs()); return arlHold; } // Version without a Pivot void Bron_KerboschWithoutPivot(ArrayList<Vertex> R, ArrayList<Vertex> P,ArrayList<Vertex> X, String pre) { System.out.print(pre + " " + printSet(R) + ", " + printSet(P) + ", " + printSet(X)); if ((P.size() == 0) && (X.size() == 0)) {printClique(R); return; } System.out.println(); ArrayList<Vertex> P1 = new ArrayList<Vertex>(P); for (Vertex v : P) { R.add(v); Bron_KerboschWithoutPivot(R, intersect(P1, getNbrs(v)), intersect(X, getNbrs(v)), pre + "\t"); R.remove(v); P1.remove(v); X.add(v); } } void Bron_KerboschPivotExecute() { ArrayList<Vertex> X = new ArrayList<Vertex>(); ArrayList<Vertex> R = new ArrayList<Vertex>(); ArrayList<Vertex> P = new ArrayList<Vertex>(graph); Bron_KerboschWithoutPivot(R, P, X, ""); } void printClique(ArrayList<Vertex> R) { System.out.print(" -------------- Maximal Clique : "); for (Vertex v : R) { System.out.print(" " + (v.getX())); } System.out.println(); } String printSet(ArrayList<Vertex> Y) { StringBuilder strBuild = new StringBuilder(); strBuild.append("{"); for (Vertex v : Y) { strBuild.append("" + (v.getX()) + ","); } if (strBuild.length() != 1) {strBuild.setLength(strBuild.length() - 1); } strBuild.append("}"); return strBuild.toString(); } public static void main(String[] args) {BufferedReader bufReader = null; if (args.length > 0) {// Unit Test Mode bufReader = new BufferedReader(new StringReader("1\n4\n4\n0 1\n0 2\n1 2\n1 3\n")); } else { File file = new File("F:\\Codes\\JavaEE\\tmp\\data\\data.txt"); try { bufReader = new BufferedReader(new FileReader(file));} catch (Exception e) { e.printStackTrace(); return; } } MaximalCliquesWithoutPivot ff = new MaximalCliquesWithoutPivot();System.out.println("Max Cliques Without Pivot"); try { int totalGraphs = ff.readTotalGraphCount(bufReader);for (int i = 0; i < totalGraphs; i++) {System.out.println("************** Start Graph " + (i + 1) + "******************************");ff.readNextGraph(bufReader); ff.Bron_KerboschPivotExecute(); } } catch (Exception e) { e.printStackTrace(); System.err.println("Exiting : " + e); } finally { try { bufReader.close(); } catch (Exception f) { } } } }

2.2With Pivot

對于With Pivot形式，偽代碼如下：
Bron-Kerbosch with Pivot (Pseudo Code) P = {V} //set of all vertices in Graph G R = {} X= {}proc BronKerbosch(P, R, X)if P ∪ X = {} thenprint set R as a maximal clique end ifChoose a pivot u from set P U Xfor each vertex v in P \nbrs(u) doBronKerbosch(P ∩{v}, R ∪ {V} , X \{v}) P = P \ {v} X = X ∪ {v}end for
Java代碼：

public class MaximalCliquesWithPivot {int nodesCount; ArrayList<Vertex> graph = new ArrayList<Vertex>(); class Vertex implements Comparable<Vertex> {int x; int degree; ArrayList<Vertex> nbrs = new ArrayList<Vertex>(); public int getX() {return x; } public void setX(int x) {this.x = x; } public int getDegree() {return degree; } public void setDegree(int degree) {this.degree = degree; } public ArrayList<Vertex> getNbrs() { return nbrs; } public void setNbrs(ArrayList<Vertex> nbrs) {this.nbrs = nbrs; } public void addNbr(Vertex y) {this.nbrs.add(y); if (!y.getNbrs().contains(y)) { y.getNbrs().add(this); y.degree++; } this.degree++; } public void removeNbr(Vertex y) {this.nbrs.remove(y); if (y.getNbrs().contains(y)) { y.getNbrs().remove(this); y.degree--; } this.degree--; } @Override public int compareTo(Vertex o) {if (this.degree < o.degree) {return -1; } if (this.degree > o.degree) {return 1;} return 0; } public String toString() { return "" + x; } } void initGraph() { graph.clear(); for (int i = 0; i < nodesCount; i++) {Vertex V = new Vertex(); V.setX(i); graph.add(V); } } int readTotalGraphCount(BufferedReader bufReader) throws Exception {return Integer.parseInt(bufReader.readLine()); } // Reads Input void readNextGraph(BufferedReader bufReader) throws Exception {try { nodesCount = Integer.parseInt(bufReader.readLine()); int edgesCount = Integer.parseInt(bufReader.readLine());initGraph(); for (int k = 0; k < edgesCount; k++) {String[] strArr = bufReader.readLine().split(" "); int u = Integer.parseInt(strArr[0]);int v = Integer.parseInt(strArr[1]);Vertex vertU = graph.get(u); Vertex vertV = graph.get(v); vertU.addNbr(vertV); } } catch (Exception e) { e.printStackTrace(); throw e; } } // Finds nbrs of vertex i ArrayList<Vertex> getNbrs(Vertex v) { int i = v.getX(); return graph.get(i).nbrs; } // Intersection of two sets ArrayList<Vertex> intersect(ArrayList<Vertex> arlFirst, ArrayList<Vertex> arlSecond) { ArrayList<Vertex> arlHold = new ArrayList<Vertex>(arlFirst); arlHold.retainAll(arlSecond); return arlHold; } // Union of two sets ArrayList<Vertex> union(ArrayList<Vertex> arlFirst, ArrayList<Vertex> arlSecond) { ArrayList<Vertex> arlHold = new ArrayList<Vertex>(arlFirst); arlHold.addAll(arlSecond); return arlHold; } // Removes the neigbours ArrayList<Vertex> removeNbrs(ArrayList<Vertex> arlFirst, Vertex v) { ArrayList<Vertex> arlHold = new ArrayList<Vertex>(arlFirst); arlHold.removeAll(v.getNbrs()); return arlHold; } // Version with a Pivot void Bron_KerboschWithPivot(ArrayList<Vertex> R, ArrayList<Vertex> P,ArrayList<Vertex> X, String pre) { System.out.print(pre + " " + printSet(R) + ", " + printSet(P) + ", " + printSet(X)); if ((P.size() == 0) && (X.size() == 0)) {printClique(R); return; } System.out.println(); ArrayList<Vertex> P1 = new ArrayList<Vertex>(P); // Find Pivot Vertex u = getMaxDegreeVertex(union(P, X)); System.out.println("" + pre + " Pivot is " + (u.x)); // P = P / Nbrs(u) P = removeNbrs(P, u); for (Vertex v : P) { R.add(v); Bron_KerboschWithPivot(R, intersect(P1, getNbrs(v)), intersect(X, getNbrs(v)), pre + "\t"); R.remove(v); P1.remove(v); X.add(v); } } Vertex getMaxDegreeVertex(ArrayList<Vertex> g) { Collections.sort(g); return g.get(g.size() - 1);} void Bron_KerboschPivotExecute() { ArrayList<Vertex> X = new ArrayList<Vertex>(); ArrayList<Vertex> R = new ArrayList<Vertex>(); ArrayList<Vertex> P = new ArrayList<Vertex>(graph); Bron_KerboschWithPivot(R, P, X, ""); } void printClique(ArrayList<Vertex> R) { System.out.print(" --- Maximal Clique : "); for (Vertex v : R) { System.out.print(" " + (v.getX())); } System.out.println(); } String printSet(ArrayList<Vertex> Y) { StringBuilder strBuild = new StringBuilder(); strBuild.append("{"); for (Vertex v : Y) { strBuild.append("" + (v.getX()) + ","); } if (strBuild.length() != 1) {strBuild.setLength(strBuild.length() - 1); } strBuild.append("}"); return strBuild.toString(); } public static void main(String[] args) {BufferedReader bufReader = null; if (args.length > 0) {// Unit Test Mode bufReader = new BufferedReader(new StringReader("1\n5\n7\n0 1\n0 2\n0 3\n0 4\n1 2\n2 3\n3 4\n")); } else { File file = new File("F:\\Codes\\JavaEE\\tmp\\data\\data.txt"); try { bufReader = new BufferedReader(new FileReader(file));} catch (Exception e) { e.printStackTrace(); return; } } MaximalCliquesWithPivot ff = new MaximalCliquesWithPivot();try { int totalGraphs = ff.readTotalGraphCount(bufReader);System.out.println("Max Cliques with Pivot"); for (int i = 0; i < totalGraphs; i++) {System.out.println("************** Start Graph " + (i + 1) + "******************************");ff.readNextGraph(bufReader); ff.Bron_KerboschPivotExecute(); } } catch (Exception e) { e.printStackTrace(); System.err.println("Exiting : " + e); } finally { try { bufReader.close(); } catch (Exception f) { } } } }

3.MC

這種MC算法的思想還是從Born-Kerbosch借鑒過來的。在MC算法中，我們使用兩個集合P、C。其中，P包含圖中所有的點，C是圖中的團（Clique）。算法思路這樣的：1.對圖中的每個點s，找出其所有鄰結點，①然后從鄰結點集合中選擇一個點v，②再找出既屬于鄰結點集合，又是點v的鄰接點，這樣產生一個新的鄰結點集合，③接著對新鄰結點集合做上述①②操作，直到每個點s的鄰結點集合訪問完，就找出以該點為Pivot的最大團；2.比較所有團，而其中最大的那個團，即為全圖的最大團。
偽代碼如下：

A：鄰接矩陣 P：所有點 C：最大團 maxSize：最大團的大小 newP：pivot v的鄰結點集合proc expand(C, P)for each vertex v in P.reverseif P.size + C.size <= maxSizereturnchoose vC.add(v)newPfor each vertex u in Pif A[v][u] == 1newP.add(w)if(newP.isEmpty && C.size > maxSize)return Cif(!newP.isEmpty)expand(C, newP)C.remove(v)P.remove(v)
Java代碼：

import java.util.ArrayList; import java.util.Arrays;public class MC {private int[][] A;private int n;private int maxSize;private int[] solution;public MC(int n, int[][] A) {// TODO Auto-generated constructor stubthis.n = n;this.A = A;maxSize = 0;solution = new int[n];}public void search(){ArrayList<Integer> C = new ArrayList<Integer>();ArrayList<Integer> P = new ArrayList<Integer>(n);for(int i = 0; i < n; i++){P.add(i);}expand(C, P);}public void expand(ArrayList<Integer> C, ArrayList<Integer> P){for(int i = P.size() - 1; i >= 0; i--){if(C.size() + P.size() <= maxSize){return;}int v = P.get(i);C.add(v);ArrayList<Integer> newP = new ArrayList<Integer>();for(int w : P){if(A[v][w] == 1){newP.add(w);}}if(newP.isEmpty() && C.size() > maxSize){saveSolution(C);}if(!newP.isEmpty()){expand(C, newP);}C.remove((Integer)v);P.remove((Integer)v);}}public void saveSolution(ArrayList<Integer> C){Arrays.fill(solution, 0);for(int i : C){solution[i] = 1;}maxSize = C.size();}public static void main(String[] args) {// TODO Auto-generated method int[][] A= {{0, 1, 1, 1, 1, 0},{1, 0, 1, 1, 1, 1},{1, 1, 0, 1, 1, 1},{1, 1, 1, 0, 1, 1},{1, 1, 1, 1, 0, 0},{0, 1, 1, 1, 0, 0}};int n = 6;MC mc = new MC(n, A);mc.search();for(int i : mc.solution){System.out.print(i + " ");}}}

總結

以上是生活随笔為你收集整理的最大团算法（Maximum Clique）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。