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

Question

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

У нас есть 5 узлов

t1
t2
a0
a1

t1 connects to a0 and a3
t2 connects to a0, a1, a2 and a3
a0 connects to a1
a1 connects to a0, t2

Моя конечная цель - создать программу, которая будет Нарисуйте связи между узлами, а также узлами, используя графическую библиотеку.

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

Answer 1

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

• Если соотношение низкое (много узлов с относительно небольшим количеством соединений), тогда график будет разреженным . Хорошей структурой данных для представления разреженных графов является список смежностей .
• Если отношение высокое (множество узлов, каждый из которых соединяется, скажем, с четвертью другие узлы), тогда граф является плотным . Хорошим представлением плотных графов является матрица смежности .