Ich bereite mich auf die Abschlussprüfung in Algorithms vor und habe eine Frage, von der ich hoffe, dass ihr mir helfen könnt.
Bei einem ungerichteten Graphen mit Gewichten zwischen 1 und 100, wie kann ich den Spanning Tree in einer linearen Zeit finden?
Antworten:
0 für die Antwort № 1Du könntest benutzen Kruskals Algorithmus mit disjunkt gesetzt und sortieren Kanten mit Zählen sortierenweil deine Gewichte begrenzt sind.