Wikipedia - Benutzerbeiträge [de]

Andor

2022-11-27T15:18:00Z

Optimalsloth: /* Staffel 1 */ Typos

{{Infobox Fernsehsendung
| Bild = Andor-logo-schwarz.png
| Deutscher Titel = Andor
| Originaltitel = Andor
| Produktionsland = Vereinigte Staaten
| Erstausstrahlungsjahre = seit 2022
| Produzent = [[Kate Hazell]], [[David Meanti]]
| Produktionsunternehmen = [[Lucasfilm]], [[The Walt Disney Company|Walt Disney Studios]]
| Länge = 38–57
| Episoden = 12
| Staffeln = 1+
| Originalsprache = Englisch
| Musik = [[Nicholas Britell]]
| Kamera = [[Adriano Goldman]], [[Frank Lamm]], [[Damián García]], [[Jonathan Freeman (Kameramann)|Jonathan Freeman]]
| Schnitt = [[John Gilroy]], [[Tim Porter]], [[Hazel Baille]], [[Dan Roberts]], [[Frances Parker]], [[Matthew Cannings]], [[Simon Smith (Filmeditor)|Simon Smith]], [[Yan Miles]]
| Titellied =
| Idee = [[Tony Gilroy]]
| Genre = [[Space Opera]], [[Thriller]], [[Drama (Filmgenre)|Drama]]
| Premiere = 21. September 2022
| Sender = [[Disney+]]
| Premiere_DE = 21. September 2022
| Sender_DE = Disney+
| Besetzung = 1
| Synchronisation = 1
}}

