gpt4 book ai didi

java - 找出 Graph 是否同构 Java

转载 作者:行者123 更新时间:2023-12-04 05:20:55 26 4
gpt4 key购买 nike

我需要通过生成所有排列来检查图是否是同构的。我正在使用这个置换类,现在我需要创建一个图形类,将图形表示为 2D boolean 数组。一个例子是用户输入 2 个图形作为字符串
Ex."0-1 0-2 1-2 1-3 2-3" and "1-3 2-0 0-3 1-2 1-0"
现在在我的构造函数中,我必须将其分解并将其放入二维 boolean 数组中。我该怎么做?

用户还可以输入更复杂的内容,例如“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"和"0-1 1-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;
}
}

最佳答案

您必须创建一个矩阵来表示您的图形,如下图所示:
enter image description here
您可以首先提示用户输入两个连接的节点,例如 1 和 2。然后您会这样做

matrix[1][2] = true;
如果你考虑方向,这意味着 1 - 2不同于 2 - 1 .否则(非定向图),你会做
matrix[1][2] = true;
matrix[2][1] = true;
不要忘记用 false 初始化矩阵, 含义(顶点未连接)。每次要检查顶点是否 XY直接连接,您只需访问位置 (X,Y)的矩阵并检查它是否为真。
如果您的图形是加权图形,则需要有一个额外的矩阵来保存权重。另一种解决方案是只有一个整数矩阵,其中 -1表示未连接, N > 0 , 表示给定的 XY与权重相连 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类(class):
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.
}

关于java - 找出 Graph 是否同构 Java,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13694201/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com