Werkt het tegenovergestelde van Kruskal’s algoritme voor minimale opspannende boom daarvoor? Ik bedoel, bij elke stap het maximale gewicht (rand) kiezen?
Enig ander idee om de maximale opspannende boom te vinden?
Antwoord 1, autoriteit 100%
Ja, dat doet het.
Eén methode voor het berekenen van de maximale gewichtsspanningsboom van een netwerk G –
vanwege Kruskal – kan als volgt worden samengevat.
- Sorteer de randen van G in afnemende volgorde op gewicht. Laat T de verzameling randen zijn die de maximale gewichtsspanboom omvat. Stel T = in.
- Voeg de eerste rand toe aan T.
- Voeg de volgende rand toe aan T als en slechts als het geen cirkel in T vormt. Als
er zijn geen overblijvende randen verlaten en melden dat G moet worden losgekoppeld.- Als T n−1 randen heeft (waarbij n het aantal hoekpunten in G is), stop en
uitgang T. Ga anders naar stap 3.
Bron: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf.
Antwoord 2, autoriteit 58%
Van Maximum Spanning Treebij Wolfram MathWorld:
“Een maximaal opspannende boom is een opspannende boomvan een gewogen grafiek met een maximaal gewicht. Het kan worden berekend door de gewichten voor elke rand te negeren en Kruskal’s algoritme(Pemmaraju en Skiena, 2003, p. 336).”
Antwoord 3, autoriteit 8%
Als je het gewicht op elke rand omkeert en minimaliseert, krijg je dan de maximale opspannende boom? Als dat werkt, kun je hetzelfde algoritme gebruiken. Nulgewichten zullen natuurlijk een probleem zijn.
Antwoord 4, autoriteit 5%
Hoewel deze draad te oud is, heb ik een andere aanpak voor het vinden van de maximale spanningstructuur (MST) in een grafiek G = (v, e)
We kunnen het algoritme van sommige soorten Prim toepassen voor het vinden van de MST. Daarvoor moet ik gesneden eigendom definiëren voor de maximale gewogen rand.
Cut Property: Laten we zeggen op elk moment dat we hebben een set S die de hoekpunten bevat die in MST zijn (dat het nu aanneemt dat het op de een of andere manier wordt berekend). Overweeg nu de set S / V (hoekpunten niet in MST):
Claim: de rand van S tot S / V die het maximale gewicht heeft, zal altijd in elke MST zijn.
Bewijs: laten we zeggen dat op een punt wanneer we de hoekpunten toevoegen aan onze set S de maximale gewogen rand van S tot S / V is E = (U, V) waar u in S en V zit in S / V V. Overweeg nu een mst die geen e bevat. Voeg de Edge E aan de MST toe. Het maakt een cyclus in de originele MST. Doorkruisen de cyclus en vind de hoekpunten U ‘in S en V’ in S / V zodanig dat U ‘de laatste vertex in S zit, waarna we S / V en V’ betreden, is de eerste vertex in S / V op het pad in cyclus van u naar v.
Verwijder de rand E ‘= (U’, V ‘) en de resulterende grafiek is nog steeds verbonden, maar het gewicht van E is groter dan E’ [zoals E is de maximale gewogen rand van S tot S / V op dit punt ] Dus dit resulteert in een mst die som is van gewichten groter dan originele MST. Dus dit is een tegenstrijdigheid. Dit betekent dat Edge E in elke MST moet zijn.
Algoritme om MST te vinden:
Start vanaf s = {s} // s is de start vertex
terwijl s niet alle hoekpunten bevat
doen
{
Voor elke vertex s in s
Voeg een vertex v toe van S / V zodanig dat gewicht van rand E = (S, V) maximaal is
}
eindigen terwijl
Implementatie:
we kunnen implementeren met behulp van Max Heap/Priority Queue waarbij de sleutel het maximale gewicht is van de rand van een hoekpunt in S naar een hoekpunt in S/V en de waarde het hoekpunt zelf is. Het toevoegen van een hoekpunt in S is gelijk aan Extract_Max from the Heap en bij elke Extract_Max verandert de sleutel van de hoekpunten naast het zojuist toegevoegde hoekpunt.
Er zijn dus m Change_Key-bewerkingen en n Extract_Max-bewerkingen nodig.
Extract_Min en Change_Key kunnen beide worden geïmplementeerd in O(log n). n is het aantal hoekpunten.
Dit kost dus O(m log n) tijd. m is het aantal randen in de grafiek.
Antwoord 5, autoriteit 3%
Laat me een verbeteringsalgoritme geven:
- maak eerst een willekeurige boomstructuur (met BFS of DFS)
- kies dan een rand buiten de boom, voeg toe aan de boom, het zal een cyclus vormen, laat de kleinste gewichtsrand in de cyclus vallen.
- ga hiermee door totdat alle overige randen worden overwogen
Zo krijgen we de maximale opspannende boom.
Deze boom voldoet aan elke rand buiten de boom, indien toegevoegd vormt deze een cyclus en de rand buiten <= alle randgewichten in de cyclus
In feite is dit een noodzakelijke en voldoende voorwaarde voor een opspannende boom om een maximale opspannende boom te zijn.
Pf.
Noodzakelijk: het is duidelijk dat dit nodig is, anders kunnen we de rand verwisselen om een boom te maken met een groter aantal randgewichten.
Voldoende: stel dat boom T1 aan deze voorwaarde voldoet en T2 de maximaal opspannende boom is.
Voor de randen T1 ∪ T2 zijn er alleen randen T1-, alleen T2-randen, T1 ∩ T2-randen, als we een rand met alleen T1 (x1, xk) toevoegen aan T2, weten we dat deze zal vormen een cyclus, en we beweren, in deze cyclus moet er één T2-only rand zijn die dezelfde randgewichten heeft als (x1, xk). Dan kunnen we deze randen verwisselen en een boom produceren die nog een rand gemeen heeft met T2 en dezelfde som van randgewichten heeft, als we dit herhalen, krijgen we T2. dus T1 is ook een maximaal opspannende boom.
Bewijs de bewering:
stel dat het niet waar is, in de cyclus moeten we een T2-only edge hebben, aangezien T1 een boom is. Als geen van de alleen-T2-randen een waarde heeft die gelijk is aan die van (x1, xk), dan maakt elk van de alleen-T2-randen een lus met boom T1, dan heeft T1 een lus leidt tot een contradictie.
Dit algoritme is ontleend aan de aantekeningen van UTD-professor R. Chandrasekaran. U kunt hier verwijzen: Single Commodity Multi-terminal Flows
Antwoord 6
Negeer het gewicht van de originele grafiek en bereken de minimale opspannende boom op de ontkende grafiek geeft het juiste antwoord. Dit is waarom: Voor dezelfde opspannende boom in beide grafieken is de gewogen som van de ene grafiek de negatie van de andere. Dus de minimum opspannende boom van de ontkende graaf zou de maximum opspannende boom van de originele moeten geven.
Antwoord 7
Alleen het omkeren van de sorteervolgorde en het kiezen van een zware rand in een hoekpuntsnede garandeert geen bos met maximale overspanning (het algoritme van Kruskal genereert bos, geen boom). In het geval dat alle randen een negatief gewicht hebben, zou het Max Spanning Forest verkregen uit de achterkant van kruskal nog steeds een negatief gewichtspad zijn. Het ideale antwoord is echter een woud van losgekoppelde hoekpunten. d.w.z. een bos van |V| singleton bomen, of |V| componenten met een totaal gewicht van 0 (niet de minste negatieve).
Antwoord 8
Verander het gewicht in een gereserveerde volgorde (u kunt dit bereiken door een negatieve gewichtswaarde te nemen en een groot aantal toe te voegen, waarvan het doel is om niet-negatief te verzekeren) Voer vervolgens uw familie-geedy-gebaseerde algoritme uit op de minimale opspannende boom.