Angenommen, Sie haben einen gerichteten Graphen mit nichtnegativen, ganzzahligen Kantenlängen, die im Bereich von 0 bis einschließlich U - 1 liegen. Welches ist der schnellste Algorithmus zur Berechnung eines minimal aufspannenden Baums für diesen Graphen? Wir können immer noch bestehende Algorithmen für minimale Spannbäume verwenden, wie den Algorithmus von Kruskal (O(m log n)) oder den Algorithmus von Prim (O(m + n log n)). Für Fälle, in denen U klein ist, sollte es jedoch möglich sein, dies viel besser zu machen.
Gibt es Algorithmen, die mit traditionellen MST-Algorithmen konkurrieren können und die die Tatsache ausnutzen, dass die Kantenlängen in einem bestimmten Bereich liegen müssen?
Danke!
