找出Graph是否与Java同构
我需要通过生成所有的排列来检查一个图是否同构。我正在使用这个置换类，现在我需要创建一个将图表示为二维布尔数组的图类。例如，用户以字符串形式输入2个图形
Ex."0-1 0-2 1-2 1-3 2-3" and "1-3 2-0 0-3 1-2 1-0"
现在，在我的构造器中，我必须将其分解，并将其放入一个二维布尔数组中。我该怎么做呢？
用户还可以输入更复杂的内容，如"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-11“和"0-1 1-2 2- 3 -0 0-4 0-7 1-4 1-5 2-5 2-6 3-6 -63-7 4-8 4-9 5-9 5-10 6-10 6-11 7-8 -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;
}
}回答 1
Stack Overflow用户
发布于 2012-12-04 08:31:47
您必须创建一个矩阵来表示您的图形，如下图所示：
您可以从提示用户输入连接的两个节点开始，例如1和2。
matrix[1][2] = true;如果考虑到方向，这意味着1 - 2不同于2 - 1。否则(一个非面向图的)，你会这样做
matrix[1][2] = true;
matrix[2][1] = true;别忘了用false初始化矩阵，意思是(顶点未连接)。每次你想要检查顶点X和Y是否直接相连，你只需要访问矩阵的位置(X,Y)并检查它是否为真。
如果你的图是一个加权的图，你需要有一个额外的矩阵来保存权重。另一种解决方案是只有一个整数矩阵，其中-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.
} https://stackoverflow.com/questions/13694201
复制相似问题
腾讯云开发者
