#python #networkx #graph-theory
Вопрос:
Рассмотрим график, на котором у нас есть несколько сегментов, которые не связаны друг с другом. Я хотел бы найти, где мне нужно добавить новые ребра, чтобы сделать график полностью связанным. Я бы хотел свести длину каждого нового ребра к минимуму. Бонус, если алгоритм также возвращает длину каждого добавляемого ребра.
Существующий график
Предложенное решение
Комментарии:
1. Вы уверены, что хотите, чтобы график был полностью подключен, а не просто подключен?
2. Звучит как 3 концептуальных шага: 1. определите, что такое подключенные компоненты (это O(v)), 2. найдите кратчайший путь между каждой парой подключенных компонентов (очевидное решение-O(n*m), где n и m — количество вершин в подграфах, но может быть почти линейным, используя карту на основе местоположения), 3. используйте алгоритм Prim для создания минимального связующего дерева (рассматривая каждый подключенный компонент как узел) — это в основном линейно, если вы правильно выбираете структуры данных.
3. Мне непонятно, что вы имеете в виду, делая края короткими. Это говорит о том, что существует базовая геометрия, о которой вы не упомянули.
4. Что вы пробовали до сих пор? У вас есть примерная сеть?
5. 1. Извините, он должен быть просто подключен, а не полностью подключен. 2. Делая края короткими, я имею в виду, что хочу соединить сегменты в самых узких промежутках между ними. 3. Я попробовал networkx, где я перебираю строки GeoJSON и создаю из них график. Это приводит к множеству
connected_components.