隣接行列への単純な加算関数

Question

私は隣接行列を開発していますので、DFSを使ってオイラー回路の問題を解くことができます。 これは私の質問に関連するコードです：

public class Graph { 

private int numVertex; 
private int numEdges; 
private boolean[][] adj; 

public Graph(int numVertex, int numEdges) { 
    this.numVertex = numVertex; 
    this.numEdges = numEdges; 
    this.adj = new boolean[numVertex][numVertex]; 
} 

public void addEdge(int start, int end){ 
    if(!adj[start][end]) 
     numEdges++; 
    adj[start][end] = true; 
    adj[end][start] = true; 
} 

私がしようとすると、テストは、いくつかのエッジを追加することで、このコードを実行すると、私が手：私はコードをテストするためにこれを使用してい

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4 
at Graph.addEdge(Graph.java:18) 
at Graph.main(Graph.java:66) 

：

public static void main(String[] args) { 

    Scanner input = new Scanner(System.in); 

    int numVertices = input.nextInt(); 
    int numLinks = input.nextInt(); 
    int startNode = input.nextInt(); 

    Graph g = new Graph(numVertices, numLinks); 

    for(int i = 0; i<numLinks; i++){ 
     g.addEdge(input.nextInt(),input.nextInt()); 
    } 

問題はaddEdge関数にあると思います。何が間違っているのですか？

Answer 1

あなたの行列はゼロベースであることに注意してください。

numVerticesとして4を渡すと、マトリックスは0,0から3,3になります。

あなたは頂点4と他の間のエッジを追加しようとするならば、あなたはエラーになります...

Answer 2

あなたはエッジの数をインクリメントすると、adj行列のサイズが自動的に変更されません。グラフを拡大するときは、行列を再割り当てし、古い​​値を新しい行列にコピーする必要があります。再割り当てでは、より大きい行列を割り当てることで（サイズと容量の違いがあります）、容量が足りなくなった場合にのみ再割り当てすることで保存できます。

2次元の行列ではなくブール値を格納しているだけなので、BitSet（実際にはセットではなくビットベクトル）を使用することをお勧めします。あなたは使用して線形配列のインデックスに（行、列）のペアに変換することができます：

index = row * numEdges + column; 

をし、あなたが（必要に応じて）他の道を行くことができます：あなたはまだBitSetを再割り当てする必要が

column = index % numEdges; 
row = index/numEdges; 

グラフが大きくなると、ストレージ全体が節約されます。二思想に

EDIT

、私はこの問題は、あなたが頂点番号が範囲内にあることを確認されていないということだと思います。ユーザーが1から始まる頂点番号を指定したい場合は、adjの索引付けが0から始まるように、ユーザー入力から1を引く必要があります。少なくとも、エンドポイント入力が有効であることを確認する必要があります。

あなたはそれを試してみたい場合は、BitSet実装は次のようなものになります：隣接行列が対称であるので、あなただけの上部（または下）三角部分を格納することで、より多くのストレージを節約することができ

public class Graph { 

private int numVertex; 
private int numEdges; 
private BitSet adj; 

public Graph(int numVertex, int numEdges) { 
    this.numVertex = numVertex; 
    this.numEdges = numEdges; 
    this.adj = new BitSet(numVertex * numVertex); 
} 

public void addEdge(int start, int end){ 
    int index = start * numVertex + end; 
    if (!adj.get(index)) { 
     adj.set(index); 
     index = end * numVertex + start; 
     adj.set(index); 
     numEdges++; 
    } 
} 

を。しかし、これはインデックス作成の計算を少し複雑にします。