'''Andor''', auch '''Star Wars: Andor''' ist eine [[Vereinigte Staaten|US-amerikanische]] [[Space Opera|Space-Opera]]-Serie von [[Tony Gilroy]], die am 21. September 2022 auf dem [[Streaming Media|Streaming]]-Portal [[Disney+]] startete. Die Serie ist Teil des ''[[Star Wars|Star-Wars]]''-Universums von [[George Lucas]] und erzählt die Vorgeschichte des Kinofilms ''[[Rogue One: A Star Wars Story]]'' (2016). In der titelgebenden Hauptrolle ist [[Diego Luna]] als Rebellen-Kapitän und Spion [[Figuren aus Star Wars#Cassian Andor|Cassian Andor]] zu sehen.

Die erste Staffel umfasst 12 Episoden. Eine zweite und zugleich letzte Staffel befindet sich bereits in Produktion.

== Handlung ==
{{Siehe auch|Andor (Fernsehserie)/Episodenliste}}
Die Serie folgt dem späteren Rebellen Cassian Andor und erzählt die Anfänge der sich bildenden Rebellenallianz und dem Wandel der Figur vom verruchten Gesetzlosen, bis hin zu einem loyalen Kämpfer der Rebellion, der später zu seinem Heldentod bei der Beschaffung der [[Todesstern]]-Baupläne führt. Andor steht im Fokus der Handlung, wobei verschiedenen Nebenhandlungen diverse weitere Figuren und deren Geschichten begleiten, und das alltägliche Leben in der Galaxis unter der Terrorherrschaft des Galaktischen Imperiums beleuchtet.

=== Staffel 1 ===
Die Serie setzt fünf Jahre vor der [[Krieg der Sterne|Schlacht von Yavin]] und somit 14 Jahre nach der Umformung der Galaktischen Republik zum Galaktischen Imperium durch [[Figuren aus Star Wars#Sheev Palpatine/Darth Sidious|Imperator Palpatine]] an.

Zu Beginn sucht [[Figuren aus Star Wars#Cassian Jeron Andor|Cassian Andor]] auf der Hauptwelt des Preox-Morlana-Sicherheitskonzerns, einer vom Imperium unabhängig agierenden privaten Sicherheitsfirma, nach seiner Schwester. Diese hat er seit seiner Kindheit nicht mehr gesehen, da das Imperium mit der Zeit ihren Heimatplaneten Kenari ausgebeutet hat, wobei er schließlich von der Plünderin Maarva Andor mitgenommen wird, als sich die Situation dort verschärft. Seine Suche verläuft jedoch suboptimal, da er zwei Mitarbeiter des Konzerns tötet und fortan flüchtet.

Dies ruft den dem Sicherheitskonzern angehörigen [[Figuren aus Star Wars#Syril Karn|Inspektor Syril Karn]] auf den Plan, der mit einer kleinen Gruppe an Soldaten Cassians Spur auf den Planeten Ferrix zurückverfolgt. Dort leben auch die mittlerweile gesundheitlich angeschlagene Maarva und die Mechanikerin Bix Caleen, die für Cassian den Kontakt zu einem mysteriösen Käufer herstellt, da dieser eine imperiale Starpath-Einheit erbeuten konnte.
Der Käufer tritt Cassian tatsächlich gegenüber und beide entkommen knapp, wobei ein großer Teil von Syrils Soldaten ums Leben kommt und dieses Ereignis ihn fassungslos zurücklässt.

Als Konsequenz wird der Konzern dem Imperium unterstellt und Cassian willigt in das Angebot des Käufers ein, an einem Diebstahl teilzunehmen. Dieser findet auf dem Planeten Aldhani statt, wobei es der Gruppe nach anfänglichen Reibereien gelingt, diesen durchzuführen und sie den Quartalslohn eines ganzen imperialen Sektors erbeuten können. Dabei überleben nur Cassian sowie die Anführerin der Gruppe Vel Sartha und Cinta Kaz; während jene eigene Wege gehen, taucht Cassian unter falschem Namen mit seinem Anteil auf der tropischen Welt Niamos unter, wird dort aber (ohne erkannt zu werden) zu sechs Jahren Gefängnis verurteilt.

Der Diebstahl auf Aldhani erregt wiederum die Aufmerksamkeit der Imperialen Sicherheitsbehörde (ISB) und [[Figuren aus Star Wars#Wullf Yularen|Colonel Wullf Yularen]], wobei letzterer höhere Strafen und drastische Maßnahmen als Folge dessen ankündigt. Derweil glaubt die aufstrebende Supervisorin [[Figuren aus Star Wars#Dedra Meero|Dedra Meero]], in mehreren scheinbar zufällig geschehenen Ereignissen eine geplante Rebellion zu erkennen, stößt aber beim Vorgesetzten Major Partagaz auf Unverständnis. Mit der Zeit gelingt es ihr jedoch dessen Anerkennung zu gewinnen und sie erkennt schließlich einen Mittelpunkt in den Aktionen, einen Fremden mit dem Codenamen ''Axis''. Da Derdra überzeugt ist, dass Bix Informationen über Axis' Aufenthaltsort und Identität besitzt, lässt sie Bix u. a. mit den Schreien von durch das Imperium ermordeten Kindern foltern.

Der mysteriöse ''Axis'' heißt eigentlich [[Figuren aus Star Wars#Luthen Rael|Luthen Rael]] und führt ein Doppelleben als Rebell und Antiquitätenhändler auf [[Orte aus Star Wars#Coruscant|Coruscant]], von dem nur seine Mitarbeiterin Kleya Marki weiß; zudem hat er mit Supervisor Lonni Jung einen Spion in den Reihen der ISB. Da Cassian verschwunden ist, ist Kleya besorgt, dass er Luthens Identität offenlegen könnte, und befiehlt Vel die Ermordung von Cassian. Luthen wiederum sucht Unterstützung beim Widerstandskämpfer und Partisanen [[Figuren aus Star Wars#Saw Gerrera|Saw Gerrera]], der ihn zu dessen Enttäuschung abweist; beide können sich dennoch darauf einigen, dass sie eine andere Rebellengruppe opfern müssen, damit sie überleben können.

Parallel versucht [[Figuren aus Star Wars#Mon Mothma|Senatorin Mon Mothma]] durch die politischen Intrigen zu navigieren, denen nicht einmal ihre Familie entkommen kann, zumal ihr (arrangierter) Ehemann Perrin Fertha sie wenig dabei unterstützt. Da die Gelderverschiebung zwischen ihr und Luthen immer schwieriger wird, wendet sie sich an ihren alten Freund, den Banker Tay Kolma, der ihr auch nur begrenzt helfen kann. Die Probleme hingegen spitzen sich zu, sodass sie Hilfe vom chandrilanischen Gangster Davo Sculdun ersucht, der als Gegenleistung ein Treffen zwischen ihren Kindern fordert, das zu einer Zwangsheirat führen soll. Später gelingt es ihr zudem, ihrem Fahrer, der sie für den ISB ausspionieren soll, weiszumachen, dass ihr Mann das Geld aufgrund seiner Spielsucht verschleudert.

Cassian wird zur gleichen Zeit auf dem Planeten Narkina 5 auf einer sterilen Gefängnisinsel festgehalten, wo er mit anderen Gefangenen technische Apparaturen für einen unbekannten Zweck zusammenbaut. Nach einiger Zeit gelingt es ihm, den Vorarbeiter Kino Loy auf seine Seite zu bringen, ehe er mit diesem und anderen eine Gefängnisrevolte in Gang setzt. Cassian und Ruescott Melshi, einem weiteren Gefangenen, gelingt die Flucht, wobei Kino freiwillig zurückbleibt, da er nicht schwimmen, und somit den im Wasser liegenden Gefängniskomplex nicht verlassen kann.

Nach Maarvas Tod richtet sich alle Aufmerksamkeit auf Ferrix, da Dedra dort ''Axis'' vermutet und Luthen sowie Vel und Cinta planen, Cassian zu töten, während Syril ihn ebenfalls aufspüren möchte. Während des großen Trauermarsches spielt Maarvas und Cassians Droide eine von ihr aufgezeichnete Nachricht ab, in der sie die Bewohner zur Bekämpfung des Imperiums aufruft. Ein imperialer Captain macht jedoch einen Fehler, indem er die Übertragung zu unterbinden versucht, was eine Straßenschlacht auslöst. Dabei wird Dedra um ein Haar getötet, aber von Syril gerettet, und Cassian befreit die inhaftierte Bix. Nachdem er seinen Freunden hilft, von Ferrix zu entkommen, stellt er Luthen vor die Wahl, ihn umzubringen oder einsteigen zu lassen.

Zeitgleich ist im Orbit von [[Orte aus Star Wars#Scarif|Scarif]] der erste [[Todesstern]] fast fertiggestellt, wobei die Arbeiten der Gefangenen von Narkina 5 zu ihrer Unkenntnis in das noch im Bau befindliche Laser-Modul überführt werden.

== {{Anker|Besetzung|Synchronisation}} Besetzung und Synchronisation ==
[[Datei:Diego Luna Berlinale 2017.jpg|mini|hochkant|Hauptdarsteller [[Diego Luna]], 2017]]
In der titelgebenden Hauptrolle ist [[Diego Luna]] zu sehen, welcher die Rolle zum zweiten Mal verkörpert. Weitere tragende Rollen umfassen [[Adria Arjona]] als Mechanikerin Bix Caleen, [[Stellan Skarsgård]] als Rebellen-Sympathisant Luthen Rael und [[Kyle Soller]] sowie [[Denise Gough]] als Gegenspieler Syril Karn, der dem imperialen Sicherheitskonzern Preox-Morlana angehört, und Lieutenant Dedra Meero, eine Angehörige der ISB.

Zudem sind [[Fiona Shaw]] als Cassians Adoptivmutter Maarva Andor, [[Joplin Sibtain]] als Brasso, [[Alex Ferns]] als Karns Stellvertreter Sergeant Linus Mosk sowie [[Ben Miles (Schauspieler)|Ben Miles]] als Tay Kolma, ein Banker und Verbündeter von Senatorin Mon Mothma, zu sehen.

Diese wird nach ''[[Star Wars: Episode III – Die Rache der Sith|Episode III]]'' und ''Rogue One'' zum dritten Mal von [[Genevieve O’Reilly]] gespielt, die sie ebenfalls in ''[[Star Wars Rebels|Rebels]]'' sprach. [[Malcolm Sinclair]] verkörpert Colonel Wullf Yularen, eine weitere Figur aus den Animationsserien ''[[Star Wars: The Clone Wars (Fernsehserie)|The Clone Wars]]'' und ''Rebels'', die hier ihr zweites Live-Action-Debüt feiert und vorher von [[Tom Kane (Synchronsprecher)|Tom Kane]] gesprochen bzw. in ''Episode IV'' von [[Robert Clarke (Schauspieler)|Robert Clarke]] gespielt wurde. [[Forest Whitaker]] porträtiert erneut Saw Gerrera, den er bereits in mehreren anderen ''Star-Wars-''Medien verkörperte bzw. sprach, während [[Duncan Pow]] seine Rolle aus ''Rogue One'' wieder aufnahm.

Die deutschsprachige Synchronfassung entsteht nach [[Dialogbuch|Dialogbüchern]] von [[Klaus Bickert]], [[Markus Jütte]], [[Christian Langhagen]], [[Laura Johae]] und [[Björn Schalla]] sowie unter der [[Dialogregie]] von Schalla und [[Birte Baumgardt]] bei [[FFS Film- & Fernseh-Synchron]] in Berlin.

[[Marcel Collé]], [[Björn Schalla]] und [[Tobias Meister]] übernahmen ihre jeweiligen Rollen aus ''Rogue One'', wie auch [[Erich Räuker]] seine aus den Animationsserien. Für Mon Mothma wurde erneut [[Alexandra Lange]] verpflichtet, welche die Figur erstmals in ''Die Rückkehr der Jedi-Ritter'' sprach.
{| class="wikitable"
! Rollenname
! Darsteller
! Porträt
! Hauptrolle (Episoden)
! Nebenrolle (Episoden)
! Gastrolle (Episoden)
! Synchronsprecher<ref>{{Synchronkartei|serie|53096|Abruf=2022-09-26}}</ref>
|-
| rowspan="3" | [[Figuren aus Star Wars#Cassian Andor|Cassian Jeron Andor]] / Kassa
| [[Diego Luna]]
| [[Datei:Diego Luna - Lucca Comics & Games 2018 01.jpg|75x75px]]
| 1.01–
|
|
| [[Marcel Collé]]
|-
| [[Antonio Viña]] (Kind)
|
|
| 1.01–1.03
|
| rowspan="2" | –{{FN|1}}
|-
| [[Lucas Bond]] (jung)
|
|
|
| 1.07, 1.12
|-
| Inspektor [[Figuren aus Star Wars#Syril Karn|Syril Karn]]
| [[Kyle Soller]]
| [[Datei:Kyle Soller at The Keeping Room UK Premiere.jpg|75x75px]]
| 1.01–1.05, 1.07–1.09, 1.11–1.12
|
|
| [[Tim Kreuer]]
|-
| Bix Caleen
| [[Adria Arjona]]
| [[Datei:Adria Arjona 2022 (cropped).jpg|75x75px]]
| 1.01–1.03, 1.07–1.09, 1.11–1.12
|
|
| [[Giuliana Jakobeit]]
|-
| Brasso
| [[Joplin Sibtain]]
|
| 1.01–1.03, 1.08, 1.11–1.12
|
|
| [[Daniel Welbat]]
|-
| Timm Karlo
| [[James McArdle]]
| [[Datei:James McArdle at the London 2012 Olympics torch relay (cropped).jpg|75x75px]]
| 1.01–1.03
|
|
| [[Fabian Kluckert]]
|-
| Chefinspektor Hyne
| [[Rupert Vansittart]]
| [[Datei:Rupert Vansittart by Gage Skidmore.jpg|75x75px]]
| 1.01, 1.04
|
|
| [[Ernst Meincke]]
|-
| [[Figuren aus Star Wars#Luthen Rael|Luthen Rael]]
| [[Stellan Skarsgård]]
| [[Datei:Stellan Skarsgård 2009.jpg|75x75px]]
| 1.02–1.08, 1.10–
|
|
| [[Douglas Welbat]]
|-
| Sergeant Linus Mosk
| [[Alex Ferns]]
|
| 1.02–1.04, 1.11–1.12
|
|
| [[Dirc Simpson]]
|-
| Maarva Andor
| [[Fiona Shaw]]
| [[Datei:Fiona Shaw BAM 2011-01-16.jpg|75x75px]]
| 1.02–1.03, 1.07–1.08, 1.12
|
|
| [[Kerstin Sanders-Dornseif]]
|-
| Clem Andor
| [[Gary Beadle (Schauspieler)|Gary Beadle]]
|
| 1.03, 1.07, 1.12
|
|
| [[Sven Gerhardt]]
|-
| Senatorin [[Figuren aus Star Wars#Mon Mothma|Mon Mothma]]
| [[Genevieve O’Reilly]]
|
| 1.04–
|
|
| [[Alexandra Lange]]
|-
| Lieutenant [[Figuren aus Star Wars#Dedra Meero|Dedra Meero]]
| [[Denise Gough]]
|
| 1.04–
|
|
| [[Flavia Vinzens]]
|-
| Vel Sartha
| [[Faye Marsay]]
| [[Datei:Faye Marsay by Gage Skidmore.jpg|75x75px]]
| 1.04–1.09, 1.11–1.12
|
|
| [[Nadine Heidenreich]]
|-
| Cinta Kaz
| [[Varada Sethu]]
|
| 1.04–1.08, 1.10–1.12
|
|
| [[Franziska Trunte]]
|-
| Kleya Marki
| [[Elizabeth Dulau]]
|
| 1.04–1.08, 1.10–1.11
|
|
| [[Moira May]]
|-
| Karis Nemik
| [[Alex Lawther]]
| [[Datei:Alex Lawther.jpg|75x75px]]
| 1.04–1.06, 1.12
|
|
| [[Jonas Lauenstein]]
|-
| Lieutenant Gorn
| [[Sule Rimi]]
|
| 1.04–1.06
|
|
| [[Tim Moeseritz]]
|-
| Taramyn Barcona
| [[Gershwyn Eustace Jnr]]
|
| 1.04–1.06
|
|
| [[Thomas Wenke]]
|-
| Arvel Skeen
| [[Ebon Moss-Bachrach]]
| [[Datei:Ebon Moss-Bachrach by Gage Skidmore.jpg|75x75px]]
| 1.04–1.06
|
|
| [[Uve Teschner]]
|-
| Perrin Fertha
| [[Alastair Mackenzie]]
|
| 1.04–1.05, 1.07–1.09, 1.12
|
|
| [[Boris Tessmann]]
|-
| Eedy Karn
| [[Kathryn Hunter]]
| [[Datei:Kathryn Hunter (cropped).jpg|75x75px]]
| 1.04–1.05, 1.07, 1.09, 1.11
|
|
| [[Karin David]]
|-
| Major Partagaz
| [[Anton Lesser]]
| [[Datei:Anton Lesser (2011).jpg|75x75px]]
| 1.04, 1.06–1.10, 1.12
|
|
| [[Detlef Gieß]]
|-
| Kommandant Jayhold Beehaz
| [[Stanley Townsend]]
|
| 1.06
|
|
| [[Klaus-Dieter Klebsch]]
|-
| Tay Kolma
| [[Ben Miles (Schauspieler)|Ben Miles]]
|
| 1.07–1.10
|
|
| [[Uwe Büschken]]
|-
| Ruescott Melshi
| [[Duncan Pow]]
|
| 1.08–1.11
|
|
| [[Björn Schalla]]
|-
| Kino Loy
| [[Andy Serkis]]
| [[Datei:Andy Serkis by Gage Skidmore 2.jpg|75x75px]]
| 1.08–1.10
|
|
| [[Lutz Schnell]]
|-
| [[Figuren aus Star Wars#Saw Gerrera|Saw Gerrera]]
| [[Forest Whitaker]]
| [[Datei:Forest Whitaker by Gage Skidmore.jpg|75x75px]]
| 1.08, 1.11
|
|
| [[Tobias Meister]]
|-
| Davo Sculdun
| [[Richard Dillane]]
|
| 1.10, 1.12
|
|
| [[Pierre Peters-Arnolds]]
|-
| B2EMO
| [[Dave Chapman (Schauspieler)|Dave Chapman]] (Stimme)
|
|
| 1.01–1.03, 1.07–1.08, 1.11–1.12
|
| [[Otto Strecker (Schauspieler)|Otto Strecker]]
|-
| Wilmon Paak
| [[Muhannad Bhaier]]
|
|
| 1.01–1.03, 1.08, 1.12
|
| [[Linus Drews]]
|-
| Salman Paak
| [[Abhin Galeya]]
|
|
| 1.01–1.03, 1.08, 1.12
|
| [[Stephan Baumecker]]
|-
| Pegla
| [[Kieran O’Brien]]
|
|
| 1.01–1.02, 1.12
|
| [[Matthias Klages]]
|-
| Lieutenant Supervisor Blevin
| [[Ben Bailey Smith]]
|
|
| 1.04–1.07, 1.12
|
| [[Timo Weisschnur]]
|-
| Leida Mothma
| [[Bronte Carmichael]]
|
|
| 1.05, 1.07–1.09, 1.11–1.12
|
| [[Yamuna Kemmerling]]
|-
| Colonel [[Figuren aus Star Wars#Wullf Yularen|Wullf Yularen]]
| [[Malcolm Sinclair]]
| [[Datei:Malcolm Sinclair at the STR Theatre Book Prize ceremony on 18 May 2011 at the Drury Lane Theatre, London.jpg|75x75px]]
|
| 1.07–1.08
|
| [[Erich Räuker]]
|-
| Flob
| [[Alex Blake (Schauspieler)|Alex Blake]]
|
|
| 1.07–1.08
|
| [[Oliver Siebeck]]
|-
| Ham
| [[Clemens Schick]]
| [[Datei:Clemens Schick Berlinale 2010 (cropped).jpg|75x75px]]
|
| 1.08–1.10
|
| Clemens Schick
|-
| Ulaf
| [[Christopher Fairbank]]
|
|
| 1.08–1.10
|
| [[Lutz Mackensy]]
|-
| Taga
| [[Tom Reed (Schauspieler)|Tom Reed]]
|
|
| 1.08–1.10
|
| [[Lasse Dreyer]]
|-
| Jembroc
| [[Brian Bovell]]
|
|
| 1.08–1.10
|
| [[Dirk Bublies]]
|-
| Xaul
| [[Josef Davies]]
|
|
| 1.08–1.10
|
| [[Tobias Nath]]
|-
| Birnok
| [[Rasaq Kukoyi]]
|
|
| 1.08–1.10
|
| [[Rezân Cheikhamous]]
|-
| Doktor Gorst
| [[Joshua James (Schauspieler)|Joshua James]]
|
|
| 1.09
|
| [[Tobias Diakow]]
|-
| Nurchi
| [[Raymond Anum]]
|
|
|
| 1.01–1.02, 1.08–1.10, 1.12
| [[Kaze Uzumaki]]
|-
| Pre-Mor-Mitarbeiter
| [[Alex Austin]]
|
|
|
| 1.01–1.02
| [[Alex Friedland]]
|-
| Vetch
| rowspan="2" | [[Ian Whyte]]
| rowspan="2" | [[Datei:Ian-whyte-2018.jpg|75x75px]]
|
|
| 1.01
| [[Matthias Friedrich]]
|-
| Moroff
|
|
| 1.08, 1.11
| –{{FN|1}}
|-
| Willi
| [[Ron Cook]]
|
|
|
| 1.02–1.03
| [[Freimut Götsch]]
|-
| Xanvan „Xan“
| [[Zubin Varla]]
|
|
|
| 1.02–1.03, 1.11–1.12
| [[Samuel Zekarias]]
|-
| Granik
| [[Kiran Shah]]
| [[Datei:Kiran Shah, 2006.jpg|rahmenlos|75x75px]]
|
|
| 1.02
| –{{FN|1}}
|-
| Attendant Heert
| [[Jacob James Beswick]]
|
|
|
| 1.04–1.12
| [[Christian Holdt]]
|-
| Kloris
| [[Lee Ross (Schauspieler)|Lee Ross]]
|
|
|
| 1.04–1.05, 1.07, 1.09, 1.12
| [[Boris Tessmann]] (1.04) [[Benjamin Kiesewetter (Schauspieler)|Benjamin Kiesewetter]] (1.05–1.07) [[Martin Schubach]] (1.09)
|-
| Supervisor Lonni Jung
| [[Robert Emms]]
|
|
|
| 1.04, 1.06–1.10, 1.12
| [[Marco Rosenberg]]
|-
| Supervisor Lagret
| [[Michael Jenn]]
|
|
|
| 1.04, 1.06–1.10, 1.12
| [[Jens-Uwe Bogadtke]]
|-
| Supervisorin Grandi
| [[Lucy Russell]]
|
|
|
| 1.04, 1.06–1.07, 1.12
| [[Maria Sumner]]
|-
| Corporal Kimzi
| [[Nick Blood]]
| [[Datei:Nick Blood (cropped).jpg|75x75px]]
|
|
| 1.05–1.06
| [[Dennis Herrmann]]
|-
| Captain Vanis Tigo
| [[Wilf Scolding]]
|
|
|
| 1.05, 1.08–1.09, 1.11–1.12
| [[Sebastian Kaufmane]]
|-
| Colonel Petigar
| [[Richard Katz (Schauspieler)|Richard Katz]]
|
|
|
| 1.06
| [[Stefan Staudinger]]
|-
| Roboda Beehaz
| [[Michelle Duncan]]
|
|
|
| 1.06
| [[Heike Beeck]]
|-
| Leonart Beehaz
| [[Alfie Todd]]
|
|
|
| 1.06
| [[Bela Baum]]
|-
| Doktor Quadpaw
| rowspan="3" | [[Aidan Cook]]
| rowspan="3" |
|
|
| 1.06
| [[Harald Effenberg]]
|-
| KX-Sicherheitsdroide
|
|
| 1.07
| Matthias Friedrich
|-
| Benthic Two-Tubes
|
|
| 1.08, 1.11
| –{{FN|1}}
|-
| Küstentruppler
| [[Sam Witwer]]
| [[Datei:Sam Witwer by Gage Skidmore.jpg|75x75px]]
|
|
| 1.07
| [[Gedeon Burkhard]]
|-
| Leevan Tenza
| [[Dilu Miah]]
|
|
|
| 1.08
| –{{FN|1}}
|-
| Kullbee Sperado
| [[Robert Nairne]]
|
|
|
| 1.08
| –{{FN|1}}
|-
| Doktor Rhasiv
| [[Adrian Rawlins]]
| [[Datei:Adrian Rawlins à Imagin'ères Toulouse.jpg|75x75px]]
|
|
| 1.09–1.10
| [[Stephan Rabow]]
|-
| Doktor Mullmoy
| [[Matt Dunkley]]
|
|
|
| 1.10, 1.12
| rowspan="2" |–{{FN|2}}
|-
| Stakun Sculdun
| [[Finley Glasgow]]
|
|
|
| 1.12
|}
{{FNZ|1|Originalton}}
{{FNZ|2|Stumm}}

== Einordnung in das ''Star-Wars''-Universum ==
Die Handlung setzt fünf Jahre vor der Erbeutung der [[Todesstern]]-Pläne, bzw. den Ereignissen von ''Rogue One: A Star Wars Story'' und damit ebenso vor ''[[Krieg der Sterne]]'' (1977) an. Dabei deckt die erste Staffel in vier Blöcken das erste Jahr ab, während die zweite Staffel die darauffolgenden vier Jahre erzählen soll.<ref name=":1">{{Internetquelle |autor=Borys Kit |url=https://www.hollywoodreporter.com/heat-vision/star-wars-cassian-andor-disney-series-adds-two-actors-1291772 |titel=‘Star Wars’: Cassian Andor Disney+ Series Adds Two Actors (Exclusive) |werk=[[The Hollywood Reporter]] |datum=2020-04-24 |sprache=en |abruf=2020-04-25}}</ref>

{{Zeitleiste Filme und Serien des Star-Wars-Universums}}

== Produktion ==
=== Entstehungsgeschichte ===
[[Datei:Tony Gilroy (7732161230).jpg|mini|275x275px|[[Tony Gilroy]], Showrunner von ''Star Wars: Andor'']]
Im November 2018 kündigte [[Lucasfilm]] an, dass die Arbeit an einer [[Prequel]]-Serie zum Film ''Rogue One: A Star Wars Story'' über die Figur Cassian Andor begonnen habe. Stilistisch sollte die Serie an einen [[Spionage]]-[[Thriller]] angelehnt sein. Als Hauptdarsteller kehrte [[Diego Luna]] zurück, der die Figur bereits im Film verkörpert hatte.<ref>{{Internetquelle |url=https://www.starwars.com/news/cassian-andor-live-action-series-announced |titel=Cassian Andor Live-Action Series Announced |werk=StarWars.com |datum=2018-11-08 |sprache=en |abruf=2019-01-04}}</ref> Als [[Showrunner]] der Serie wurde [[Tony Gilroy]] verpflichtet, nachdem zunächst berichtet wurde, dass Stephen Schiff diese Aufgabe übernehmen werde. Gilroy war als Autor bereits an der Entstehung von ''Rogue One: A Star Wars Story'' beteiligt gewesen. Schiff verblieb weiterhin Teil des Autorenteams der Drehbücher. Ebenso am Drehbuch beteiligten sich [[Dan Gilroy]] und [[Beau Willimon]]. Im Februar 2021 wurden [[Susanna White]] und Benjamin Caron als weitere Regisseure der Serie angekündigt.<ref>{{Internetquelle |autor=Jacob Fisher |url=https://discussingfilm.net/2021/02/04/ben-caron-susanna-white-set-to-direct-andor-series-exclusive/ |titel=Ben Caron & Susanna White Set To Direct ‘Andor’ Series (EXCLUSIVE) |werk=Discussing Film |datum=2021-02-04 |sprache=en |abruf=2021-02-07}}</ref>

Die Vorproduktion von ''Andor'' begann im September 2019 und einen Monat später sollte mit dem Drehen begonnen werden, nachdem Diego Luna seine Arbeit an der Serie ''[[Narcos: Mexico]]'' abgeschlossen hatte.<ref>{{Internetquelle |autor=Brent Lang |url=https://variety.com/2018/biz/news/star-wars-diego-luna-1203023798/ |titel=‘Star Wars’: Diego Luna to Lead Spinoff Series |werk=[[Variety]] |datum=2018-11-08 |sprache=en |abruf=2021-02-07}}</ref> Die Arbeiten an der Serie wurden etwa sechs Wochen nach Aufnahme der Vorproduktion aufgrund der [[COVID-19-Pandemie]] zunächst auf unbestimmte Zeit unterbrochen.<ref>{{Internetquelle |autor=Rohan Patel |url=https://www.comicbookmovie.com/tv/star_wars/cassian_andor/exclusive-cassian-andor-disney-series-had-completed-about-six-weeks-of-pre-production-prior-to-shut-down-a174467 |titel=Cassian Andor Disney+ Series had completed about six weeks of pre-production prior to shut down |werk=ComicBookMovie.com |datum=2020-04-10 |sprache=en |abruf=2020-04-25}}</ref>

=== Dreharbeiten ===
Die Dreharbeiten zu ''Andor'' begannen Ende November 2020 in den [[Pinewood Studios]] in [[London]] unter der Regie von Toby Haynes.<ref>{{Internetquelle |autor=Maggie Dela Paz |url=https://www.comingsoon.net/tv/news/1157097-cassian-andor-has-begun-filming |titel=Cassian Andor: Diego Luna Confirms Disney+ Series Has Begun Filming |werk=ComingSoon.net |datum=2020-12-04 |sprache=en |abruf=2021-02-07}}</ref> Ursprünglich sollte bereits 2019 mit dem Drehen begonnen werden, doch der Beginn der Dreharbeiten wurde zuerst verschoben und später nach dem Ausbruch der COVID-19-Pandemie 2020 erneut. Deswegen entschied sich Regisseur Tony Gilroy, für die Dreharbeiten nicht von [[Amerika]] nach [[England]] zu reisen, und die Regieführung der ersten drei Episoden der Serie ging über an Toby Haynes. Gilroy verblieb jedoch als [[Executive Producer|ausführender Produzent]] und Showrunner der Serie.<ref>{{Internetquelle |autor=Justin Kroll |url=https://deadline.com/2020/09/black-mirrors-toby-haynes-rogue-one-disney-tony-gilroy-1234582109/ |titel=‘Black Mirror’s Toby Haynes To Direct ‘Rogue One’ Spin-Off Series At Disney+ As Tony Gilroy Steps Aside As Director |werk=[[Deadline (Website)|Deadline]] |datum=2020-09-22 |sprache=en |abruf=2021-02-07}}</ref> Die Produktion wurde Anfang 2021 schließlich wieder unter strengen Hygiene-Maßnahmen fortgesetzt. Mitte August 2021 wurden die Dreharbeiten an der Serie schließlich abgeschlossen.<ref>{{Internetquelle |url=https://bespinbulletin.com/2021/08/exclusive-andor-has-finished-filming/ |titel=EXCLUSIVE: Andor has finished filming |werk=Bespin Bulletin |datum=2021-08-22 |sprache=en |abruf=2021-08-22}}</ref>

Im Februar 2022 erklärte Darsteller [[Stellan Skarsgård]], dass die Dreharbeiten zur zweiten Staffel im Herbst 2022 starten sollen.

== Veröffentlichung ==
Die erste Staffel von ''Andor'' wurde ab dem 21. September 2022 im wöchentlichen Rhythmus auf der Video-Streaming-Plattform [[Disney+]] gezeigt. Dabei konnten zum Start bereits die ersten drei Episoden abgerufen werden.<ref>{{Internetquelle |autor=Erik Pedersen, Nellie Andreeva |url=https://deadline.com/2019/08/disney-plus-programs-movies-full-list-marvel-star-wars-pixar-simpsons-streaming-service-1202594496/ |titel=Disney+ Unveils ‘Lizzie McGuire’ Sequel, ‘Muppets’ Short-Form, ‘Obi-Wan Kenobi’ At D23 – Full List Of Streaming Service’s Programming |werk=Deadline |datum=2019-08-24 |sprache=en |abruf=2021-02-07}}</ref> Die erste Staffel umfasste zwölf Episoden und endete am 23. November 2022 mit dem Staffelfinale ''Rix Road''.

== Rezeption ==
{{Rezension
|Bewertung1='''[[Rotten Tomatoes]]'''
|Bewertung1Wert=
|Bewertung2=Kritiker
|Bewertung2Wert={{Rating|9.3|10}}<ref name="RottenTomatoes">{{Rotten Tomatoes|tv/andor|Andor|abruf=2022-11-18}} {{" |Sprache=en |Text=A gritty adventure told from the ground perspective of the Empire's reign, Andor is an exceptionally mature and political entry into the Star Wars mythos – and one of the best yet.}}</ref>
|Bewertung3=Publikum
|Bewertung3Wert={{Rating|8.3|10}}<ref name="RottenTomatoes" />
|Bewertung4='''[[Metacritic]]'''
|Bewertung4Wert=
|Bewertung5=Kritiker
|Bewertung5Wert={{Rating|7.4|10}}<ref name="Metacritics">{{Metacritic|tv/andor|Andor|abruf=2022-11-18}}</ref>
|Bewertung6=Publikum
|Bewertung6Wert={{Rating|7.8|10}}<ref name="Metacritics" />
|Bewertung7='''[[Internet Movie Database|IMDb]]''' (Publikum)
|Bewertung7Wert={{Rating|8.3|10}}<ref name="IMDb">{{Internetquelle |url=https://www.imdb.com/title/tt9253284/ |titel=Andor |hrsg=[[Internet Movie Database]] (IMDb) |sprache=en |abruf=2022-11-18}}</ref>
|Bewertung8='''[[Moviepilot]]'''
|Bewertung8Wert={{Rating|7.4|10}}<ref name="moviepilot">{{Internetquelle |url=https://www.moviepilot.de/serie/star-wars-andor |titel=Andor |hrsg=[[Moviepilot]] |abruf=2022-11-18}}</ref>
}}
{{Manueller Rahmen
|content = {{Graph:Chart |width=280 |height=100 |type=rect
|xAxisTitle=Staffel 1 – Folgen |yAxisTitle=Wertung (%)
|x=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
|y=92, 89, 92, 90, 100, 100, 100, 100, 100, 100, 93
|showValues= }}
|caption = Episodenbewertung auf [[Rotten Tomatoes]]<ref name="RottenTomatoes" />
|align = right
}}

Der Aggregator [[Rotten Tomatoes]] ermittelte eine Zustimmung von 93 % auf der Grundlage von 545 Kritikerbewertungen.<ref name="RottenTomatoes" /> [[Metacritic]], das einen gewichteten Durchschnitt verwendet, vergab eine Punktzahl von 74 von 100 auf der Grundlage von 31 Kritiken, was auf „allgemein positive Kritiken“ hinweist.<ref name="Metacritics" />

Die britische Tageszeitung ''[[The Guardian]]'' betitelte ''Andor'' als {{" |Text=die beste Star-Wars-Serie seit ''[[The Mandalorian]]''}},<ref name="guardian_2022-09-21">{{Internetquelle |autor=Jack Seale |url=https://www.theguardian.com/tv-and-radio/2022/sep/21/rogue-one-andor-review-the-best-star-wars-show-since-the-mandalorian |titel=Andor review – the best Star Wars show since The Mandalorian |werk=[[The Guardian]] |datum=2022-09-21 |sprache=en |abruf=2022-10-08}}</ref> während das US-amerikanische Branchenblatt ''[[Variety]]'' sich positiv über ''Andors'' Abkehr von anderen ''Star-Wars-''Projekten äußerte, mit einer {{" |Text=Geschichte von Menschen, die nichts mit Solos, Skywalkers oder Palpatines zu tun haben, deren Leben aber dennoch wichtig ist}}.<ref name="Variety_2022-09-20">{{Internetquelle |autor=Caroline Framke |url=https://variety.com/2022/tv/news/andor-review-star-wars-rogue-one-disney-plus-1235376955/ |titel='Andor' Marks a Huge, and Hugely Welcome, Departure From Disney+’s Typical 'Star Wars' Model: TV Review |werk=[[Variety]] |datum=2022-09-20 |sprache=en |abruf=2022-10-08}}</ref>

Laut dem Filmkritiker [[Andreas Borcholte]] vom ''[[Der Spiegel (online)|Spiegel]]'' wähne man sich zu Beginn der Serie {{" |im falschen Science-Fiction-Film}}, da die Szenerie wie aus ''[[Blade Runner]]'' und ''[[WALL·E – Der Letzte räumt die Erde auf|WALL·E]]'' entsprungen wirke. ''Andor'' sei eine {{" |Text=»Star Wars«-Serie für Erwachsene, die eher auf ein panoramisches, weniger explosives Narrativ setzt.}} Im Gegensatz zu den letzten Fernsehserien im ''Star-Wars-''[[Franchise (Medien)|Franchise]] spielen {{" |Text=Jedi-Ritter, Sith-Lords und »Macht«-Brimborium mal keine Rolle.}}<ref name="spiegel_2022-09-21">{{Internetquelle |autor=[[Andreas Borcholte]] |url=https://www.spiegel.de/kultur/tv/star-wars-serie-andor-bei-disney-proletarier-zu-sternenkriegern-a-1cda2c0e-149d-4d3a-a1cc-a7634cd1d95a |titel=Proletarier zu Sternenkriegern |werk=[[Der Spiegel (online)|Der Spiegel]] |datum=2022-09-21 |abruf=2022-10-08}}</ref> Für den Filmkritiker Niklas Freund von der ''[[Süddeutsche Zeitung|Süddeutschen Zeitung]]'' ist ''Andor'' {{" |mehr [[Agententhriller]] als Zukunftsmärchen}}, womit der Franchise endlich mal wieder was riskiere.<ref name="sueddeutsche_2022-09-21">{{Internetquelle |autor=Nicolas Freund |url=https://www.sueddeutsche.de/medien/star-wars-andor-disney-plus-1.5660363 |titel=In dunklen Gassen |werk=[[Süddeutsche Zeitung]] |datum=2022-09-21 |abruf=2022-10-08}}</ref> Für Andreas Fischer von der Fernsehzeitschrift ''[[Prisma (Fernsehzeitschrift)|Prisma]]'' ist die Serie {{" |endlich ein Hit}}, da sie {{" |mit spannenden Abenteuern, einem authentischen Look und ambivalenten Figuren}} überzeuge und die Galaxie {{" |aus einer neuen Perspektive}} erkunde.<ref name="prisma_2022-09-21">{{Internetquelle |autor=Andreas Fischer |url=https://www.prisma.de/news/streaming/Andor-Kritik-Diese-Star-Wars-Serie-ist-endlich-ein-Hit,41360112 |titel=„Andor“: Diese „Star Wars“-Serie ist endlich ein Hit |werk=[[Prisma (Fernsehzeitschrift)|Prisma]] |datum=2022-09-21 |abruf=2022-10-08}}</ref> Für Stephanie Schlottag von der Computerspielezeitschrift ''[[GameStar]]'' ist {{" |Text=nicht nur der Look, auch die Stimmung der Serie […] galaxienweit von den bunten [[Space Opera|Sci-Fi-Opern]] der Filme entfernt}}, diese lege auch gegenüber ''Rogue One'' {{" |nochmal eine ordentliche Schippe Dreck und Gewalt oben drauf}}.<ref name="gamestar_2022-09-21">{{Internetquelle |autor=Stephanie Schlottag |url=https://www.gamestar.de/artikel/serienkritik-star-wars-andor-folge-1-2-3,3384794.html |titel=Serienkritik: Andor ist anders als alles, was wir bisher von Star Wars gesehen haben |werk=[[GameStar]] |datum=2022-09-21 |abruf=2022-10-08}}</ref>

Laut Benjamin Hecht vom Online-Portal ''[[Filmstarts]]'' glänze die Serie {{" |mit seiner Verliebtheit fürs Detail, dem einnehmenden Worldbuilding, starken Dialogen und einem beeindruckenden Produktionsaufwand}}, mache jedoch den {{" |gleichen Fehler wie bei ''[[Obi-Wan Kenobi (Fernsehserie)|Obi-Wan Kenobi]]''}}, da die Serie {{" |sich wirklich sehr viel Zeit lässt, die Welt und unzählige Nebenfiguren auszubauen}}. Zudem sei die {{" |komplette Struktur von ‚Andor‘ […] darauf ausgelegt, dass jeweils drei Folgen einen eigenen Handlungsbogen}} haben, werden jedoch ab der vierten Folge im Wochenrhythmus veröffentlicht, {{" |das Endprodukt wirkt dadurch träge}}.<ref name="filmstarts_2022-10-08">{{Internetquelle |autor=Benjamin Hecht |url=https://www.filmstarts.de/nachrichten/18544551.html |titel=Disney+ macht bei „Star Wars: Andor“ den gleichen Fehler wie bei „Obi-Wan Kenobi“ – Netflix zeigt, wie es besser geht! |werk=[[Filmstarts]] |datum=2022-10-05 |abruf=2022-10-08}}</ref> Für Andreas Engelhardt vom Online-Portal ''[[Kino.de]]'' {{" |Text=wirkt Andor wie eine Rückbesinnung auf aufrichtigere Zeiten}}, da die {{" |Text=letzten Star Wars-Titel dem von [[Marvel Cinematic Universe|Marvel-Filmen]] inspirierten lustig, lockeren, mit einem Augenzwinkern versehenen Ansatz folgten, den gefühlt so gut wie alle modernen Blockbuster kopieren.}}<ref name="kino_2022-09-21">{{Internetquelle |autor=Andreas Engelhardt |url=https://www.kino.de/serie/andor-2022/news/andor-kritik-darauf-haben-wir-im-star-wars-universum-seit-jahren-gewartet/ |titel=„Andor“-Kritik: Darauf haben wir im „Star Wars“-Universum seit Jahren gewartet |werk=[[Kino.de]] |datum=2022-09-21 |abruf=2022-09-24}}</ref>

== Weblinks ==
* {{IMDb|tt9253284}}
* {{fernsehserien.de|andor}}

== Einzelnachweise ==
<references responsive />

{{Navigationsleiste Star Wars}}

[[Kategorie:Fernsehserie (Vereinigte Staaten)]]
[[Kategorie:Fernsehserie der 2020er Jahre]]
[[Kategorie:Actionfernsehserie]]
[[Kategorie:Star-Wars-Serie]]

Algorithmus von Kruskal

2021-07-22T13:06:35Z

Optimalsloth: Einzelnachweise zusammengeführt

Der '''Algorithmus von Kruskal''' ist ein [[Greedy-Algorithmus]] der [[Graphentheorie]] zur Berechnung minimaler [[Spannbaum|Spannbäume]] von [[Ungerichteter Graph|ungerichteten Graphen]]. Der [[Graph (Graphentheorie)|Graph]] muss dazu zusätzlich [[Zusammenhang von Graphen|zusammenhängend]], [[Kantengewichteter Graph|kantengewichtet]] und endlich sein.

Der Algorithmus stammt von [[Joseph Kruskal]], der ihn 1956 in der Zeitschrift „Proceedings of the [[American Mathematical Society]]“ veröffentlichte. Er beschrieb ihn dort wie folgt:
: ''Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von <math>G</math> (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.''<ref name="KRUSKAL">[[Joseph Kruskal]]: ''On the shortest spanning subtree and the traveling salesman problem.'' In: ''Proceedings of the American Mathematical Society'', 7, 1956, S. 48–50</ref>

Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.

Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er für jede [[Zusammenhang von Graphen|Zusammenhangskomponente]] des Graphen einen minimalen Spannbaum. Diese Bäume bilden einen [[Spannbaum|minimalen aufspannenden Wald]].

== Idee ==
Der Algorithmus von Kruskal nutzt die Kreiseigenschaft minimaler Spannbäume ({{enS|minimum spanning tree}}, MST). Dazu werden die Kanten in der ersten Phase aufsteigend nach ihrem Gewicht sortiert. In der zweiten Phase wird über die sortierten Kanten iteriert. Wenn eine Kante zwei Knoten verbindet, die noch nicht durch einen Pfad vorheriger Kanten verbunden sind, wird diese Kante zum MST hinzugenommen.

== Beispiel ==
{| class="wikitable"
|-
|[[Datei:Prim Algorithm 0.svg|200px]]
|Dies ist der Graph, zu dem der Algorithmus von Kruskal einen minimalen Spannbaum berechnen wird. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. Zu Beginn ist noch keine Kante ausgewählt.
|-
|[[Datei:Kruskal Algorithm 1.svg|200px]]
|Die Kanten AD und CE sind die kürzesten (noch nicht ausgewählten) Kanten des Graphen. Beide können ausgewählt werden. Hier wird zufällig AD ausgewählt. (Dass diese keinen Kreis bildet, ist im ersten Schritt selbstverständlich.)
|-
|[[Datei:Kruskal Algorithm 2.svg|200px]]
|Nun ist CE die kürzeste, noch nicht ausgewählte Kante. Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt.
|-
|[[Datei:Kruskal Algorithm 3.svg|200px]]
|Die nächste Kante ist DF mit Länge 6. Sie bildet mit den schon gewählten Kanten keinen Kreis und wird deshalb ausgewählt.
|-
|[[Datei:Kruskal Algorithm 4.svg|200px]]
|Jetzt könnten die Kanten AB und BE, jeweils mit Länge 7, ausgewählt werden. Es wird zufällig AB gewählt. Die Kante BD wird rot markiert, da sie mit den bis jetzt gewählten Kanten einen Kreis bilden würde und somit im weiteren Verlauf des Algorithmus nicht mehr berücksichtigt werden muss.
|-
|[[Datei:Kruskal Algorithm 5.svg|200px]]
|BE ist nun mit Länge 7 die kürzeste der noch nicht ausgewählten Kanten und da sie mit den bisher gewählten keinen Kreis bildet, wird sie ausgewählt. Analog zur Kante BD im letzten Schritt werden jetzt die Kanten BC, DE und FE rot markiert.
|-
|[[Datei:Kruskal Algorithm 6.svg|200px]]
|Als letzte wird die Kante EG mit Länge 9 ausgewählt, da alle kürzeren bzw. gleich langen Kanten entweder schon ausgewählt sind oder einen Kreis bilden würden. Die Kante FG wird rot markiert. Da nun alle nicht ausgewählten Kanten einen Kreis bilden würden (sie sind rot markiert) ist der Algorithmus am Ende angelangt und der grüne Graph ist ein minimaler Spannbaum des zugrundeliegenden Graphen.
|}

== Algorithmus ==
Die Grundidee ist, die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zur Lösung hinzuzufügen, die mit allen zuvor gewählten Kanten keinen [[Kreis (Graphentheorie)|Kreis]] bildet. Es werden somit sukzessiv sogenannte [[Zusammenhang (Graphentheorie)|Komponenten]] zum minimalen [[Spannbaum]] verbunden.

=== Input ===
Als Eingabe dient ein zusammenhängender kantenbewerteter Graph <math>G = (V,\,E,\,w)</math>. <math>V</math> bezeichnet die Menge der Knoten ''(vertices)'', <math>E</math> die Menge der Kanten ''(edges)''. Die Gewichtsfunktion <math>w\colon E \rightarrow \R</math> ordnet jeder Kante ein Kantengewicht zu.

=== Output ===
Der Algorithmus liefert einen minimalen Spannbaum <math>M = (V,\,E')</math> mit <math>E' \subseteq E</math>.

=== Pseudocode ===
Der Algorithmus von Kruskal arbeitet nicht-deterministisch, d. h., er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Alle diese Ergebnisse sind minimale Spannbäume von <math>G</math>.
[[Datei:KruskalDemo.gif|mini|160x160px|Ein Beispiel für den Algorithmus von Kruskal basierend auf dem [[Euklidischer Abstand|Euklidischen Abstand]].]]
G = (V,E,w): ein zusammenhängender, ungerichteter, kantengewichteter Graph
''kruskal''(G)
1 <math>E' \leftarrow \emptyset</math>
2 <math>L \leftarrow E</math>
3 Sortiere die Kanten in L aufsteigend nach ihrem Kantengewicht.
4 '''solange''' <math>L \neq \emptyset</math>
5 wähle eine Kante <math>e \in L</math> mit kleinstem Kantengewicht
6 entferne die Kante <math>e</math> aus <math>L</math>
7 '''wenn''' der Graph <math>(V,E' \cup \lbrace e \rbrace)</math> keinen Kreis enthält
8 '''dann''' <math>E' \leftarrow E' \cup \lbrace e \rbrace</math>
9 M = (V,E') ist ein minimaler Spannbaum von G.

Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden. Sei <math>G=(V,E,w)</math> etwa ein zusammenhängender kantengewichteter Graph. Dann gibt man <math>G'=(V,E,w')</math> mit <math>w'(e) = s - w(e)</math>, <math>s \in \mathbb{N}</math> und <math>\forall e \in E \,: s > w(e)</math> im Algorithmus von Kruskal ein. Als Ausgabe erhält man schließlich einen minimalen Spannbaum von <math>G'</math> und somit einen maximalen von <math>G</math>.

Zum Testen, ob Knoten <math>u</math> und <math>v</math> in unterschiedlichen Teilbäumen sind, kann eine [[Union-Find-Struktur]] verwendet werden. Dann ergibt sich eine Laufzeit von <math>O(T_{sort}(|E|) + |E| \cdot \alpha(|V|))</math>. Dabei ist <math>T_{sort}</math> die Zeit, die zum Sortieren der Kantengewichte benötigt wird und <math>\alpha(\cdot))</math> das Inverse der [[Ackermannfunktion]]. Für realistische Eingaben ist <math>\alpha(|V|)</math> immer kleiner oder gleich <math>5</math>

=== Programmierung ===
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung eines [[Ungerichteter Graph|ungerichteten Graphen]] mit einem Array von [[Kante (Graphentheorie)|Kanten]]. Der ungerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''UndirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''main'' verwendet, die die Kanten und Kantengewichte eines minimalen Spannbaums auf der Konsole ausgibt. Die [[Funktion (Programmierung)|Funktion]] ''unionSubsets'' verwendet ''[[Union-Find-Struktur#Union by size und Union by rank|union by rank]]'', um zwei [[Teilmenge|Teilmengen]] von Kanten des Graphen zu vereinigen.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ Kruskal’s Minimum Spanning Tree Algorithm]</ref><syntaxhighlight lang="c++">
#include <iostream>
#include <sstream>
using namespace std;

// Deklariert den Datentyp für die Knoten des Graphen
struct Node
{
int index;
string value;
Node* next;
};

// Deklariert den Datentyp für die Kanten des Graphen
struct Edge
{
int startIndex;
int endIndex;
int weight;
};

// Deklariert die Klasse für den ungerichteten Graphen
class UndirectedGraph
{
public:
int numberOfVertices;
Edge* edges; // Pointer auf das Array für die Kanten
};

// Deklariert die Klasse für Teilmengen (Teilbäume) der Kantenmenge des ungerichteten Graphen
class subset
{
public:
int parent; // Index der Wurzel
int rank; // Rang der Teilmenge
};

// Diese rekursive Funktion gibt den Index der Wurzel der Teilmenge (Teilbaum) mit dem Index i zurück
int find(subset subsets[], int i)
{
// Setzt Index der Wurzel auf den Index der Wurzel der Teilmenge mit dem Index i
if (subsets[i].parent != i)
{
subsets[i].parent = find(subsets, subsets[i].parent); // Rekursiver Aufruf der Funktion
}
return subsets[i].parent;
}

// Diese Methode bildet die Vereinigungsmenge der zwei Teilmengen (Teilbäume) mit den Indexen index1 und index2
void unionSubsets(subset subsets[], int index1, int index2)
{
int newIndex1 = find(subsets, index1); // Index der Teilmenge mit dem Index index1
int newIndex2 = find(subsets, index2); // Index der Teilmenge mit dem Index index2
// Hängt den Teilbaum mit dem niedrigeren Rang unter die Wurzel des Baums mit dem höheren Rang
if (subsets[newIndex1].rank < subsets[newIndex2].rank)
{
subsets[newIndex1].parent = newIndex2;
}
else if (subsets[newIndex1].rank > subsets[newIndex2].rank)
{
subsets[newIndex2].parent = newIndex1;
}
else // Wenn die Teilbäume denselben Rang haben, wird der Rang des einen Baums erhöht und der andere Baum unter die Wurzel des anderen Baums gehängt
{
subsets[newIndex2].parent = newIndex1;
subsets[newIndex1].rank++;
}
}

// Diese Funktion vergleicht die Gewichte der Kanten edge1 und edge2
int compare(const void* edge1, const void* edge2)
{
return ((Edge*)edge1)->weight > ((Edge*)edge2)->weight; // Gibt 1 zurück, wenn der Vergleich true ergibt. Gibt 0 zurück, wenn der Vergleich false ergibt.
}

// Diese Funktion verwendet den Algorithmus von Kruskal und gibt den minimalen Spannbaum zurück
Edge* getMSTByKruskal(UndirectedGraph* graph)
{
Edge* edges = graph->edges; // Pointer auf das Array für die Kanten
int numberOfVertices = graph->numberOfVertices; // Variable für die Anzahl der Knoten
int numberOfEdges = sizeof(edges); // Variable für die Anzahl der Kanten

Edge* minimalSpanningTree = new Edge[numberOfVertices]; // Deklariert ein Array für die Kanten, das als Ergebnis der Methode zurückgegeben wird
int currentIndex = 0; // Aktueller Kantenindex
int nextIndex = 0; // Kantenindex für die nächste Iteration
qsort(edges, numberOfEdges, sizeof(edges[0]), compare); // Sortiert das Array edges der Kanten mit der C++-Standardfunktion qsort (Sortierverfahren Quicksort) und der oben definierten Vergleichsfunktion compare

subset* subsets = new subset[numberOfVertices]; // Deklariert ein Array für die Teilmengen der Kantenmenge
for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die Teilmengen mit einzelnen Kanten erzeugt
{
subsets[i].parent = i;
subsets[i].rank = 0;
}
while (currentIndex < numberOfVertices - 1 && nextIndex < numberOfEdges) // So lange der aktuelle Kantenindex kleiner als die Anzahl der Knoten minus 1 ist
{
Edge nextEdge = edges[nextIndex++]; // Weist die verbleibende Kante mit dem kleinsten Kantengewicht zu und erhöht den Kantenindex für die nächste Iteration um 1
int index1 = find(subsets, nextEdge.startIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.startIndex
int index2 = find(subsets, nextEdge.endIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.endIndex
if (index1 != index2) // Wenn die Kante keinen Zyklus erzeugt
{
minimalSpanningTree[currentIndex++] = nextEdge; // Fügt die Kante dem minimalen Spannbaum hinzu
unionSubsets(subsets, index1, index2); // Methodenaufruf, der die Vereinigungsmenge der zwei Mengen mit den Indexen index1 und index2 bildet
}
}
return minimalSpanningTree;
}

// Gibt die Kanten, die Gewichte und das gesamte Kantengewicht des minimalen Spannbaums auf der Konsole aus
string MSTtoString(Edge* minimalSpanningTree)
{
stringstream text;
int weight = 0;
for (int i = 0; i < sizeof(minimalSpanningTree) - 1; i++)
{
Edge edge = minimalSpanningTree[i];
text << "(" << edge.startIndex << ", " << edge.endIndex << "), Gewicht: " << edge.weight << endl;
weight += edge.weight;
}
text << "Kantengewicht des minimalen Spannbaums: " << weight << endl;
return text.str(); // Typumwandlung von stringstream nach string
}

// Hauptfunktion die das Programm ausführt
int main()
{
// Deklariert und initialisiert ein Array mit 5 Kanten
Edge* edges = new Edge[5];
edges[0].startIndex = 0;
edges[0].endIndex = 1;
edges[0].weight = 10;
edges[1].startIndex = 0;
edges[1].endIndex = 2;
edges[1].weight = 6;
edges[2].startIndex = 0;
edges[2].endIndex = 3;
edges[2].weight = 5;
edges[3].startIndex = 1;
edges[3].endIndex = 3;
edges[3].weight = 15;
edges[4].startIndex = 2;
edges[4].endIndex = 3;
edges[4].weight = 4;

// Erzeugt den ungerichteten Graphen mit den gegebenen Kanten
UndirectedGraph* undirectedGraph = new UndirectedGraph;
undirectedGraph->edges = edges;
undirectedGraph->numberOfVertices = 4;
Edge* minimalSpanningTree = getMSTByKruskal(undirectedGraph); // Aufruf der Methode, die einen Pointer auf das Array von Kanten zurückgibt
cout << MSTtoString(minimalSpanningTree); // Aufruf der Methode, die das Ergebnis auf der Konsole ausgibt
}
</syntaxhighlight>

=== Varianten ===
==== Paralleles Sortieren ====
Das Sortieren der ersten Phase kann parallelisiert werden. In der zweiten Phase ist es für die Korrektheit jedoch wichtig, dass die Kanten nacheinander abgearbeitet werden. Mit <math>O(log |V|)</math> Prozessoren kann in linearer Zeit parallel sortiert werden. Dadurch sinkt die Gesamtlaufzeit auf <math>O(|E| \cdot \alpha(|V|))</math>.

==== Filter-Kruskal ====
Eine Variante des Algorithmus von Kruskal namens Filter-Kruskal wurde von Osipov et al.<ref name="osipov2009" /> beschrieben und eignet sich besser zur Parallelisierung. Die grundlegende Idee besteht darin, die Kanten in ähnlicher Weise wie bei [[Quicksort]] zu partitionieren und anschließend Kanten auszusortieren, welche Knoten im gleichen Teilbaum verbinden, um somit die Kosten für die weitere Sortierung zu verringern. Filter-Kruskal eignet sich besser zur Parallelisierung, da das Sortieren, Partitionieren und Filtern einfach parallel ausgeführt werden können, indem die Kanten zwischen den Prozessoren aufgeteilt werden. Der Algorithmus wird im folgenden Pseudocode dargestellt.

filterKruskal(<math>G</math>):
'''falls''' <math>|E| <</math> KruskalSchwellwert:
'''return''' kruskal(<math>G</math>)
pivot = zufällige Kante aus <math>E</math>
<math>(E_{\leq}</math>, <math>E_{>}) \gets </math>partition(<math>E</math>, pivot)
<math>A \gets</math> filterKruskal(<math>E_{\leq}</math>)
<math>E_{>} \gets</math> filter(<math>E_{>}</math>)
<math>A \gets A</math> <math>\cup</math> filterKruskal(<math>E_{>}</math>)
'''return''' <math>A</math>

partition(<math>E</math>, pivot):
<math>E_{\leq} \gets \emptyset </math>
<math>E_{>} \gets \emptyset</math>
'''für alle''' <math>(u, v) \in E</math>:
'''falls''' gewicht(<math>u, v</math>) <math>\leq</math> gewicht(pivot):
<math>E_{\leq} \gets E_{\leq} \cup {(u, v)}</math>
'''sonst'''
<math>E_{>} \gets E_{>} \cup {(u, v)} </math>
'''return''' (<math>E_{\leq}</math>, <math>E_{>}</math>)

filter(<math>E</math>):
<math>E_{filtered} \gets \emptyset </math>
'''für alle''' <math>(u, v) \in E</math>:
'''falls''' find-set(u) <math>\neq</math> find-set(v):
<math>E_{filtered} \gets E_{filtered} \cup {(u, v)}</math>
'''return''' <math>E_{filtered}</math>

== Korrektheitsbeweis ==
Sei <math>G = (V,E,w)</math> ein zusammenhängender kantengewichteter Graph und <math>M = (V,E')</math> die Ausgabe des Algorithmus von Kruskal. Um nun die Korrektheit des Algorithmus zu beweisen, muss Folgendes gezeigt werden:
# der Algorithmus [[Terminiertheit|terminiert]] (er enthält keine Endlosschleife).
# <math>M</math> ist ein minimaler Spannbaum von <math>G</math>, also:
## <math>M</math> ist spannender Teilgraph von <math>G</math>.
## <math>M</math> enthält keinen Kreis.
## <math>M</math> ist zusammenhängend.
## <math>M</math> ist bezüglich <math>G</math> minimal.

Im Nachstehenden folgen einige Beweisideen, die die Gültigkeit der einzelnen Aussagen darlegen:
; Terminierung: Durch Zeile 6 wird in jedem Schleifendurchlauf genau ein Element aus <math>L</math> entfernt. Außerdem wird <math>L</math> durch keine weitere Operation verändert. Aus <math>L</math> werden wegen Zeile 4 nur solange Elemente entfernt, bis <math>L = \emptyset</math>. Da zu Beginn im Algorithmus <math>L = E</math> gesetzt wurde und <math>E</math> nach Definition nur endlich ist, wird auch die Schleife nur endlich oft durchlaufen. Daraus folgt, dass Kruskals Algorithmus terminiert.
; M ist aufspannender Teilgraph von G: Da die Menge der Knoten nach Definition des Algorithmus bei <math>M</math> und <math>G</math> gleich ist und wegen Zeile 8 offensichtlich <math>E' \subseteq E</math> gilt, ist <math>M</math> aufspannender Teilgraph von <math>G</math>.
; M enthält keinen Kreis: Dass <math>M</math> keinen Kreis beinhalten kann, ist durch Zeile 7 trivial.
; M ist zusammenhängend: Im Folgenden wird indirekt gezeigt, dass <math>M</math> zusammenhängend ist. Sei <math>M</math> also nicht zusammenhängend. Dann gibt es in <math>M</math> zwei Knoten <math>x</math> und <math>y</math>, die nicht durch einen Weg verbunden sind. Da aber <math>x</math> und <math>y</math> in <math>G</math> durch einen Weg verbunden sind, existiert eine Kante <math>k</math> in <math>G</math>, welche nicht in <math>M</math> vorhanden ist. Der Algorithmus betrachtet in Zeile 7 garantiert jede Kante aus <math>G</math> und damit auch <math>k</math>. Der Graph <math>(V,E' \cup \lbrace k \rbrace)</math> in Zeile 7 muss kreisfrei sein, da es zwischen <math>x</math> und <math>y</math> in <math>M=(V,E')</math> keinen Weg gibt. Mit Zeile 8 wird <math>k</math> dann in <math>M</math> eingefügt. Dies widerspricht allerdings der Tatsache, dass <math>k</math> nicht in <math>M</math> enthalten ist. Somit ist unsere Annahme hinfällig und <math>M</math> doch zusammenhängend.
; M ist bezüglich G minimal: Wir zeigen durch Induktion, dass für <math>k=0,...,n</math> die folgende Behauptung wahr ist:
Wenn <math>F</math> die Kantenmenge ist, die im <math>k</math>-ten Schritt des Algorithmus erzeugt wurde, dann gibt es einen minimalen Spannbaum, der <math>F</math> enthält.
Die Behauptung ist für <math>k=0</math> wahr, d. h. <math>F = \emptyset</math> (d. h., es ist noch keine Kante eingeplant). Jeder minimale Spannbaum erfüllt die Behauptung und es existiert ein minimaler Spannbaum, da ein gewichteter, zusammenhängender Graph immer einen minimalen Spannbaum besitzt.
Jetzt nehmen wir an, dass die Behauptung für <math>0 \le k < n</math> erfüllt ist und <math>F</math> die vom Algorithmus nach Schritt <math>k</math> erzeugte Kantenmenge ist. Es sei <math>M</math> der minimale Spannbaum, der <math>F</math> enthält.
Wir betrachten jetzt den Fall <math>k+1</math>. Dafür sei <math>e</math> die letzte vom Algorithmus eingefügte Kante.
; Falls <math>e \in M</math>: Dann ist die Behauptung auch für <math>F+e</math> erfüllt, da der minimale Spannbaum <math>F</math> um eine Kante aus dem minimalen Spannbaum <math>M</math> erweitert wird.
; Falls <math>e \notin M</math>: Dann enthält <math>M+e</math> einen Kreis und es gibt eine Kante <math>f</math>, die im Kreis, aber nicht in <math>F</math> liegt. (Wenn es keine solche Kante <math>f</math> geben würde, dann hätte <math>e</math> nicht zu <math>F</math> hinzufügt werden können, da dann ein Kreis entstanden wäre.) Damit ist <math>M-f+e</math> ein Baum. Weiterhin kann das Gewicht von <math>f</math> nicht geringer als das Gewicht von <math>e</math> sein, da sonst der Algorithmus <math>f</math> anstelle von <math>e</math> hinzugefügt hätte. Mit <math>w(e) \le w(f)</math> folgt, dass <math>w(M-f+e) \le w(M)</math> gilt. Da aber <math>M</math> minimaler Spannbaum ist, gilt außerdem <math>w(M) \le w(M-f+e)</math> und daraus folgt <math>w(M-f+e) = w(M)</math>. Somit ist <math>M-f+e</math> ein minimaler Spannbaum, der <math>F+e</math> enthält, und die Behauptung ist erfüllt.

Damit folgt für <math>k=n</math>, dass der Kruskal-Algorithmus nach <math>n</math> Schritten eine Menge <math>F</math> erzeugt, die zu einem minimalen Spannbaum erweitert werden kann. Da aber das Ergebnis nach <math>n</math> Schritten des Algorithmus bereits ein Baum ist (wie oben gezeigt wurde), muss dieser minimal sein.

== Zeitkomplexität ==
Im Folgenden sei <math>\left|E\right|</math> die Anzahl der Kanten und <math>\left|V\right|</math> die Anzahl der Knoten. Die [[Zeitkomplexität|Laufzeit]] des Algorithmus setzt sich zusammen aus dem notwendigen [[Sortierverfahren|Sortieren]] der Kanten nach ihrem Gewicht und dem Überprüfen, ob der Graph kreisfrei ist.
Das Sortieren benötigt eine Laufzeit von <math>\mathcal{O}\bigl(\left|E\right| \cdot \log(\left|E\right|)\bigr)</math>. Bei einer geeigneten Implementierung ist das Überprüfen auf Kreisfreiheit schneller möglich, so dass das Sortieren die Gesamtlaufzeit bestimmt. Insbesondere bei Graphen mit vielen Kanten ist insofern der [[Algorithmus von Prim]] effizienter.

Wenn die Kanten bereits vorsortiert sind, arbeitet der Algorithmus von Kruskal schneller. Man betrachtet nun, wie schnell das Überprüfen auf Kreisfreiheit möglich ist. Um eine bestmögliche Laufzeit zu erreichen, speichert man alle Knoten in einer [[Union-Find-Struktur]]. Diese enthält Informationen darüber, welche Knoten zusammenhängen. Zu Beginn ist noch keine Kante in den Spannbaum eingetragen, daher ist jeder Knoten für sich in einer einzelnen [[Partition (Mengenlehre)|Partition]]. Wenn eine Kante <math>(v_1,v_2)</math> hinzugefügt werden soll, wird überprüft, ob <math>v_1</math> und <math>v_2</math> in verschiedenen Partitionen liegen. Dazu dient die Operation ''Find(x)'': Sie liefert einen Repräsentanten der Partition, in dem der Knoten x liegt. Wenn Find(<math>v_1</math>) und Find(<math>v_2</math>) verschiedene Ergebnisse liefern, dann kann die Kante hinzugefügt werden und die Partitionen der beiden Knoten werden vereinigt (''Union''). Ansonsten würde durch Hinzunehmen der Kante ein Kreis entstehen, die Kante wird also verworfen.
Insgesamt wird die Operation ''Find'' <math>2\cdot \left|E\right|</math> (für jede Kante) und die Operation ''Union'' <math>\left|V\right|-1</math> mal aufgerufen.
Bei Verwenden der Heuristiken [[Union-By-Size]] und [[Pfadkompression]] ergibt eine [[amortisierte Laufzeitanalyse]] für den Algorithmus eine Komplexität von <math>\mathcal{O}(\left|E\right| \cdot \log^* \left|V\right|)</math>. Dabei ist <math>\log^*(n)</math> definiert als
:<math>\min \Bigl\{s\in\mathbb{N} \mid \underbrace{\log\bigl(\log(\ldots\log(n)\ldots)\bigr)}_{s\text{-mal}} \le 1 \Bigr\}</math>
und praktisch konstant. Theoretisch wächst diese Funktion jedoch unendlich, weshalb sie in der O-Notation nicht weggelassen werden kann.

== Parallele Implementierung ==
Aufgrund von Datenabhängigkeiten zwischen den Iterationen lässt sich der Algorithmus von Kruskal grundsätzlich schwer parallelisieren. Es ist jedoch möglich, das Sortieren der Kanten zu Beginn parallel auszuführen oder alternativ eine parallele Implementation eines [[Binärer Heap|Binären Heaps]] zu verwenden um in jeder Iteration die Kante mit dem kleinsten Gewicht zu finden<ref>{{Cite journal|last1=Quinn|first1=Michael J.|last2=Deo|first2=Narsingh|date=1984|title=Parallel graph algorithms|url=|journal=ACM Computing Surveys (CSUR) 16.3|volume=|pages=319–348}}</ref>. Durch paralleles Sortieren, was auf <math>O(n \cdot \log n)</math> Prozessoren in <math>O(n)</math> Zeit möglich ist<ref>{{cite book|title=Introduction to Parallel Computing|last1=Grama|first1=Ananth|last2=Gupta|first2=Anshul|last3=Karypis|first3=George|last4=Kumar|first4=Vipin|publisher=|year=2003|isbn=978-0-201-64865-2|location=|pages=412–413}}</ref>, kann die Laufzeit des Algorithmus auch bei zuvor unsortierten Kanten auf <math>O(|E| \cdot \log^*|V|)</math> reduziert werden.

Eine Variante des Algorithmus von Kruskal namens Filter-Kruskal wurde von Osipov et al.<ref name="osipov2009">{{Cite journal|last1=Osipov|first1=Vitaly|last2=Sanders|first2=Peter|last3=Singler|first3=Johannes|date=2009|title=The filter-kruskal minimum spanning tree algorithm|url=|journal=Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics|volume=|pages=52–61}}</ref> beschrieben und eignet sich besser zur Parallelisierung. Die grundlegende Idee besteht darin, die Kanten in ähnlicher Weise wie bei [[Quicksort]] zu partitionieren und anschließend Kanten auszusortieren, welche Knoten im gleichen Teilbaum verbinden, um somit die Kosten für die Sortierung zu verringern. Der Algorithmus wird im folgenden [[Pseudocode]] dargestellt.

FILTER-KRUSKAL(G):
1 '''if''' |G.E| < KruskalThreshhold:
2 '''return''' KRUSKAL(G)
3 pivot = CHOOSE-RANDOM(G.E)
4 <math>E_{<=}</math>, <math>E_{>}</math> = PARTITION(G.E, pivot)
5 A = FILTER-KRUSKAL(<math>E_{<=}</math>)
6 <math>E_{>}</math> = FILTER(<math>E_{>}</math>)
7 A = A ∪ FILTER-KRUSKAL(<math>E_{>}</math>)
8 '''return''' A

PARTITION(E, pivot):
1 <math>E_{<=}</math> = ∅, <math>E_{>}</math> = ∅
2 '''foreach''' (u, v) in E:
3 '''if''' weight(u, v) <= pivot:
4 <math>E_{<=}</math> = <math>E_{<=}</math> ∪ {(u, v)}
5 '''else'''
6 <math>E_{>}</math> = <math>E_{>}</math> ∪ {(u, v)}
5 '''return''' <math>E_{<=}</math>, <math>E_{>}</math>

FILTER(E):
1 <math>E_{filtered}</math> = ∅
2 '''foreach''' (u, v) in E:
3 '''if''' FIND-SET(u) ≠ FIND-SET(v):
4 <math>E_{filtered}</math> = <math>E_{filtered}</math> ∪ {(u, v)}
5 '''return''' <math>E_{filtered}</math>

Filter-Kruskal eignet sich besser zur Parallelisierung, da sowohl das Sortieren und Partitionieren, als auch das Filtern einfach parallel ausgeführt werden kann, indem die Kanten zwischen den Prozessoren aufgeteilt werden.<ref name="osipov2009" />

Weitere Varianten für eine Parallelisierung von Kruskals Algorithmus sind ebenfalls möglich. So besteht zum Beispiel die Möglichkeit, den sequentiellen Algorithmus auf mehreren Teilgraphen parallel auszuführen, um diese dann zusammenzuführen bis schlussendlich nur noch der finale minimale Spannbaum übrigbleibt<ref>{{Cite journal|last1=Lončar|first1=Vladimir|last2=Škrbić|first2=Srdjan|last3=Balaž|first3=Antun|date=2014|title=Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures|url=|journal=Transactions on Engineering Technologies.|volume=|pages=543–554}}</ref>. Eine simplere Form des Filter-Kruskals, bei welchem Hilfsthreads benutzt werden, um Kanten, die eindeutig nicht Teil des minimalen Spannbaums sind, im Hintergrund zu entfernen, kann ebenfalls verwendet werden<ref>{{Cite journal|last1=Katsigiannis|first1=Anastasios|last2=Anastopoulos|first2=Nikos|last3=Konstantinos|first3=Nikas|last4=Koziris|first4=Nectarios|date=2012|title=An approach to parallelize kruskal’s algorithm using helper threads|url=|journal=Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International|volume=|pages=1601–1610}}</ref>.

== Sonstiges ==
Der Algorithmus diente Kruskal ursprünglich als Hilfsmittel für einen vereinfachten Beweis, dass ein Graph mit paarweise verschiedenen Kantengewichten einen eindeutigen minimalen Spannbaum besitzt.

== Weblinks ==
{{Wikibooks|Algorithmensammlung: Graphentheorie: Algorithmus von Kruskal|Algorithmus von Kruskal|suffix=Implementierungen in der Algorithmensammlung}}
* [http://web-old.archive.org/web/20160314221605/http://www-m9.ma.tum.de/graph-algorithms/mst-kruskal/index_de.html Interaktives Applet zum Lernen, Ausprobieren und Demonstrieren des Algorithmus]
* Ronny Harbich: [http://www.uni-magdeburg.de/harbich/mst.php Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal.] 2006
* [http://web-old.archive.org/web/20160127080051/http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php Anschauliche Darstellung des Algorithmus im Rahmen des Informatikjahres 2006]

== Einzelnachweise ==
<references />

[[Kategorie:Optimierungsalgorithmus|Kruskal]]
[[Kategorie:Graphsuchalgorithmus|Kruskal]]