2

すべての順列を生成して、グラフが同型であるかどうかを確認する必要があります。この順列クラスを使用しているので、グラフを2Dブール配列として表すグラフクラスを作成する必要があります。例として、ユーザーが2つのグラフに文字列として入力する場合があります

Ex."0-1 0-2 1-2 1-3 2-3" and "1-3 2-0 0-3 1-2 1-0"

今、私のコンストラクターでは、それを分割して2Dブール配列に配置する必要があります。どうすればいいですか？

ユーザーは、「0-1 1-2 2-3 3-0 0-4 0-11 1-5 1-6 2-7 2-8 3-93-104-5」のようなもっと複雑なものを入力することもできます。 6-7 8-9 10-11 4-7 4-8 5-9 5-10 6-9 6-10 7-118-11"および"0-11-2 2-3 3-0 0- 4 0-7 1-4 1-5 2-5 2-6 3-6 3-7 4-8 4-9 5-9 5-10 6-10 6-11 7-8 7-11 8-9 9 -10 10-11 11-8 "

public class PermutationGenerator
{
    // private data

    private int[] perm;
    private boolean first;

    // constructor

    public PermutationGenerator (int n)
    {
        perm = new int [n];
        first = true;
    }



    public int[] next ()
    {
        int n = perm.length;

        // starting permutation: 0 1 2 3 ... n-1

        if (first)
        {
            first = false;
            for (int i = 0 ; i < n ; i++)
                perm [i] = i;
            return perm;
        }

        // construct the next permutation
        // find largest k so that perm[k] < perm[k+1]; if none, finish

        int i, j, k, l;

        for (k = n - 2 ; k >= 0 && perm [k] >= perm [k + 1] ; k--)
            ;
        if (k < 0)
            return null; // no more

        // find largest l so that perm[k] < perm[l]

        for (l = n - 1 ; l >= 0 && perm [k] >= perm [l] ; l--)
            ;

        // swap perm[k] and perm[l]

        swap (perm, k, l);

        // reverse perm[k+1]...perm[n-1]

        for (i = k + 1, j = n - 1 ; i < j ; i++, j--)
            swap (perm, i, j);

        return perm;
    }


    // swap a[i] and a[j]

    private static void swap (int a[], int i, int j)
    {
        int temp = a [i];
        a [i] = a [j];
        a [j] = temp;
    }
}
4

1 に答える 1

3

次の図に示すように、グラフを表すマトリックスを作成する必要があります。

ここに画像の説明を入力してください

接続されている2つのノード、たとえば1と2の入力をユーザーに求めることから始めることができます。次に、次のようにします。

matrix[1][2] = true;

方向を考慮している場合、それはと1 - 2は異なることを意味し2 - 1ます。それ以外の場合（グラフが方向付けられていない場合）、

matrix[1][2] = true;
matrix[2][1] = true;

false行列を、意味（頂点が接続されていない）で初期化することを忘れないでください。X頂点が直接接続されているかどうかを確認するたびに、マトリックスYの位置にアクセスして、それが真であるかどうかを確認する必要があります。(X,Y)

グラフが加重グラフの場合、加重を保持するために追加の行列が必要です。別の解決策は、整数の行列を1つだけ持つことです。ここで、-1は接続されていないN > 0ことを意味し、は、与えられたXとYが重みで接続されていることを意味しNます。

ユーザー入力について：

"0-1 1-2 2-3 3-0 0-4 0-11 1-5 1-6 2-7 2-8 3-9 3-10 4-5 6-7 8-9 10-11 4 -7 4-8 5-9 5-10 6-9 6-10 7-11 8-11 "

特に、 Scannerクラスを使用できます。

String input;
Scanner in = new Scanner(System.in);

// Reads a single line from the console 
// and stores into name variable
input = in.nextLine();

その後、入力を解析する必要があります。グラフの頂点を保持する固定形式を想定します。次に例を示します。

  String input =  "0-1 0-2 1-2 1-3 2-3";
  int x,y;

  for(int i = 0; i < input.length(); i+=4)
  {
       x = Character.getNumericValue(input.charAt(i));   // first vertex 
       y = Character.getNumericValue(input.charAt(i+2)); // second vertice 
       matrix_graph[x][y] = true;
       matrix_graph[y][x] = true; // if the graph is not oriented.
  }
于 2012-12-04T00:31:47.417 に答える