寻找正确方向的一步 . 我和我一起上过4节课 . 一个是超类，即图形和3个子类，称为Edge，DirectedGraph和BipartiteGraph .
我在创建二分图时遇到了一些麻烦 . 具体来说，我得到了这些指示：
扩展Graph类以创建新的BipartiteGraph类 . 它应该继承超类的所有功能：自动将所有偶数索引顶点（0,2,4）指定为类的“A分区”的一部分，并将所有奇数索引顶点（1,3,5）指定为部分“B分区” . 这不需要新的代码，只需要一个概念上的期望 . 覆盖Graph的构造函数以获得相同的输入（顶点数），调用超级构造函数，然后验证图是否为二分 . 也就是说，确保所有现有边都是从A中的顶点到B中的顶点 . 如果图不是二分，则擦除内部表示（例如，对于邻接矩阵，使大小为0x0数组），因此它不能使用！添加一个方法setPreferences（），它将一个整数和一个数组或整数的ArrayList作为参数 . 第一个整数是我们想要附加首选项的顶点，列表是首选项列表，从大多数到最不喜欢 . 验证int数组是否按某种顺序包含其他分区的所有成员然后保存该信息（您需要一个数组/ ArrayLists的一维数组来存储这些列表，每个顶点一个） . 添加没有参数的方法stableMatching并返回稳定匹配（以int对的ArrayList的形式） . 咨询维基百科是有帮助的：http：//en.wikipedia.org/wiki/Stable_marriage_problem . 首先，我建议验证每个顶点都有为其设置的首选项列表！
这是我在超类中的构造函数：
public class Graph {
// Setup privately modified variables which will define the graph
// These two parameters are storage variables for edges and vertices
// These variables were changed from Vertex and Edge to numVertices and
// numEdges.
private int numVertices;
private int numEdges;
// This will be the adjacency matrix to represent our graph, this will
// represent edges.
// adj_Matrix_Edges was previously static meaning it did not have access to
// multiple graphs, onyl one graph.
protected boolean[][] adj_Matrix_Edges;
// first step will be to setup the graph, using this constructor
public Graph(int vertices) {
numVertices = vertices;
if (numVertices < 0) {
throw new RuntimeException(
"Number of vertices cannot be a nonnegative value");
}
System.out.println("There are now " + numVertices
+ " vertices in the graph.");
// A graph is created based on the specifications, N X N or (n^2)
// graph.
adj_Matrix_Edges = new boolean[vertices][vertices];
}
这是我到目前为止为BipartiteGraph类所做的：
public class BipartiteGraph extends Graph{
//Initialize two partitions for bipartite graph.
boolean[][] a;
boolean[][] b;
//Constructor of BipartiteGraph class
public BipartiteGraph(int vertices) {
super(vertices);
//Copy over even elements of graph into partition A.
for (int i = 0; i < adj_Matrix_Edges.length; i++){
for (int j = 0; j < adj_Matrix_Edges[i].length; j++){
if (j%2 == 0){
adj_Matrix_Edges[j] = a[j];
}
}
}
//Copy over odd elements of graph into Partition B.
for (int i = 0; i < adj_Matrix_Edges.length; i++){
for (int j = 0; j < adj_Matrix_Edges[i].length; j++){
if (j%2 != 0){
adj_Matrix_Edges[j] = b[j];
}
}
}
}
public void setPreferences(int vertex, int[] preferences){
if ()
}
public List stableMatching(){
java.util.List<Integer> matching = new ArrayList<Integer>();
}
我做的事情太复杂了，代码是否比看起来更简单？
2 回答
我认为
BipartiteGraph的声明中有一个错误：您将
a和b声明为二维数组，作为矩阵 .a和b模型互补 subsets 的顶点集 . 因此，它们应该是顶点列表或布尔数组，表示第i个顶点是否在a中 . 此外，您不需要存储两者，因为一个是另一个的补充 .也许我错过了一些东西，但是你必须把它写成作业吗？否则，你可以依靠JUNG并使用HyperGraph：
http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/Hypergraph.html