0

問題は、隣接する頂点が同じ色を持つことができないように、最小数の色で特定のグラフを色付けするために再帰を使用することです。その繰り返しと接頭辞は、各ノードの色で構成される文字列です (例: 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 に答える