Первый поиск по глубине и первый поиск по ширине

Question

Первый поиск по глубине и первый поиск по ширине

Исключение нулевого указателя - это индикатор того, что вы используете объект, не инициализируя его.

Например, ниже - класс ученика, который будет использовать его в нашем коде.

public class Student {

    private int id;

    public int getId() {
        return this.id;
    }

    public setId(int newId) {
        this.id = newId;
    }
}

Приведенный ниже код дает вам исключение с нулевым указателем.

public class School {

    Student obj_Student;

    public School() {
        try {
            obj_Student.getId();
        }
        catch(Exception e) {
            System.out.println("Null Pointer ");
        }
    }
}

Поскольку вы используете Obj_Student, но вы забыли инициализировать его, как в правильном коде, показанном ниже:

public class School {

    Student obj_Student;

    public School() {
        try {
            obj_Student = new Student();
            obj_Student.setId(12);
            obj_Student.getId();
        }
        catch(Exception e) {
            System.out.println("Null Pointer ");
        }
    }
}

25

breadth-first-search depth-first-search algorithm java

задан Growler 30 May 2013 в 18:01

1 ответ

Другие вопросы по тегам:

breadth-first-search depth-first-search algorithm java

Похожие вопросы:

score 3 · Accepted Answer

Конечный результат ваших обходов правильный, вы довольно близки. Тем не менее, вы немного в деталях.

При первом глубинном поиске вы извлекаете узел, отмечаете его как посещенный и складываете его не посещенные дочерние элементы. В этой последовательности. Порядок может показаться несущественным для дерева, но если у вас есть граф с циклами, вы можете попасть в бесконечный цикл, но это другое обсуждение.

Учитывая базовую линию алгоритма, после того, как вы поместите корневой узел в стек, вы начнете свою первую итерацию, немедленно нажав A. Он не останется в стеке до конца алгоритма. Вы получите A, сложите D, C и B одновременно (или B, C и D, вы можете сделать это слева направо или справа налево, это ваш выбор) и отметите A как посещенное. Прямо сейчас ваш стек имеет D внизу, C посередине и B сверху.

Следующим выбранным узлом является B. Вы поместите F и E в стек (я сохраню порядок в том же порядке, что и у вас), отметив B как посещенный. В стеке сверху вниз E F C D. Затем E выталкивается, новые узлы не добавляются и E помечается как посещенные. Цикл будет продолжен, делая то же самое с F, C и D. Окончательный порядок - A B E F C D.

Я попытаюсь переписать алгоритм аналогично вашему:

Push root into stack
Loop until stack is empty
    Pop node N on top of stack
    Mark N as visited
    For each children M of N
        If M has not been visited (M.visited() == false)
            Push M on top of stack

Я не буду вдаваться в детали для поиска в ширину, алгоритм точно такой же. Разница заключается в структуре данных и их поведении. Очередь FIFO («первым пришел - первым обслужен»), и поэтому вы посетите все узлы одного уровня, прежде чем начнете посещать узлы нижних уровней.