Алгоритм рисования графиков без проверки всех пар вершин?
Алгоритмы рисования графа, такие как описанные здесь, проверяют все вершины два на два и применяют дополнительные силы, если две вершины соединены ребром. Если у нас очень большой граф, проверка всех пар вершин будет дорогостоящей. Существует ли какой-либо алгоритм рисования графа, который рисует большой граф, используя только существующие ребра, а не проверяя все возможные пары?
РЕДАКТИРОВАТЬ
Под алгоритмом рисования я имел в виду алгоритм, который назначает двухмерную или трехмерную позицию каждой вершине, так что рендеринг сфер или окружностей (или любой другой формы) в виде вершин в назначенных им позициях приводит к правдоподобному визуальному представлению всего графа.
2 ответа
Проверьте это Весенне-Электрическое Вложение Это в O(nlog n).
Если у вас есть разреженная матрица, вы можете подумать о создании графа в виде списка соседей или просто как пара вершин (например, (1, 3) и 1 и 3 - это число вершин).