首页 > 专题系列 > Java解POJ > POJ 1419 Graph Coloring [解题报告] Java
2013
11-09

POJ 1419 Graph Coloring [解题报告] Java

Graph Coloring

问题描述 :

You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph and the only available colors are black and white. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes may be black.

Figure 1: An optimal graph with three black nodes

输入:

The graph is given as a set of nodes denoted by numbers 1…n, n <= 100, and a set of undirected edges denoted by pairs of node numbers (n1, n2), n1 != n2. The input file contains m graphs. The number m is given on the first line. The first line of each graph contains n and k, the number of nodes and the number of edges, respectively. The following k lines contain the edges given by a pair of node numbers, which are separated by a space.

输出:

The output should consists of 2m lines, two lines for each graph found in the input file. The first line of should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring. It is given by the list of black nodes, separated by a blank.

样例输入:

1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

样例输出:

3
1 4 5

解题代码:

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
 static Scanner cin;
 public static void main(String args[]){
   cin = new Scanner(System.in);

   int m = cin.nextInt();
   for(int i=0;i< m;i++)
     run();
  }

 static void run(){
   int n = cin.nextInt();
   int k = cin.nextInt();

   Graph graph = new Graph(n);
   for(int i=0;i< k;i++)
	graph.addEdge(cin.nextInt(), cin.nextInt());

   graph.Coloring(0);
   System.out.println(graph.maxBlack);
   graph.record.print();
  }
}

class Graph{
 int n;
 Node[] nodes;

 int maxBlack=-1;
 Record record;

 public Graph(int n){
   this.n = n;

   nodes = new Node[n];
  for(int i=0;i< n;i++)
    nodes[i] = new Node();

  record = new Record();
 }

 void addEdge(int m, int n){
   nodes[m-1].add(nodes[n-1]);
   nodes[n-1].add(nodes[m-1]);
 }

 void Coloring(int colored){
   if(colored< n){
     int position=0;
	while(nodes[position].color != 0)
     position = (position+1)%n;
     Node node = nodes[position];

     node.color = 'b';
     if(node.check() == true)
	Coloring(colored+1);

     node.color = 'w';
     Coloring(colored+1);

     node.color = 0;
     return;	
   }	

   int tmp = countBlack();
   if(tmp > maxBlack){
	maxBlack = tmp;
	record.clear();

	for(int i=0;i< n;i++)
         if(nodes[i].color == 'b')
	    record.add(new Integer(i+1));
    }

}

int countBlack(){
  int count=0;
  for(int i=0;i< n;i++)
    if(nodes[i].color == 'b')
	count++;
  return count;
 }
}

class Node{
 char color=0;
 LinkedList< Node> linkList;

 void setColor(char c){
   color = c;
}

void add(Node another){
  if(linkList==null)
    linkList = new LinkedList< Node>();

  linkList.add(another);
 }

 boolean isEdgeColored(){
  for(Node n:linkList)
    if(n.color == 0)
      return false;
  return true;
 }

 boolean check(){
  if(color=='w')
    return true;

   for(Node n:linkList)
    if(n.color=='b')
	return false;
   return true;
 }
}

class Record extends ArrayList< Integer>{
  void print(){
   for(Integer p:this)
	System.out.print(p+" ");
   System.out.println();
 }

}

  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