4

この質問は、Java 開発者にとってかなり簡単なはずです。約 2 時間かけて調べたのですが、このコードの何が問題なのかよくわかりません。

基本的に、Karger の最小カット アルゴリズムを実装しています。グラフ内のノードをマージし続け、最後に交差するエッジの数 (int 値) を計算する必要があります。このアルゴリズムは、常に最初のグラフから n 回繰り返す必要があります。私の問題は、Graph オブジェクトのディープ コピーを作成できず、間違いを見つけられないことです。

問題を表示するだけでコードをトリミングしましたが、何が問題なのかまだわかりません。ここにコードがあります。

クラス ノード:

public class Node {
public Integer Data;


public Node() {
    Data = 0;
}

public Node(Node rhs) {
    Data = rhs.Data.intValue();
}

public Node(Integer rhs) {
    Data = rhs.intValue();
}

public void setNode(Integer rhs) {
    Data = rhs;
}

クラスグラフ:

public class Graph {

public ArrayList<ArrayList<Node>> AdjList;
public ArrayList<Node> NodeSet; // This contains all the nodes

public Graph() {
    AdjList = new ArrayList<ArrayList<Node>>();
    NodeSet = new ArrayList<Node>();
}

public Graph(Graph G) {
    AdjList = new ArrayList<ArrayList<Node>>();
    for (ArrayList<Node> L : G.AdjList) {
        ArrayList<Node> Lcopy = new ArrayList<Node>();
        for (Node N : L) {
            Node copy = new Node(N);
            Lcopy.add(copy);
        }
        AdjList.add(L);
    }
}
    public void addNewAdjList(ArrayList<Node> NodeAdjList) {
    // Input is the adjacency list of a new node
    // The first element in the NodeAdjList is the node itself, the rest is the adj nodes
    AdjList.add(NodeAdjList);
}
public static void printAdjList(ArrayList<Node> Adjlist) {
    Node start = Adjlist.get(0);
    System.out.print(start.Data + " : ");
    for (int j=1; j < Adjlist.size(); ++j) {
        System.out.print(Adjlist.get(j).Data + ", ");
    }
    System.out.print("\n");
}

主要：

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
    Node Five = new Node(5);
    Node Seven = new Node(7);
    Node One = new Node(1);
    
    Graph G = new Graph();
    
    ArrayList<Node> L = new ArrayList<Node>();
    L.add(Five);
    L.add(Seven);
    L.add(One);
    
    G.addNewAdjList(L);
    
    Graph R = new Graph(G);
    R.AdjList.get(0).get(1).setNode(19); // Gets node #1 in the first adj list, i.e. 7
    
    Graph.printAdjList(G.AdjList.get(0));
    Graph.printAdjList(R.AdjList.get(0));

}

}

出力：

5:19、1、

5:19、1、

この種のことは、正直言って私を困惑させます。Java は値渡しのみであることは理解していますが、オブジェクトは常に参照によって表されます。私が理解している限り、G のコピー コンストラクターは常にディープ コピーを作成する必要があります。すべての隣接リストを移動してから、ノードのディープ コピーを作成しています。コピーされたオブジェクトで .setNode() を呼び出すと、元のオブジェクト (参照が異なる) も変更される理由がわかりません。

1のような以前の回答は、私が行っているのと同じ方向に進んでいるようです。ここで何が欠けていますか? :S

4

1 に答える 1

5

あなたのエラーはここにあります：

ArrayList<Node> Lcopy = new ArrayList<Node>();
for (Node N : L) {
    Node copy = new Node(N);
    Lcopy.add(copy);
}
AdjList.add(L);

L(と呼ばれる)のコピーを作成しましたが、元のグラフを複製したグラフにLcopy追加しました。それを修正するには、最後の行を次のようにします。 L

AdjList.add(Lcopy);

注: このエラーの代わりに変数に適切な名前を使用していれば、Lおそらくこのエラーは発生しなかったでしょう!

于 2012-07-29T22:11:32.070 に答える