Można użyć algorytmu Prim lub algorytmu Kruskala, aby znaleźć minimalne drzewo rozpinające / wykres zbioru wierzchołków / węzłów i krawędzi / łączy. Potrzebuję jednak algorytmu, który znajduje minimalny wykres rozpiętości tej kolekcji, ale wynikowy wykres musi zawierać tylko dowolnie wybrane węzły, a nie wszystkie węzły. W porządku, jeśli wynikowy wykres zawiera więcej węzłów niż tylko te potrzebne.

Czy taki algorytm istnieje? Być może można po prostu użyć algorytmu Prim (lub Kruskala) po zmodyfikowaniu wykresu, aby uwzględnić tylko potrzebne węzły? Ale nie jestem pewien, jak zmodyfikować wykres, aby to zrobić, zachowując jego połączenie.

Załóżmy na przykład, że mamy wykres początkowy w kształcie rombu (z kosztami linków w nawiasach):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

Teraz arbitralnie decydujemy, że potrzebne są tylko węzły A i D. Gdybyśmy zaczęli od A, nadal chcielibyśmy, aby obrała lewą ścieżkę, ponieważ ((2 + 2) <(1 + 5)).

Powiedzmy, że zmodyfikowaliśmy nieco wykres:

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

Jeśli zdecydujemy, że potrzebne są tylko węzły A, D i E, zdajemy sobie sprawę, że ścieżka z minimalnym kosztem niekoniecznie jest ścieżką o najmniejszej liczbie łączy. Biorąc A - B - D i A - C - E kosztuje 7, ale A - C - D i C - E kosztuje 8.