6. Prim algorithm

Application Scenario – Road repair

Take a look at an application scenario and problem:

  1. 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
  2. The distance of each village is represented by A line (weight), for example, A — B is 5 km away
  3. Q: How can roads be built so that villages can be connected and the total length of road built can be minimized?

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.

Minimum spanning tree

The problem of road construction is essentially a Minimum Cost Spanning Tree (MST) problem. 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

  1. N vertices, there must be N minus 1 edges
  2. Contains all vertices
  3. The N minus one edges are all in the diagram
  4. For example (see figure 🙂
  5. The algorithms for minimum spanning tree are prim algorithm and Kruskal algorithm

introduce

Prim algorithm is used to find the minimum spanning tree, that is, in a connected graph containing n vertices, to find the connected subgraph with only (n-1) edges containing all N vertices, that is, the so-called minimal connected subgraph Prim algorithm is as follows:

  1. 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
  2. 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
  3. 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
  4. Repeat step 2 until U is equal to V, that is, all vertices are marked as visited, and D has n-1 edges
  5. Tip: it’s hard to understand the steps alone. Let’s explain them in code.
  6. Graphic Prim algorithm

code

  1. 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
  2. The distance of each village is represented by A line (weight), for example, A — B is 5 km away
  3. Q: How can roads be built so that villages can be connected and the total length of road built can be minimized?
/** * @author DSH * @date 2020/10/9 * @description */ public class PrimAlgorithm {public static void The main (String [] args) {/ / test figure is creating A successful char [] data = new char [] {' A ', 'B', 'C', 'D', 'E', 'F', 'G'}; int verxs = data.length; / / the relationship between the adjacency matrix using two-dimensional array, said 10000 indicates two points is not connected int [] [] weight = new int [] [] {,5,7,10000,10000,10000,2 {10000}, 5100, 00100, 00,9,10000,10000,3 {}, {7100, 00100, 00100 00,8,10000,10000}, {10000,9,10000,10000,10000,4,10000}, 00,8,10000,10000,5,4} {10000100, 10000100, 00100, 00,4,5,10000,6 {}, {2,3,10000,10000,4,6,10000}}; // Create a MGraph object MGraph MGraph = new MGraph(verxs); MinTree = new MinTree(); minTree.createGraph(mGraph,verxs,data,weight); / / output minTree. ShowGraph (mGraph); Mintree. prim(mGraph,0); //<A,G,B,E,F,D,C>}} // create minimum spanning tree -> graph class MinTree{// create graph adjacency matrix /** ** @param graph object * @param verxs graph corresponding number of vertices * Public void createGraph(MGraph graph,int verxs, char data[], int[][] weight){ int i,j; for (i = 0; i < verxs; Graph. Data [I] = data[I]; for (j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; Public void showGraph(MGraph graph){for (int[] link: graph.weight) { System.out.println(Arrays.toString(link)); Public void prim(MGraph graph,int v){//1. Int [] visited = new int[graph.verxs]; // Visited [] defaults to 0, indicating that it has not been visited. Int h1 = -1; int h2 = -1; int minWeight = 10000; // Start minWeight as a large number and replace it with for (int k = 1; k < graph.verxs; K++) {for (int I = 0; for (int I = 0; i < graph.verxs; For (int j = 0; int j = 0; j < graph.verxs; If (visited[I]==1 && visited[j]==0 && graph. Weight [I][j]<minWeight){// j <minWeight; // Replace minWeight = graph.weight[I][j]; // Replace minWeight with graph. h1 = i; h2 = j; System.out.println(" edge <" + graph.data[h1] + "," + graph.data[h2] + "> weight :"+minWeight); // Mark the current node as visited[h2] = 1; // reset minWeight minWeight = 10000; }} // create adjacency matrix class MGraph{int verxs; Char [] data; // Save node data int[][] weight; Public MGraph(int verxs) {this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; }}Copy the code

The output

The < > A, G weight: 2 < G, B > weight: 3 < G, E > weight: 4 < E, F > weight: 5 < F, D > weight: 4 < A, C > weight: 7Copy the code

7. Kruskal algorithm

Application scenario – Bus station problem

Take a look at an application scenario and problem:

  1. 7 new sites (A,B,C,D,E,F,G) have been added to A city. Now roads need to be built to connect the 7 sites
  2. The distance of each station is represented by A line (weight), for example, the distance between A and B is 12 km
  3. Q: How can roads be built to ensure that all stops are connected and the total length of road built is the shortest?

Kruskal algorithm introduction

  1. Kruskal algorithm is used to find the minimum spanning tree of the weighted connected graph.
  2. Basic idea: select n-1 edges in order of weight from small to large, and ensure that the n-1 edges do not constitute a loop
  3. Specific approach: first, construct a forest containing only N vertices, and then according to the weight from small to large, select edges from the network to join the forest, and make the forest does not generate a loop, until the forest becomes a tree

Kruskal’s algorithm illustrated

The principle and steps of Kruskal algorithm are illustrated with the urban bus station problem:

If n-1 edges are selected from a connected graph with n vertices to form a minimal connected subgraph, and the sum of weights of n-1 edges in the connected subgraph is minimized, it is called the minimum spanning tree of a connected network.

For example, for a connected network as shown in figure G4, there can be multiple spanning trees with different summation weights.

Kruskal algorithm diagram

Kruskal is illustrated in Figure G4 above (assuming that the array R holds the minimum spanning tree result).

  • Step 1: Add edges

    to R. Edge

    has the lowest weight, so it is added to the minimum spanning tree result R.
    ,f>
    ,f>
  • Step 2: Add edges

    to R. After the previous step, edge

    has the least weight, so it is added to the minimum spanning tree result R.
    ,d>
    ,d>
  • Step 3: Add edges

    to R. After the previous step, edge

    has the least weight, so it is added to the minimum spanning tree result R.
    ,e>
    ,e>
  • Step 4: Add edges

    to R. After the previous operation, edge

    has the lowest weight, but

    will form a loop with the existing edge. Therefore, skip the edge

    . By the same token, the jump
    ,e>
    ,e>
    ,e>
    ,f>

Edge > < C, F. Add edges <B,F> to the minimum spanning tree result R.

  • Step 5: Add edges

    to R.
    ,g>

After the previous step, edge <E,G> has the least weight, so it is added to the minimum spanning tree result R.

After the previous operation, edge <F,G> has the lowest weight, but <F,G> will form a loop with the existing edge. Therefore, skip the edge <F,G>. Similarly, skip edge <B,C>. Add edges <A,B> to the minimum spanning tree result R.

At this point, the minimum spanning tree construction is complete! It includes the following edges :<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>.

Kruskal algorithm analysis

According to the basic idea and practice of Kruskal algorithm introduced in front, we can understand that kruskal algorithm focuses on the following two problems to be solved: all edges of a pair of graphs are sorted according to the weight size. The second problem is how to judge whether a loop is formed when an edge is added to a minimum spanning tree. Problem one is very easy to solve, the sorting algorithm can be used to sort. Problem two is handled by recording the endpoint of a vertex in the “minimum spanning tree”. The endpoint of a vertex is the “maximum vertex connected to it in the minimum spanning tree”. Then, every time an edge needs to be added to the minimum survival tree, it is determined whether the end points of the two vertices of the edge coincide, which will form a loop.

How to decide whether to construct a loop – give an example (see figure)

After adding



to the minimum spanning tree R, the vertices of these edges have an endpoint: (01) C has an endpoint F (02) D has an endpoint F (03) E has an endpoint F (04) F has an endpoint F
,e>
,d>
,f>

Note about the end point:

  1. That is, after arranging all the vertices in order from smallest to largest; The end point of a vertex is the “largest vertex connected to it”.
  2. So, next, although

    is the least weighted edge. However, the end point of C and E is F, that is, they have the same end point. Therefore, if

    is added to the minimum spanning tree, a loop will be formed. So that’s how you identify the loop. That is, the two vertices of the edge we are adding cannot both point to the same end point, or they will form a loop. [There is code description at the back]
    ,e>
    ,e>

Kruskal Best Practice – Bus station issues

Look at a bus stop problem:

  1. There are 7 new stations (A,B,C,D,E,F,G) in Beijing. Now roads need to be built to connect the 7 stations
  2. The distance of each station is represented by A line (weight), for example, the distance between A and B is 12 km
  3. Q: How can roads be built to ensure that all stops are connected and the total length of road built is the shortest?
  4. Code implementation and annotations
/** * @author DSH * @date 2020/10/9 * @description public class KruskaCase {private int edgeNum; Private char[] vertexs; Private int[][] martix; Private static final int INF = integer.max_value; private static final int INF = integer.max_value; public static void main(String[] args) { char[] vertexts = {'A','B','C','D','E','F','G'}; / / int kruskal algorithm of adjacency matrix matrix [] [] = {/ * A * / {0, 12, INF, INF, INF, 16, 14}, / * B * / {12, 0, 10, INF, INF, 7, INF}, /*C*/ { INF, 10, 0, 3, 5, 6, INF}, /*D*/ {INF, INF, 3, 0, 4, INF, INF}, /*E*/ {INF, INF, 5, 4, 0, 2, 8}, /*F*/ {16, 7, 6, INF, 2, 0, 9}, /*G*/ {14, INF, INF, INF, 8, 9, 0} }; KruskaCase = new KruskaCase(Vertexts, matrix); // Print the constructed matrix kruskacase.print (); // Sequence test code // EData[] edges = kruskacase.getedges (); // System.out.println(" before "+ array.tostring (edges)); // kruskaCase.sortEdges(edges); // System.out.println(" array after "+ array.tostring (edges)); kruskaCase.kruskal(); } public KruskaCase(char[] vertexs, int[][] martix) {vlen = vertexs.length; Vertexs = new char[vlen]; vertexs = new char[vlen]; for (int i = 0; i < vlen; i++) { this.vertexs[i] = vertexs[i]; } this.martix = new int[vlen][vlen]; for (int i = 0; i < vlen; i++) { for (int j = 0; j < vlen; j++) { this.martix[i][j] = martix[i][j]; For (int I = 0; i < vlen; i++) { for (int j = i+1; j < vlen; j++) { if (this.martix[i][j]! =INF){ edgeNum++; }}}} // sortEdges, bubble sort private void sortEdges(EData[] edges){for (int I = 0; i < edges.length-1; i++) { for (int j = 0; j < edges.length-1-i; j++) { if (edges[j].weight>edges[j+1].weight){ EData temp = edges[j]; edges[j] = edges[j+1]; edges[j+1] = temp; }}}} /** ** @param the values of vertices passed in by ch such as 'A', 'B', etc. * @return returns the indices corresponding to the ch vertex, Private int getPosition(char ch){for (int I = 0; private int getPosition(char ch){for (int I = 0; i < vertexs.length; i++) { if (vertexs[i]==ch){ return i; } } return -1; } / * * * to get the edges in the graph on the EData [] array, the array need to traverse the * by matrix adjacency matrix to get * EData form of [] [{' A ', 'B', '12'}...].  * @return */ private EData[] getEdges(){ int index = 0; EData[] edges = new EData[edgeNum]; for (int i = 0; i < vertexs.length; i++) { for (int j = i+1; j < vertexs.length; j++) { if (martix[i][j]! =INF){ edges[index++] = new EData(vertexs[i],vertexs[j],martix[i][j]); } } } return edges; } /** * get the end of a vertex with subscript I to determine if the ends are the same * @param ends Private int getEnd(int[] ends,int I){private int getEnd(int[] ends,int I){private int getEnd(int[] ends,int I){ while (ends[i]! =0){ i = ends[i]; } return i; } // public void kruskal(){ int index = 0; Int ends[] = new int[edgeNum]; int ends[] = new int[edgeNum]; EData[] rets = new EData[edgeNum]; EData[] edges = getEdges(); EData[] edges = getEdges(); // sortEdges according to their weights (from small to large); // Add edges to the minimum spanning tree. If not, add edges to rets. i < edgeNum; Int p1 = getPosition(edges[I].start); Int p2 = getPosition(edges[I].end); Int m = getEnd(ends,p1); int m = getEnd(ends,p1); Int n = getEnd(ends,p2); int n = getEnd(ends,p2); If (m! < span style = "box-sizing: border-box! Important; / / set the end of a m in the existing minimum spanning tree > < E, F,0,0,0,0,0,0,0,0,0,0,0 [0] = >,0,0,0,5,0,0,0,0,0,0,0 [0] (F) is the end point of the E of rets [index++] = edges [I]; // Count and print "minimum spanning tree ", rets system.out.println (" minimum spanning tree "); for (int i = 0; i < index; i++) { System.out.println(rets[i]); } // system.out. println(" minimum spanning tree = "+ array.tostring (rets)); Public void print(){system.out.println (" the adjacency matrix is :"); for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { System.out.printf("%15d",martix[i][j]); } System.out.println(); Class EData{char start; // Create a class EData whose object instance represents an edge. // Char end; // End of edge (another point) int weight; Public EData(char start, char end, int weight) {this.start = start; this.end = end; this.weight = weight; } @Override public String toString() { return "EData{" + "<" + start + ", " + end + ">=" + weight + '}'; }}Copy the code

8. Dijkstra algorithm

Application Scenario – Shortest path problem

Take a look at an application scenario and problem:

  1. During the war, there were seven villages (A,B,C,D,E,F,G) in Shengli Township. Now there are six postmen who need to deliver mail from point G to six villages (A,B,C,D,E,F)
  2. The distance of each village is represented by A line (weight), for example, A — B is 5 km away
  3. Q: How do you calculate the shortest distance from village G to other villages?
  4. What is the shortest distance from any other point to any other point?

Dijkstra algorithm is introduced

Dijkstra algorithm is a typical shortest path algorithm used to calculate the shortest path from one node to other nodes. Its main feature is that it spreads out from the starting point (the breadth-first search idea) until it reaches the end point.

Dijkstra algorithm process

  1. Set the starting vertex to v, the set of vertices v {v1,v2,vi… }, the distance from v to the vertices of v constitutes the distance set Dis, Dis{d1,d2,di… }, the Dis set records the distance from v to each vertex in the graph (to itself can be regarded as 0, the distance from v to vi corresponds to di)
  2. Select di with the smallest value from Dis and remove Dis set, and remove the corresponding vertex vi in V set at the same time. In this case, V to vi is the shortest path
  3. Update Dis set, the update rule is: compare the distance value from V to the vertex in V set with the distance value from V to the vertex in V set via vi, keep the smaller one (at the same time, the precursor node of the vertex should also be updated as vi, indicating that it is reached through VI)
  4. Repeat the two steps until the shortest path vertex is the target vertex

Best application of Dijkstra algorithm – shortest path

  1. During the war, there were seven villages (A,B,C,D,E,F,G) in Shengli Township. Now there are six postmen who need to deliver mail from point G to six villages (A,B,C,D,E,F)
  2. The distance of each village is represented by A line (weight), for example, A — B is 5 km away
  3. Q: How do you calculate the shortest distance from village G to other villages?
  4. What is the shortest distance from any other point to any other point?
  5. Dijkstra algorithm is analyzed by graphic method

Code implementation

/** * @author DSH * @date 2020/10/10 * @description */ public class DijkstraAlogrithm {public static void main(String[] args) { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; Int [][] matrix = new int[vertex.length][vertex.length]; final int N = 65535; / / say not connection matrix [0] = new int [] {N, 5, 7, N, N, N, 2}; matrix[1] = new int[]{5, N, N, 9, N, N, 3}; matrix[2] = new int[]{7, N, N, N, 8, N, N}; matrix[3] = new int[]{N, 9, N, N, N, 4, N}; matrix[4] = new int[]{N, N, 8, N, N, 5, 4}; matrix[5] = new int[]{N, N, N, 4, 5, N, 6}; matrix[6] = new int[]{2, 3, N, N, 4, 6, N}; Graph graph = new graph (vertex, matrix); // Test the adjacency matrix to display graph.showgraph (); graph.dijkstra(6); // Start vertex is G graph.showdijistra (); Class Graph {char[] vertex; // array int[][] matrix; // Adjacency matrix VisitedVertex VisitedVertex; public Graph(char[] vertex, int[][] matrix) { this.vertex = vertex; this.matrix = matrix; Public void showGraph() {for (int[] link: matrix) {system.out.println (arrays.toString (link)); }} public void dijkstra(int index){visitedVertex = new VisitedVertex(vertex.length, index); update(index); For (int j = 0; j < vertex.length; j++) { index = visitedVertex.updateArr(); // Select and return a new access vertex update(index); Private void update(int index){int len = 0; private void update(int len = 0); // for (int j = 0; j < matrix[index].length; j++) { len = visitedVertex.getDis(index)+matrix[index][j]; // If the j vertex is not visited and len is less than the distance from the starting vertex to the j vertex, we need to update if (! visitedVertex.in(j) && len < visitedVertex.getDis(j)){ visitedVertex.updatePre(j,index); // Update j vertex visitedVertex. UpdateDis (j,len); }} public void showDijistra(){visitedVertex. Show (); Public int[] already_arr; public int[] already_arr; public int[] already_arr; Public int[] pre_visited; public int[] pre_visited; Dis public int[] dis public int[] dis public int[] dis; Public VisitedVertex(int length,int index) {public VisitedVertex(int length,int index) { this.already_arr = new int[length]; this.pre_visited = new int[length]; this.dis = new int[length]; // Initialize dis array. Fill (dis,65535); this.already_arr[index] = 1; This. dis[index] = 0; // Set the access distance of the starting vertex to 0} Public Boolean in(int index){return already_arr[index] {return already_arr[index] = = 1; } /** * public void updateDis(int index,int len){dis[index]  = len; } /** * @param pre * @param index */ public void updatePre(int pre, int index){ pre_visited[pre] = index; } @param index */ public int getDis(int index){return dis[index]; } @return */ public int updateArr(){int min = 65535, index = 0; for (int i = 0; i < already_arr.length; i++) { if (already_arr[i] == 0 && dis[i] < min){ min = dis[i]; index = i; Already_arr [index] = 1; already_arr[index] = 1; return index; } / * * * * shows the final results of the three arrays of output * / public void show () {System. Out. Println (" = = = = = = = = = = = = = = = = = "); //already_arr for (int i = 0; i < already_arr.length; i++) { System.out.print(already_arr[i]+" "); } System.out.println(); //pre_visited for (int pre: pre_visited) { System.out.print(pre+" "); } System.out.println(); //dis for (int d: dis) { System.out.print(d+" "); } System.out.println(); / / output sort char [] vertex = {' A ', 'B', 'C', 'D', 'E', 'F', 'G'}; int count = 0; for (int d: dis) { if (d! =65535){ System.out.print(vertex[count]+"("+d+") "); }else { System.out.print("N"); } count++; } / / the output (2) B (3) C (9) (10) D E (4), F (0) System. (6) G out. The println (); }}Copy the code