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

Question

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

В своем разделе «Графики» он утверждает:

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

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

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

Answer 1

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

Это просто базовые структуры данных, как сказал Хаммар в другом ответе, в 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  

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

matrix

Матрица - это простой двумерный массив.Предполагая, что у вас есть идентификаторы вершин, которые можно представить в виде массива типа 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 .

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

Answer 2

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

Сравните

struct Node {
    Node *neighbours[];
};

с

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

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

Answer 3

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

Answer 4

Другой хороший ресурс: Академия Хана - «Представление графов»

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

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

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

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

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