Gewichtete Diagramme und Anwendungen

Ein Diagramm ist ein gewichtetes Diagramm, wenn jeder Kante ein Gewicht zugewiesen wird. Gewichtete Diagramme haben viele praktische Anwendungen.

Die obige Abbildung geht davon aus, dass die Grafik die Anzahl der Flüge zwischen Städten darstellt. Mithilfe des BFS können Sie die geringste Anzahl an Flügen zwischen zwei Städten ermitteln. Gehen Sie davon aus, dass die Kanten die Fahrstrecken zwischen den Städten darstellen, wie in der Abbildung unten dargestellt. Wie ermitteln Sie die minimalen Gesamtentfernungen für die Verbindung aller Städte? Wie findet man den kürzesten Weg zwischen zwei Städten? In diesem Kapitel wird auf diese Fragen eingegangen. Ersteres ist als Minimum Spanning Tree (MST)-Problem und letzteres als Problem des kürzesten Pfades bekannt.

Im vorangegangenen Kapitel wurde das Konzept der Graphen vorgestellt. Sie haben gelernt, wie Sie Kanten mithilfe von Kantenarrays, Kantenlisten, Adjazenzmatrizen und Adjazenzlisten darstellen und wie Sie ein Diagramm mithilfe der Schnittstelle Graph, der Klasse AbstractGraph und der Klasse UnweightedGraph Klasse. Im vorherigen Kapitel wurden außerdem zwei wichtige Techniken zum Durchlaufen von Diagrammen vorgestellt: Tiefensuche und Breitensuche sowie angewandte Durchquerung zur Lösung praktischer Probleme. In den folgenden Beiträgen werden gewichtete Diagramme vorgestellt. Sie lernen den Algorithmus zum Finden eines minimalen Spannbaums in Post und den Algorithmus zum Finden kürzester Pfade in Post kennen.

Das obige ist der detaillierte Inhalt vonGewichtete Diagramme und Anwendungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!