Я работаю с неориентированным графом, и на определенной стадии конвейера я стремлюсь найти максимальное связующее дерево (MST).Проблема в том, что у нас есть некоторые шумные вершины, которые мы можем обнаружить на основе самого MST.Поэтому, когда MST вычисляется, мы можем обнаружить некоторые вершины как шум и удалить их.
Таким образом, мы получаем лес, но это не обязательно максимальный остов / дерево / лес, если граф обрезан по шуму.Я могу пересчитать MST графика (с удаленными шумными вершинами), но это занимает время.Еще один вариант - использовать частичные остовные деревья, оставшиеся после удаления шума, и попытаться соединить их с максимальными остовами.
Я знаю, что если я начну с остаточного леса, это не обязательно приведет к MST, но это будет приближение к тому, что мне нужно, поэтому не стоит беспокоиться в этом смысле.
Как вы знаете, алгоритм Крускала является прогрессивным и добавляет ребра (упорядоченный вес) в MST, если это действие не делает цикл.Мне интересно, существует ли простой способ или существует реализованная версия в Networkx, которая может принять частично вычисленное связующее дерево и завершить его на основе графика или нет.
Функция, которую я сейчас использую:
import networkx as nx
gmst = nx.maximum_spanning_tree(g, weight="n")
noisy_vertices = detect_noisy_vertices(gmst)
gmst.remove_nodes_from(noisy_vertices)
# gmst is now a forest and based on kruskal it could continue to
# add edges to make an approximately maximum spanning tree
detect_noisy_vertices(gmst) возвращает список вершин шума, основанный на некоторых условиях, не связанных с этим вопросом.
Спасибо.