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 に答える