Сравнение представления графа объекта со списком смежности и матричным представлением

82

В настоящее время я следую совету Стива Йегге по подготовке к собеседованию по техническому программированию: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

В своем разделе о графиках он утверждает:

Существует три основных способа представления графа в памяти (объекты и указатели, матрица и список смежности), и вам следует ознакомиться с каждым представлением и его плюсами и минусами.

Плюсы и минусы представлений матриц и списков смежности описаны в CLRS, но мне не удалось найти ресурс, который сравнивал бы их с представлением объекта.

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

algorithm graph graph-algorithm jbeard4
источник
как насчет индуктивных графов - к какой из 3 категорий они относятся?
Эрик Каплун

Ответы:

94

объекты и указатели

Это просто базовые структуры данных, такие как hammar, о которых говорится в другом ответе, Javaвы бы представили это с помощью классов, таких как ребра и вершины. Например, ребро соединяет две вершины и может быть направленным или неориентированным и может содержать вес. Вершина может иметь идентификатор, имя и т. Д. В большинстве случаев обе имеют дополнительные свойства. Таким образом, вы можете построить свой график с ними, например

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30

Этот подход обычно используется для объектно-ориентированных реализаций, поскольку он более читабелен и удобен для объектно-ориентированных пользователей;).

матрица

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

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

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

список смежности

Это просто микс простой структуры данных, я обычно реализую это с помощью файла HashMap<Vertex, List<Vertex>>. Аналогичный крест может быть HashMultimapв Гуаве.

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

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

Это используется для представления разреженных графиков. Если вы подаете заявку в Google, вы должны знать, что веб-граф разреженный. Вы можете справиться с ними более масштабируемым образом, используя BigTable .

Да и кстати, вот очень хорошее резюме этого поста с модными картинками;)

Томас Юнгблут
источник
Этот подход хорош, потому что у вас есть поиск вершин O (1), эта сложность немного неверна, в частности, это O (1 + alpha), где альфа = количество слотов в хеш-карте / количество вершин. Поэтому я предлагаю использовать массив вместо хеш-карты
Тимофей
@Tim амортизируется на O (1). Ваш расчет сложности сильно зависит от реализации. См. JavadocHashMap ( docs.oracle.com/javase/7/docs/api/java/util/HashMap.html ), в котором говорится: This implementation provides constant-time performance for the basic operations= O (1) амортизировано.
Thomas Jungblut
6
@Tim Я думаю, что все здесь знают, что доступ к массиву быстрее, чем при любом HashTableиспользовании. Так что не нужно придираться к небольшим постоянным альфа-накладным расходам, которыми можно пренебречь.
Thomas Jungblut
2
Пожалуйста, не поймите меня неправильно, я не оскорбляю вас хорошим ответом, но у меня такое чувство, что ваш ответ может быть улучшен, так почему бы не упомянуть его здесь :)
Тимофей
2
@Tim Я добавил в ответ амортизированную записку. Благодарю.
Thomas Jungblut
7

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

Сравнить

struct Node {
    Node *neighbours[];
};

с участием

struct Node {
    Node *left;
    Node *right;
};

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

хаммар
источник
4

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

Михал Чизмазия
источник
5
почему есть ссылка на представление списка смежности под названием "список инцидентов"? Наверное, лучше использовать этот алгоритмist.com
index.php/
1

Еще один хороший ресурс: Khan Academy - «Представляющие графы».

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

Преимущество: мы можем хранить больше информации о кромке (упомянутой Михалом)

Недостаток: это очень медленная структура данных для работы:

  • Найдите край: O (log e)
  • Убрать ребро: O (e)
  • Найти все узлы, смежные с данным узлом: O (e)
  • Определите, существует ли путь между двумя узлами: O (e ^ 2)

e = количество ребер

Крис Люнг
источник