Создание быстрого словаря

Question

Для школьной задачи я должен создать график и сделать с ним кое-что. На входе каждая вершина имеет идентификатор, который является номером 0-999'999'999. Поскольку я не могу создать массив так долго, я не могу использовать этот идентификатор в качестве ключа в матрице смежности. Моим первым решением было создать отдельный идентификатор, который является произвольным исходным, и хранить его в каком-то словаре/карте, но по мере того, как я получаю 10 000 записей вершин, поиск, вероятно, должен замедляться. Алгоритм должен быть под O (n^2), и у меня уже есть BFS и топопорт. Что было бы лучшим решением в этом случае? В качестве побочного примечания - я не могу использовать уже установленные библиотеки (поэтому я не могу использовать граф, карту, вектор, классы строк и т. Д.), Но я могу сам их кодировать, если это лучший вариант.

Answer 1

Что вы хотите бинарное дерево поиска, чтобы сделать поиски в O(logn) времени или хэш-карта, чтобы сделать поиски в ~O(1) времени или вы можете пойти с маршрутом массива, в этом случае размер вашего массива будет максимальное значение вашего ID может иметь (в вашем случае, 10^9).

Как сказал вам @amit, проверьте деревья AVL/Red-Black и хеш-карты. Нет лучшего способа сделать поиск в графе ниже O(n), если вы не можете изменить топологию графика, чтобы превратить его в «график поиска».

Answer 2

Зачем вам нужно создать массив размером 1 миллиард. Вы можете просто создать матрицу смежности или список смежности количества узлов.

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

Рассмотрим этот граф, неужели вы думаете, что вам нужно иметь 10^10 элемент в списке смежности вместо 4-х элементов?