0

问题是使用递归以最少的颜色数为给定的图形着色，这样相邻的顶点就不能具有相同的颜色。函数签名是静态字符串穷举（int color，String prefix），其中颜色是正在使用的颜色数在该迭代中，前缀是由每个节点的颜色组成的字符串（例如，如果有 3 个节点，其中节点 0 用颜色 0 着色，节点 1 用颜色 1 着色，节点 2 用颜色 2 着色；然后前缀将是 012）。当所有节点都着色时，该函数返回字符串前缀。第一次调用是使用参数 (0,"") 进行的，这意味着尝试用 0 种颜色着色。这是我写的代码。对于少于 34 个节点，它工作正常并返回正确答案，但对于大于 34 个节点，该函数不会返回到主节点。任何改进代码的想法将不胜感激。如果需要更多信息，请告诉我。

int n=36;
static int[] lastcolor = new int[n];    
static StringBuilder newprefix ;
String addprefix="";
static int node=0,j=0;
Graph.generateFixedSet(n);
verticies2 =Graph.getVerticies();

public static String exhaustive(int color,String prefix)

 {

    newprefix = new StringBuilder(prefix);

        if(prefix.length()==verticies2.size())
            return prefix;
        else
        {
             for(;j<=color;j++)
            {
                lastcolor[node]=j;

                addprefix = Integer.toString(j);
            canColor =1;
            tempnode = (verticies2.get(node)).getEdges();
                for( h=0;h<tempnode.size();h++)
                {
                     if((tempnode.get(h)).getColor() == j)
                {
                    canColor =0;
                    break;
                }

             }

            if(canColor==1)
                {
                        verticies2.get(node).setColor(j);              
                    node++;
                        j=0;
                newprefix.append(addprefix);
                        break;

                }//end if canColor  
            }//end for

        if(j!= 0)
            {


                if(node==1)
                {                           
                        color++;
                        j=0;
                        node=1;
                newprefix.delete(0,newprefix.length());
                newprefix.append("0");

                }//end if node <=1
                else
                {
                        verticies2.get(node).setColor(-1);
                        node--;
                        j=lastcolor[node]+1;
                        newprefix.setLength(node);
                    }
            }//end if j!=0
            prefix = newprefix.toString();
            return exhaustive(color,prefix);
            }//end else
     }//end exhaustive
4

1 回答 1

0

不要使用递归。如有必要，请使用循环...和数组列表。

于 2012-03-18T18:27:09.333 回答