Мне нужно реализовать алгоритм, который работает на плоских графах, и я хочу выбрать подходящую структуру данных для их представления.
Вершины хранятся в массиве, каждый из которых имеетсвязанная пара координат,
Ребро имеет связанную ломаную линию между своими конечными вершинами с произвольным числом промежуточных точек (возможно, ни одной), сохраненных в последовательности во вспомогательном массиве.
Ребра ненаправленные (если a => b существует, то b => a существует),
Должны поддерживаться следующие примитивные операции:
добавление ребра между двумя вершинами, обозначенными их индексами,
перечисление всех ребер, происходящих из данной вершины (и рекурсивно, все пути иззаданной вершины),
для заданного ребра, следуйте соответствующей полилинии до конечной вершины.
Iищу структуру данных, которая является космической EFВеличина O (V + E) и позволяет избежать избыточности данных.
Что бы вы использовали?Кандидатами, которых я вижу, являются списки смежности , DCEL , крылатые ребра , но я могу пропустить один.Я думаю, что четырехугольные ребра излишни.