1. Application Scenario – Road repair
Question:
-
There are seven villages (A, B, C, D, E, F, G) in Shengli Township.
-
The distance of each village is marked by A line (weight), such as A to B distance of 5 km
-
How can roads be built to ensure that villages are connected and the total length of road built is the shortest
Ideas:
Connect 10 edges, but the total mileage is not the minimum
The right idea is to choose as few routes as possible, and each route is the smallest, to ensure that the total mileage is the least
2. Minimum spanning tree
The problem of road construction is essentially a Minimum Cost Spanning Tree (MST)
Given a weighted undirected connected graph, how to select a spanning tree to minimize the sum of all edge weights on the tree, which is called minimum spanning tree
-
N vertices, there must be N minus 1 edges
-
Contains all vertices
-
The N minus one edges are all in the diagram
-
The algorithms for minimum spanning tree are prim algorithm and Cthuluscale algorithm
3. Introduction to Prim algorithm
Prim algorithm to find the minimum spanning tree, that is, in the connected graph containing n vertices, find the connected subgraph as long as (n-1) edge contains all n vertices, that is, the so-called minimal connected subgraph
-
Let G=(V,E) be the connected network, T=(U,D) be the minimum spanning tree, V,U be the set of vertices,E,D be the set of edges
-
If the minimum spanning tree is constructed from vertex U, then vertex U is taken out from set V and put into set U, marking visited[u]=1 of vertex V
-
If there is an edge between vertex UI in set U and vertex vj in set V-U, then the edge with the lowest weight among these edges is searched, but it cannot form a loop. Add vertex Vj to set U and edge (UI,vj) to set D, and mark visited[vj]=1
-
Repeat step 2 until U is equal to V, that is, all vertices are marked as visited, and D has n-1 edges
4. Practice (Prim algorithm)- road repair problem
-
There are 7 villages (A, B, C, D, E, F, G) in Shengli township. Now roads need to be built to connect the 7 villages
-
The distance of each village is represented by A line (weight), for example, A — B is 5 km away
-
Q: How can roads be built so that villages can be connected and the total length of road built can be minimized?
5. Code implementation
public class PrimAlgorithm {
public static void main(String[] args) {
// Test to see if the graph is created OK
char[] data = new char[] {'A'.'B'.'C'.'D'.'E'.'F'.'G'};
int verxs = data.length;
// The relation of the adjacency matrix is expressed by the two-dimensional array,10000 is the large number, indicating that the two points are not connected
int[][] weight = new int[] [] {{10000.5.7.10000.10000.10000.2},
{5.10000.10000.9.10000.10000.3},
{7.10000.10000.10000.8.10000.10000},
{10000.9.10000.10000.10000.4.10000},
{10000.10000.8.10000.10000.5.4},
{10000.10000.10000.4.5.10000.6},
{2.3.10000.10000.4.6.10000}};// Create the MGraph object
MGraph graph = new MGraph(verxs);
// Create a MinTree object
MinTree minTree = new MinTree();
minTree.createGraph(graph, verxs, data, weight);
/ / output
minTree.showGraph(graph);
// Test the Prim algorithm
minTree.prim(graph, 1); }}/** * Create minimum spanning tree -> graph of village */
class MinTree {
/** * Creates the graph's adjacency matrix **@paramGraph Graph object *@paramNumber of verxs graph corresponding vertices *@paramThe values of the vertices of the data graph *@paramThe adjacency matrix of the weight graph */
public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
int i, j;
for (i = 0; i < verxs; i++) {
graph.data[i] = data[i];
for (j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; }}}/** * displays the graph's adjacency matrix **@param graph
*/
public void showGraph(MGraph graph) {
int[][] weight = graph.weight;
for (int[] link : weight) { System.out.println(Arrays.toString(link)); }}/** * write prim algorithm, get minimum spanning tree **@paramGraph drawing *@paramV means at which vertex of the graph A-> 0 B-> 1 */ is generated
public void prim(MGraph graph, int v) {
//visited If the node (vertex) has been visited
int[] visited = new int[graph.verxs];
// Visited The default element values are 0, indicating that it has not been visited
for (int i = 0; i < graph.verxs; i++) {
visited[i] = 0;
}
// Mark the current node as accessed
visited[v] = 1;
H1 and h2 record the subscripts of the two vertices
int h1 = -1;
int h2 = -1;
// Initialize minWeight to a large number, which will be replaced later in the loop
int minWeight = 10000;
// Because there are gragh. Verxs verxs vertices, there are graph.verxS-1 edges after the prim algorithm is finished
for (int k = 0; k < graph.verxs; k++) {
// Determine which node is closest to the subgraph generated each time
// the I node represents the node that has been accessed
for (int i = 0; i < graph.verxs; i++) {
// the j node represents a node that has not been accessed
for (int j = 0; j < graph.verxs; j++) {
if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
// Replace minWeight(find the edge with the least weight between already accessed nodes and unaccessed nodes)minWeight = graph.weight[i][j]; h1 = i; h2 = j; }}}// Find an edge that is the smallest
System.out.println("Edge" " + graph.data[h1] + "," + graph.data[h2] + "> weights." + minWeight);
// Mark the current node as visited
visited[h2] = 1;
// Set minWeight to 10000
minWeight = 10000; }}}class MGraph {
/** * indicates the number of nodes */
int verxs;
/** * Store node data */
char[] data;
/** * is our adjacency matrix */
int[][] weight;
public MGraph(int verxs) {
this.verxs = verxs;
this.data = new char[verxs];
this.weight = new int[verxs][verxs]; }}Copy the code