So verwenden Sie Java, um den Algorithmus von Prim zu implementieren
Der Algorithmus von Prim ist ein klassischer Algorithmus zur Lösung minimaler Spannbäume und kann zur Lösung verschiedener Netzwerkoptimierungsprobleme verwendet werden. In diesem Artikel stellen wir vor, wie der Prim-Algorithmus mithilfe der Java-Sprache implementiert wird, und stellen entsprechende Codebeispiele bereit.
1) Initialisieren Sie den minimalen Spannbaum so, dass er leer ist, wählen Sie einen Anfangsscheitelpunkt v aus, um sich dem Satz des minimalen Spannbaums anzuschließen.
2) Führen Sie die folgenden Schritte in einer Schleife aus, bis der minimale Spannbaumsatz alle Scheitelpunkte enthält:
a) Wählen Sie einen Scheitelpunkt u von außerhalb des minimalen Spannbaumsatzes aus, sodass das Gewicht von u zum Scheitelpunkt im minimalen Spannbaumsatz beträgt der Kleinste.
b) Fügen Sie den Scheitelpunkt u zur minimalen Spannbaummenge hinzu und notieren Sie die Gewichte der Kanten (u, v).
c) Aktualisieren Sie das Gewicht von u auf den Scheitelpunkt außerhalb des minimalen Spannbaumsatzes. Wenn das Gewicht eines Scheitelpunkts kleiner ist, aktualisieren Sie das Gewicht des Scheitelpunkts auf den Scheitelpunkt im minimalen Spannbaumsatz.
import java.util.Arrays; public class PrimAlgorithm { // 假设使用邻接矩阵表示图 public int prim(int[][] graph) { int numVertex = graph.length; // 图中顶点的个数 int[] lowCost = new int[numVertex]; // 存储顶点到最小生成树集合的最小权值 boolean[] visited = new boolean[numVertex]; // 标记顶点是否已经加入最小生成树集合 int[] parent = new int[numVertex]; // 存储顶点的父节点 Arrays.fill(lowCost, Integer.MAX_VALUE); // 初始化最小权值为无穷大 Arrays.fill(visited, false); // 初始化顶点未访问 // 从顶点0开始构建最小生成树 lowCost[0] = 0; // 顶点0到最小生成树集合的最小权值为0 parent[0] = -1; // 顶点0没有父节点 // 循环直到最小生成树集合包含所有顶点 for (int i = 0; i < numVertex - 1; i++) { // 选择一个顶点u使得u到最小生成树集合中的顶点的权值最小 int u = -1; for (int j = 0; j < numVertex; j++) { if (!visited[j] && (u == -1 || lowCost[j] < lowCost[u])) { u = j; } } visited[u] = true; // 将顶点u加入最小生成树集合 // 更新u到最小生成树集合外的顶点的权值 for (int v = 0; v < numVertex; v++) { if (!visited[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]) { lowCost[v] = graph[u][v]; parent[v] = u; } } } int totalPrice = 0; for (int i = 1; i < numVertex; i++) { totalPrice += graph[parent[i]][i]; } return totalPrice; } public static void main(String[] args) { int[][] graph = { {0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0} }; PrimAlgorithm primAlgorithm = new PrimAlgorithm(); int totalPrice = primAlgorithm.prim(graph); System.out.println("Total weight of minimum spanning tree: " + totalPrice); } }
Im obigen Code verwenden wir die Adjazenzmatrix zur Darstellung des Diagramms und verwenden den Dijkstra-Algorithmus, um das Gesamtgewicht von zu lösen der minimale Spannbaum. Im Beispiel verwenden wir ein 5-Scheitelpunkt-Diagramm, um die Verwendung des Algorithmus zu demonstrieren.
Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Algorithmus von Prim mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!