Man kann den Prim-Algorithmus oder den Kruskal-Algorithmus verwenden, um den minimalen Spannbaum / Graphen einer Sammlung von Eckpunkten / Knoten und Kanten / Verbindungen zu finden. Was ich jedoch möchte, ist ein Algorithmus, der das minimale überspannende Diagramm dieser Sammlung findet, aber das resultierende Diagramm muss nur willkürlich ausgewählte Knoten anstelle aller Knoten enthalten. Es ist in Ordnung, wenn das resultierende Diagramm mehr Knoten als nur die benötigten enthält.

Gibt es einen solchen Algorithmus? Vielleicht könnte man einfach den Algorithmus von Prim (oder Kruskal) verwenden, nachdem der Graph so modifiziert wurde, dass nur die benötigten Knoten enthalten sind? Ich bin mir jedoch nicht sicher, wie ich den Graphen ändern soll, um die Verbundenheit aufrechtzuerhalten.

Angenommen, wir haben ein rautenförmiges Startdiagramm (mit den Kosten für Links in Klammern):

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

Nun entscheiden wir willkürlich, dass nur die Knoten A und D benötigt werden. Wenn wir bei A anfangen würden, würden wir immer noch wollen, dass es den linken Pfad nimmt, weil ((2 + 2) <(1 + 5)).

Angenommen, wir ändern das Diagramm geringfügig:

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

Wenn wir entscheiden, dass nur die Knoten A, D und E benötigt werden, stellen wir fest, dass der Pfad mit den minimalen Kosten nicht unbedingt der mit den wenigsten Verbindungen ist. A - B - D und A - C - E kosten 7, A - C - D und C - E kosten 8.