Графы

[NikiToZz_]

Добрый день. Возник вопрос: как хранить графы в коллекциях, не в двумерных массивах.

А вопрос возник вот почему. Искал реализацию поиска в глубина на JAVA и в викиучебнике написано:

List<Integer>[] graph = readGraph();
boolean[] used = new boolean[graph.length];

public static void dfs(int pos) {
    used[pos] = true;
    System.out.println(pos);
    for (int next : graph[pos])
        if (!used[next])
            dfs(next);
}

Реализация, разумеется, верна. Но мне непонятно, как здесь хранится сам граф.

P.S. другими словами, напишите метод readGraph();

[p51x]

https://ru.wikipedia.org/wiki/%D0%A1...81%D1%82%D0%B8

Причем тут Java?.. Это ж базовые вещи из математики или только из-за кода...

[NikiToZz_]

Сообщение от p51x

https://ru.wikipedia.org/wiki/%D0%A1...81%D1%82%D0%B8

Причем тут Java?.. Это ж базовые вещи из математики или только из-за кода...

Мой вопрос вроде бы понятен) Мне нужно увидеть реализацию с ArrayListom, а не ссылочку на список смежности в вики)

[p51x]

Что там не понятно? В файле/пользовательском вводе/на луне как-то записаны списки смежности, например, так:

2 3
4
5
1 2

Вот каждая строка и получается ArrayList.

P.S. Конечно, вы всегда можете обратиться в раздел фриланса и за вас напишут один из вариантов.

[NikiToZz_]

Сообщение от p51x

Что там не понятно? В файле/пользовательском вводе/на луне как-то записаны списки смежности, например, так:

2 3
4
5
1 2

Вот каждая строка и получается ArrayList.

P.S. Конечно, вы всегда можете обратиться в раздел фриланса и за вас напишут один из вариантов.

Допустим, у меня есть такой список смежности.

1 2
1 3
2 4

т.е. у графа 4 вершины.

Я пишу такую реализацию, чтобы позже пройтись по списку dfsом, описанным выше:

public static ArrayList<Integer>[] readGraph() {
        ArrayList<Integer>[] graph = new ArrayList[num];
        for (int i = 0; i < (num - 1); i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < num; i++) {
            int arI = scan.nextInt();
            int arJ = scan.nextInt();
            graph[arI].add(new Integer(arJ));
        }
        return graph;
    }

В итоге в ArrayList у меня, судя по всему, получается немного не то, что мне хотелось бы видеть для dfs.

[p51x]

Давайте с простого: что такое num и чему он равен? Предполагаю, что количество вершин и 4, тогда:

for (int i = 0; i < num; i++) {

сколько строк вы тут считываете и сколько в файле?

[NikiToZz_]

Сообщение от p51x

Давайте с простого: что такое num и чему он равен? Предполагаю, что количество вершин и 4, тогда:

for (int i = 0; i < num; i++) {

сколько строк вы тут считываете и сколько в файле?

Копировал разные участки кода, поэтому так получилось.. там везде до num - 1. Проблема не в том, что я не могу создать arrayList со списка смежности. Проблема моя состоит в том, что после того, как создаю этот самый ArrayList, и я запускаю dfs. У меня вылетает исключение ArrayIndexOutOfBoundsException

[NikiToZz_]

Сообщение от p51x

Давайте с простого:

Давайте. Объясните, почему в dfs на вики берется именно массив коллекций?

List<Integer>[] graph = readGraph();

Как, по их мнению, должен храниться граф?

[Black Fregat]

Опередили, пока писал..

Сообщение от NikiToZz_

Реализация, разумеется, верна.

Но там нет никакого условия завершения поиска.

Сообщение от NikiToZz_

Допустим, у меня есть такой список смежности.

Судя по дальнейшему коду, это список рёбер, а не смежности.

Сообщение от NikiToZz_

Я пишу такую реализацию

Тут явная проблема вокруг num.
1) Как-то не очень правильно заводить массив размером num в которм инициализировать только первые (num-1) членов.
2) Насколько я понял, num - количество вершин, но ведь количество рёбер никак с ним не связано, почему второй цикл тоже до num?

[NikiToZz_]

Сообщение от Black Fregat

2) Насколько я понял, num - количество вершин, но ведь количество рёбер никак с ним не связано, почему второй цикл тоже до num?

Там везде до (num-1). моя описка

Сообщение от Black Fregat

Но там нет никакого условия завершения поиска.

if (!used[next])

-- оно и есть