MST в unDirected графе с удаленным краем [duplicate]
Вы объявили «список» как «свойство уровня класса», а не «свойство уровня экземпляра». Чтобы иметь свойства, определенные на уровне экземпляра, вам необходимо инициализировать их путем ссылки с параметром «self» в методе __init__ (или в другом месте в зависимости от ситуации).
Вы не строго нужно инициализировать свойства экземпляра в методе __init__, но это упрощает понимание.
1 ответ
Просто выполните поиск пути минимальной дистанции теперь отсоединенной части дерева к остальной части дерева и добавьте этот путь между ними - это единственный край.
Скажем, что ваше исходное дерево - T. С удалением края он теперь разбивается на деревья T1 и T2.
Возьмите один из них - скажем, T2. Каждое ребро, инцидентное узлу на T2, либо находится на T2, либо является одним соединением T2 с T1. Среди этих ребер, инцидентных узлу на T2, выберите тот, который ((имеет другой конец в узле T1) и (имеет минимальную стоимость среди всех таких ребер)). Найти это ребро, скажем, e = (u, v), принимает время O (| E |). O (| N |), если отделенная часть представляет собой лист.
, если бы существовало дерево, скажем T ', с меньшей стоимостью, чем T1 \ union T2 \ union {e}, то узловые множества N1 и N2 из T1 и T2 будут иметь больше межсоединений, чем просто один ребро,
, т. е. было бы два или более ребер на T ', которые начинаются с узла в N1 и заканчиваются на узле в N2. В противном случае ((T1 и T2 являются минимальными связующими деревьями с последующим увеличением по N1 и N2) и (e является наименее дорогостоящей связью между T1 и T2)) будет ложным. Но тогда любой промежуточный T1 и T2 дороже, чем e = (u, v) - противоречит.
Пропустили некоторые подробности проверки. надеюсь это поможет.
-
1– Alin Ciocan 2 December 2012 в 18:36
-
2– ashley 3 December 2012 в 01:01
-
3– Michael Dotson 26 February 2014 в 19:46