Плюсы и минусы определения графа как вложенных узловых объектов по сравнению со словарем?

Я практикую пару алгоритмов (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-адресом, кешем и т. д.), в то время как словарь, вероятно, полезен только для изучения структуры графа. Это верно?

Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
0
67
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Каковы преимущества пространственной и временной сложности при построении графов с использованием узловых объектов по сравнению со словарями?

С точки зрения пространства сложность одинакова для обоих. Но с точки зрения времени у каждого есть свои преимущества.

Как вы сказали, если вам нужно запросить конкретный узел, лучше использовать словарь с запросом O (1). Но если вам нужно добавить узлы, версия с графом имеет только временную сложность O (1), в то время как словарь имеет амортизированную временную сложность O (1), становясь O (n), когда требуется расширение.

В целом, думайте о сравнении как о ArrayList и LinkedList, поскольку принципы одинаковы.

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

Моя непосредственная интуиция подсказывает, что использование объектов позволит вам сделать что-то гораздо более сложное (например, каждый узел, представляющий сервер, с IP-адресом, mac-адресом, кешем и т. д.), в то время как словарь, вероятно, полезен только для изучения структуры графа. Это верно?

Нет. Со словарем у вас может быть либо отдельный словарь, связанный с узлом (ключом) с его значением, либо, если значение достаточно маленькое, например IPv4, и оно уникально, вы можете просто использовать его как ключ.

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

ring0-collections 09.02.2023 01:22

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

Pedro Cavalheiro 09.02.2023 06:05

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

Pedro Cavalheiro 09.02.2023 06:19

Другие вопросы по теме