Я практикую пару алгоритмов (DFS, BFS). Чтобы настроить практические примеры, мне нужно сделать граф с вершинами и ребрами. Я видел два подхода — определение массива вершин и массива ребер, а затем объединение их в «граф» с использованием словаря, например:
graph = {'A': ['B', 'E', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B', 'E'],
'E': ['A', 'B', 'D'],
'F': ['C'],
'G': ['C']}
Но в серии видеороликов, сделанных автором «взлома интервью по кодированию», их подход состоял в том, чтобы определить объект «узел», который содержит идентификатор, и список смежных/дочерних узлов (на Java):
public static class Node {
private int id;
LinkedList<Node> adjacent = new LinkedList<Node>(); // nodes children
private Node(int id) {
this.id = id; //set nodes ID
}
}
Ловушка, которую я вижу при использовании последнего метода, заключается в создании пользовательской функции для добавления ребер, а также в отсутствии непосредственного обзора структуры всего графа; Чтобы создать ребра, вы должны сначала получить объект узла, связанный с идентификатором, сначала перейдя к нему или используя хэш-карту, а затем, используя его ссылку, добавив целевой узел к этому исходному узлу:
private Node getNode(int id) {} //method to retrieve node from hashmap
public void addEdge(int source, int destination) {
Node s = getNode(source);
Node d = getNode(destination);
s.adjacent.add(d);
}
Хотя по сравнению с использованием простого словаря добавление новых ребер тривиально:
graph['A'].append('D')
Используя объект узла, добавление нового соединения к каждому дочернему элементу узла становится более подробным (представьте, что класс Node является классом Python, который принимает идентификатор и список дочерних элементов узла):
node1 = Node('A', [])
node2 = Node('B', [node1])
node3 = Node('C', [node1, node2])
new_node = Node('F', [])
for node in node3.adjacent:
node.adjacent.append(new_node) # adds 'F' node to every child node of 'C'
при использовании словарей, если я хочу добавить new_node к каждому соединению/дочернему элементу node3:
for node in graph['C']:
graph[node].append('F')
Каковы преимущества пространственной и временной сложности построения графов с использованием узловых объектов по сравнению со словарями? Зачем автору использовать объекты узла вместо словаря? Моя непосредственная интуиция подсказывает, что использование объектов позволит вам сделать что-то гораздо более сложное (например, каждый узел, представляющий сервер, с IP-адресом, mac-адресом, кешем и т. д.), в то время как словарь, вероятно, полезен только для изучения структуры графа. Это верно?
Каковы преимущества пространственной и временной сложности при построении графов с использованием узловых объектов по сравнению со словарями?
С точки зрения пространства сложность одинакова для обоих. Но с точки зрения времени у каждого есть свои преимущества.
Как вы сказали, если вам нужно запросить конкретный узел, лучше использовать словарь с запросом O (1). Но если вам нужно добавить узлы, версия с графом имеет только временную сложность O (1), в то время как словарь имеет амортизированную временную сложность O (1), становясь O (n), когда требуется расширение.
В целом, думайте о сравнении как о ArrayList и LinkedList, поскольку принципы одинаковы.
Наконец, если вы решите использовать словарную версию и предсказываете, что у вас не будет небольшого количества смежных узлов, вы можете хранить ребра в наборе вместо массива, поскольку они, скорее всего, не упорядочены и запрашивают узел. поскольку существование смежного узла становится операцией O (1) вместо O (n). То же самое относится и к версии узлов, использующей набор вместо связанного списка. Просто убедитесь, что дополнительные накладные расходы на вставки оправдывают себя.
Моя непосредственная интуиция подсказывает, что использование объектов позволит вам сделать что-то гораздо более сложное (например, каждый узел, представляющий сервер, с IP-адресом, mac-адресом, кешем и т. д.), в то время как словарь, вероятно, полезен только для изучения структуры графа. Это верно?
Нет. Со словарем у вас может быть либо отдельный словарь, связанный с узлом (ключом) с его значением, либо, если значение достаточно маленькое, например IPv4, и оно уникально, вы можете просто использовать его как ключ.
Нет, ничто не мешает вам использовать значения словаря в качестве собственной структуры данных или кортежа. Только ключи должны быть типа, который можно хэшировать.
Кроме того, если вместо букв для ключей вы используете индексы (0, 1, 2), вы можете преобразовать свой словарь в список, чтобы получить лучшее из обоих миров (запрос произвольного узла O (1) без штрафов за вставку).
Спасибо за объяснение и советы по оптимизации. Об использовании двух словарей, одного для соединений и одного для его значений - что, если я не могу централизованно хранить данные в одном словаре? Например, если каждый узел является сервером, данные, связанные с каждым узлом, будут локальными для каждого узла. Является ли использование узловых объектов единственным решением в этом случае?