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

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

В разделе "Графы" он утверждает:

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

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

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

Ответы

Ответ 1

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

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

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

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

Это просто простой набор данных, я обычно реализую это с помощью 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.

О и BTW, здесь - очень хорошее резюме этого сообщения с фантастическими картинами;)

Ответ 2

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

Сравнение

struct Node {
    Node *neighbours[];
};

с

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

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

Ответ 3

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