Подання графа списками суміжності в java

ArrayList[] Graph = new ArrayList [N];

Справа в тому що в Java у об'єктів є не тільки клас а й параметри класу, при цьому відповідність параметрів при виклику методів і при присвоєнні не перевіряється, просто іноді компілятор кидає warning'і про те що він не знає, який у даного об'єкта параметр. Можна створити ArrayList і привласнити його в ArrayList і це компілюватиметься. У Рантайм відбувається наступне: при виклику параметризрвані методу перевіряється що параметр об'єкта відповідає тому параметру який там очікується, в разі невдачі генерується якийсь RuntimeException.

Щось я не помітив, щоб від цього пропало попередження "Note: Main.java uses unchecked or unsafe operations". Або це так і повинно залишитися, а заяви про те, що Java краще, ніж плюси, гарантує безпеку виконання, треба ділити на 0x100?

Повний текст -
[Cut]
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Main static int nextInt (StreamTokenizer in) try in.nextToken ();
return (int) in.nval;
> Catch (IOException ex) Logger.getLogger (Main.class.getName ()). Log (Level.SEVERE, null, ex);
return 0;
>
>
public static void main (String [] args) throws FileNotFoundException StreamTokenizer in = new StreamTokenizer (new FileReader ( "input.txt"));
PrintWriter out = new PrintWriter (new File ( "output.txt"));
int TEST_NUM = nextInt (in);
for (int the_test = 0; the_test ArrayList[] Graph = new ArrayList [N];
for (int i = 0; i graph [i] = new ArrayList();
for (int k = 0; k graph [u] .add (new Integer (v));
>
int [] st = new int [N];
int [] d = new int [N];
Arrays.fill (st, 0);
Arrays.fill (d, 987654321);
int start = nextInt (in);
st [start] = 1;
d [start] = 0;
Queue qqq = new ArrayDeque();
qqq.add (start);
while (! qqq.isEmpty ()) int u = qqq.poll ();
for (int w. (ArrayList) Graph [u])
if (st [w] == 0) qqq.add (w);
st [w] = 1;
d [w] = d [u] +1;
>
>
for (int i = 0; i out.print (d [i] + "");
out.println ();
>
out.close ();
>
>

ArrayList[] Graph = new ArrayList [N];

@SuppressWarnings ( "unchecked")
ArrayList[] Graph = new ArrayList [N];

раз вже так цей warning ненависний

Більше так не роби, використовуй що-небудь типу ideone або paste.pocoo.org

По-перше generic-ами часто бувають unsafe casts, і warning-й нікуди не дінеш. По-друге в Java 7 компілятор розглядає частина з цих випадків як safe і нічого не пише. По-третє безпека - це коли програма не падає від неправильного дії а генерує exception, який ловиться і обробляється. Точно так само можна попросити перевірити можливість поділу на 0 або присвоювання типу Integer x = (Integer) obj;

"Безпека - це коли програма не падає від неправильного дії а генерує exception, який ловиться і обробляється"
Де саме я не маю рації, вважаючи, що коли неправильна дія взагалі не пропускається компілятором, то це ще більш безпечно?

Деректіви компілятора взагалі то можна змінювати. Тому всі Ваші шлагбауми можна цілком обійти, відключивши перевірки на рівні JVM.

За роз'яснення, що писати треба
ArrayList[] Graph = new ArrayList [N];
-- величезне спасибі, схоже, це на 99% закриває питання.

А щодо решти тексту повідомлення - щось чи то погано написано, чи то я погано читаю, але спочатку я його навіть не здогадувався. Особливо мене засмутило твердження "Можна створити ArrayList і привласнити його в ArrayList і це компілюватиметься. ".

Щоб привласнити їх при компіляції потрібно це зробити через перетворення до Raw Type:

List listI = new LinkedList();
listI.add (7);
List list = listI;
List listS = list;
listS.add ( "Java");
System.out.println (listS);

При компіляції нічого очікувати помилки, однак буде попередження яке можна побачити з допомогою -XLint: unchecked

Це зроблено для сумісності зі старими версіями (до 5-ї Java).

Сам зазвичай писав на плюсах vector> Але якось недавно наслухався що vector> Типу ефективніше. Сам такого правда не помітив, але чомусь повірив. У list-е адже напевно багато пам'яті йде на покажчики, пам'ять напевно ж і тепер (а не тільки 15 років тому) виділяється не побайтно а якимись параграфами або ще якимись порціями, і т.д.
Втім, ArrayList або LinkedList, як мені здається, абсолютно не впливає на суть основного питання.

Чим все-таки не влаштовує масив ArrayList'ов?
Начебто операції з графом реалізовувати простіше.
Щодо перфомансу приблизно однаково, але взагалі у списків суміжності є потенційна перевага в тому, що суміжні з вершиною ребра йдуть послідовно на відміну від одного великого списку, де немає такого порядку.
Якщо потрібне повноцінне видалення ребер, то можна по-аналогії зробити масив HashSet'ов, якщо перфоманс не дуже важливий.
Цікаве питання - як зробити швидку структуру для додавання / видалення ребер / вершин.

Схожі статті