Greedy-Algorithmen

 Im Gegensatz zu BFS, DFS und dem Algorithmus von Dijkstra sind die Teilgraphen, die der Algorithmus von Kruskal berechnet, keine Bäume mehr. Der aufspannende Baum wird nicht durch schrittweises Hinzufügen einer optimalen Kante zu einem Baum konstruiert, sondern durch schrittweises Hinzufügen einer optimalen Kante zu einem Wald. Damit wachsen während der Durchführung mehrere Bäume parallel, die sich am Ende zu einem aufspannenden Teilbaum vereinigen. Alle Algorithmen gehören aber einen bestimmten Klasse an, den sogenannten Greedy-Algorithmen. Diese Algorithmen führen „gierig“ entsprechend dem Stand der Berechnungen optimierte Einzelschritte durch, um ein optimales Gesamtergebnis zu erzielen. Eine spätere Korrektur eines Schritts ist nicht notwendig. Was jetzt gut ist, ist später auch gut.

 „Greedy“ funktioniert nicht für alle graphentheoretischen Probleme. Ein berühmtes Gegenbeispiel ist das Problem des Handlungsreisenden (travelling salesman problem): Gegeben ist ein gewichteter vollständiger Graph der Ordnung n. Gesucht ist ein Hamilton-Kreis a₁, …, a_n, a₁ in G mit minimalem Gewicht. Ein Handlungsreisender, der diesem Kreis folgt, besucht also alle betrachteten Städte (Ecken), kommt am Ende wieder zu Hause an (Startecke) und hat die geringstmöglichen Reisekosten (Kantengewichte). Das Problem ist hier die Minimierung des Gewichts, nicht die Konstruktion eines Hamilton-Kreises an sich: Aufgrund der Vollständigkeit des Graphen können wir von jeder Ecke zu jeder anderen gehen und damit jeden Weg zu einem Hamilton-Kreis fortsetzen. Ein Greedy-Algorithmus, der ausgehend von einer Startecke stets den ersten unbesuchten Nachbarn mit minimalem Kantengewicht wählt, findet im Allgemeinen keinen Hamilton-Kreis mit minimalem Gewicht:

 Das Problem des Handlungsreisenden ist ein NP-vollständiges Problem, sodass wahrscheinlich kein effizienter Algorithmus existiert.