Выбор реализации C направленного графа

Question

Добро пожаловать mon amie ,

В моей домашней работе я чувствую необходимость использовать Graph ADT.Тем не менее, я хотел бы получить его, как бы сказать, generic .То есть я хочу хранить в нем все, что мне захочется.

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

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

Но опять же, нам нужночтобы связать узел с его списком соседних узлов, , а как насчет хеш-таблицы?

Можете ли вы помочь мне решить, в какой структуре данных (связанный список, дерево, хеш-таблица) следуетхранить узлы?

Answer 1

... График АДТ. Тем не менее, я хотел бы иметь его, как бы сказать, универсальный. То есть я хочу хранить в нем все, что мне захочется.

В этом и заключается смысл ADT (абстрактный тип данных).

---

Относительно того, какую структуру данных использовать, вы можете использовать любой. Для набора узлов, Hash table будет хорошим вариантом (если у вас есть хорошая реализация на C). Вы будете иметь амортизированный доступ O (1) к любому узлу. A LinkedList займет наихудший случай O (n), чтобы найти узел, a Balanced Tree будет O (logn) и не даст вам никакого преимущества над хеш-таблицей, если по какой-то причине вы не отсортируете набор ноды LOT (в этом случае с использованием обхода дерева по порядку сортируется и за O (n) время)

Что касается списков смежности для каждого узла, это зависит от того, что вы хотите сделать с графом. Если вы будете реализовывать только, скажем, DFS и BFS, вам нужно выполнить итерацию по всем соседям определенного узла, поэтому LinkedList - самый простой способ, и его достаточно.

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

A LinkedList соседних узлов может быть достаточно, это зависит от того, что вы собираетесь делать.

Answer 2

Если вам нужно знать, какие узлы соседствуют друг с другом, вы можете использовать матрицу смежности . Другими словами, для графа n узлов у вас есть матрица n x n, чья запись для (i,j) равна 1, если i и j находятся рядом друг с другом на графике.