Java - Узлы против Ints для графа, реализованного с использованием списка смежности

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

Проблема в том, что большинство реализаций списков смежности, которые я вижу в Интернете (Example1, Example2 и Example3) вообще не использовать узлы. Они просто используют HashMap целых чисел и LinkedLists. Это вообще правильно? Поскольку в определении (Wikipedia) говорится, что он состоит из вершин или узлов. Более того, большинство реализаций графов, использующих матрицу смежности, используют узлы, а не целые числа. Example4. Я что-то упускаю в этой головоломке?

Я понимаю, что использование целых чисел в отличие от узлов более эффективно с точки зрения пространства, однако это приводит к еще большему количеству сложностей. Например, посмотрите этот фрагмент кода из примера 1 -

// add edge from vertices v1 to v2
void addEdge(int v1,int v2){
adj.get(v1).add(v2);
}

его цель - добавить ребро от v1 до v2. Он полностью игнорирует возможность того, что может быть более одной вершины с одинаковым значением int, и в этом случае он оставляет открытой возможность того, что метод addEdge () может добавить ребро между непредусмотренными вершинами.

Так является ли неправильная реализация списков смежности в Example1,2,3? Если они правы, будет ли плохо, если я реализую список смежности с использованием узлов вместо целых чисел? Я не хочу, чтобы мои интервьюеры думали, что я какой-то идиот, лол


java nodes graph adjacency-list adjacency-matrix
person satnam    schedule 28.01.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете использовать Node (который содержит тип данных) или сразу использовать тип данных (в ваших примерах Integer), и они оба будут работать

Однако использование Node - лучший выбор по нескольким причинам

  1. Избегайте проблем, о которых вы правильно упомянули, с повторяющимися значениями данных
  2. Использование узла более объектно-ориентировано. Это позволяет классу Graph работать с любым типом данных, который содержит узел. Это делает код более переносимым, поскольку график может работать со строками, длинными, целыми числами и т. Д.

  3. Чтобы воспользоваться преимуществами переносимости, о которых я упоминал выше, класс Node должен быть определен следующим образом

    class Node<T>{
    T data;
}

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

Надеюсь, это поможет!

person abhaybhatia    schedule 29.03.2016