1

在这个作业中，我必须向 EdgeList 和 AdjMatrix 对象类添加一个例程，以返回广度优先生成树。签名将是：

在 EdgelList 中： EdgeList BFSpanning();

在 AdjMatrix 中：EdgeList BFSpanning();

但我真的很困惑，我只是在这两个类中编写 BFSpanning 方法吗？谁能给我一个硬结构？我似乎无法写出正确的方法。

这是我的 adjmatrix 类：

public class AdjMatrix extends Object implements Cloneable{
  private int size;
  private long[][] m;

  public Object clone(){
    int i, j;
    AdjMatrix ret;
    ret = new AdjMatrix();
    ret.setSize(this.getSize());
    for (i=0; (i < this.getSize()); i=i+1){
      for (j=0; (j < this.getSize()); j=j+1){
        ret.setUndirected(i, j, this.getEdge(i, j));
      }
    }
    return (ret);
  }

  public void setSize(int size) throws BadSizeException{
    int i, j;
    if (this.sizeOK(size)) {
      this.size = size;
      m = new long [size][];
      for (i=0; (i < size); i=i+1){
        m[i] = new long[size];
        for (j=0; (j < size); j=j+1){
          m[i][j] = -1;
        }
      }
    } else {
      throw new BadSizeException();
    }
  }

  public int getSize(){
    return(this.size);
  }

  public void setUndirected(int x, int y, long val) throws BadIndexException {
    if (this.OK(x, y)) {
      m[x][y] = val;
      m[y][x] = val;
    } else {
      throw new BadIndexException();
    }
  }

  public void setDirected(int x, int y, long val) throws BadIndexException {
    if (this.OK(x, y)) {
      m[x][y] = val;
    } else {
      throw new BadIndexException();
    }
  }
  public long getEdge(int x, int y) throws BadIndexException {
    long ret = -1;
    if (this.OK(x, y)) {
      ret = m[x][y];
    } else {
      throw new BadIndexException();
    }
    return (ret);
  }

  public boolean sizeOK(int size) {
    return (size > 0);
  }
  public boolean OK(int x, int y) {
    return (((x >=0) && (x < this.size)) &&
            ((y >=0) && (y < this.size)));
  }
}

这是我的 edglist 课程：

public class EdgeList extends Object implements Cloneable{
  private int nodeNumber;
  private Edges[] nodes;

  public Object clone(){
    int i, j;
    EdgeList ret;
    ret = new EdgeList();
    ret.setNodeNumber(this.nodeNumber);
    for (i=0; (i < this.getNodeNumber()); i=i+1){
      ret.nodes[i] = (Edges) (this.nodes[i].clone());
    }
    return (ret);
  }

  public void setNodeNumber(int nodes) throws BadNodeNumberException{
    int i;
    if (nodes > 0) {
      this.nodeNumber = nodes;
      this.nodes = new Edges[nodes];
      for (i=0; (i < nodes); i = i + 1){
        this.nodes[i] = new Edges();
        this.nodes[i].setSize(nodes);
      }
    } else {
      throw new BadNodeNumberException();
    }
  }

  public int getNodeNumber(){
    return(this.nodeNumber);
  }

  public void addEdge(int x, int y, long val) throws BadIndexException, DuplicateEdgeException {
    int i;
    if (this.OK(x, y)) {
      this.nodes[x].add(y, val);
    } else {
      throw new BadIndexException();
    }
  }

  public Edges getEdges(int i) throws BadIndexException {
    Edges ret = null;
    if ((i >= 0) && (i < this.nodeNumber)) {
      ret = (Edges)(nodes[i].clone());
    } else {
      throw new BadIndexException();
    }
    return (ret);
  }

  public boolean OK(int x, int y) {
    return (((x >=0) && (x < this.nodeNumber)) &&
            ((y >=0) && (y < this.nodeNumber)));
  }
}

也不知道你是否需要看到这个类的边缘：

public class Edges extends Object implements Cloneable{
  private int size;
  private int place;
  private Edge[] edges;
  public Object clone(){
    Edges ret;
    int i;
    ret = new Edges();
    ret.setSize(this.size);
    for (i=0; (i < this.getSize()); i=i+1){
      ret.add(this.edges[i].getNode(), this.edges[i].getValue());
    }
    return (ret);
  }

  public void setSize(int size){
    edges = new Edge[size];
    this.size = 0;
    this.place = 0;
  }
  public void add(int node, long value) throws DuplicateEdgeException{
    int i;
    boolean ok;
    Edge e;
    ok = ((node  > 0) && (node < edges.length)) && (size < edges.length);
    for (i=0; (i < this.size); i = i + 1) {
      ok = ok && (this.edges[i].getNode() != node);
    }
    if (ok) {
      e = new Edge();
      e.setNode(node);
      e.setValue(value);
      this.edges[this.size] = e;
      this.size = this.size + 1;
    } else {
      throw new DuplicateEdgeException();
    }
  }

  public Edge getCurrent(){
    Edge ret = null;
    if (size != 0) {
      ret =(Edge) (this.edges[place].clone());
    } else {}
    return (ret);
  }

  public void next(){
    this.place = (this.place + 1) % this.size;
  }

  public int getSize(){
    return (this.edges.length);
  }  
}
4

1 回答 1

0

如果您不明白，请向您的老师寻求澄清。话虽如此，我可以提供一个猜测：

是的，您要在每个类上编写一个方法。它们都返回一棵树，它是图的子集并具有所有顶点。他们实际上如何做到这一点将大不相同。该作业的目标很可能表明，以不同的方式存储相同的数据需要对同一问题有不同的解决方案。此外，您可能会发现一种方法比另一种更容易编写，这将表明某些数据格式使回答某些问题更容易或更难。

于 2015-07-07T17:51:54.657 回答