Простая функция добавления к матрице смежности

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

Помните, что ваша матрица основана на нулевом значении.

Если вы прошли 4 как numVertices, ваша матрица будет идти от 0,0 до 3,3.

Затем, если вы попытаетесь добавить ребро между вершиной 4 и любым другими вы будете иметь ошибку ...

Answer 2

Когда вы увеличиваете число ребер, размер adj матрицы не меняется автоматически. Когда вы вырастите график, вам нужно перераспределить матрицу и скопировать старые значения в новую матрицу. Вы можете сэкономить на перераспределении, выделив большую матрицу для начала (так что разница между размером и емкостью) и только перераспределение, когда у вас заканчивается емкость.

Могу ли я предположить, что, поскольку вы просто сохраняете логическое значение, вместо двумерной матрицы, вы просто используете BitSet (что на самом деле является битовым вектором, а не множеством). Вы можете конвертировать (строка, столбец) пар к линейному индексу массива с помощью:

index = row * numEdges + column; 

и вы можете пойти другим путем (при необходимости) с:

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

Вам все еще нужно перераспределить BitSet когда график растет, но вы сэкономите много хранения.

EDIT

На второй мысли, я думаю, что проблема в том, что вы не проверить, что число вершин находятся в пределах диапазона. Если вы хотите, чтобы пользователь указывал число вершин, начинающееся с 1, вам нужно вычесть 1 из ввода пользователя, чтобы индексирование adj начиналось с 0. Как минимум, вы должны проверить, что входы конечной точки действительны.

Если вы хотите попробовать, 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++; 
    } 
} 

Поскольку матрица смежности симметрична, вы могли бы сэкономить больше места для хранения лишь хранить верхнюю (или нижнюю) треугольная часть , Но это сделало бы вычисление индексации немного более сложным.