最大团算法（Maximum Clique）

快来打我* 2022-08-19 13:11 219阅读 0赞

# 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 = {} then
    	  print set R as a maximal clique
    end if
    
    for each vertex v in P do
    
    BronKerbosch(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 = {} then
    	  print set R as a maximal clique
    end if
    
    Choose a pivot u  from set P U X
    
    for each vertex v in P \nbrs(u) do
    
    BronKerbosch(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.reverse
    		if P.size + C.size <= maxSize
    			return
    		choose v
    		C.add(v)
    		newP
    		for each vertex u in P
    			if A[v][u] == 1
    				newP.add(w)
    		
    		if(newP.isEmpty && C.size > maxSize)
    			return C
    		
    		if(!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 stub
    		this.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 + " ");
    		}
    	}
    
    }