Writing in the front

  • Full text of data structure and algorithm

Road repair problem (Prim algorithm)

  • Minimum spanning tree, given a weighted undirected connected graph, how to select a spanning tree to minimize the sum of all edge weights in the tree; N vertices, N minus 1 edges
  • Prim algorithm, in the connected graph containing n vertices, find only n-1 edges, including all n vertices of the connected subgraph, minimal connected subgraph
  • The minimum spanning tree is created, and the minimum weight is selected between each vertex as the connected point. Because every vertex has two statesVisited/not visitedSo two floorsThe for loop, ensuring that all vertices are scanned and passedmGraph.weight[i][j] < minWeight, to ensure that the edge obtained (the edge growing outward) must be the smallest in the next subgraph traversal
Class MinTree {** * @param graph object * @param verxs fixed point * @param data fixed point value * @param weight graph adjacency matrix */ public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) { for (int i = 0; i < verxs; i++) { graph.data[i] = data[i]; for (int 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 mGraph, int v) {public void prim(mGraph mGraph, int v) { Int visited[] = new int[mgraph.verxs]; // The current node is marked as visited[v] = 1; Int h1 = -1; int h2 = -1; Int minWeight= 10000; int minWeight= 10000; int sumWeight = 0; for (int k = 1; k < mGraph.verxs; MGraph. Verxs -1 // To generate n-1 edges, that is, to traverse n-1 times, to find the edge with the least weight each time // once for each loop, For (int I = 0; for (int I = 0; for (int I = 0; i < mGraph.verxs; I ++) {// Visited [I] == 1, for (int j = 0; j < mGraph.verxs; J ++) {// visited[j] == 0 If (visited[I] == 1 && visited[j] == 0 && mGraph. Weight [I][j] < minWeight) {// Find nodes that have been visited and nodes that have not been visited. MinWeight = mGraph. Weight [I][J]; h1 = i; h2 = j; Println (" edge <" + mgraph.data [h1] + "," + mgraph.data [h2] + "> weight :" + minWeight); // Mark the current node as visited[h2] = 1; sumWeight += minWeight; // reset minWeight to find the next subgraph minWeight = 10000; } System.out.println(sumWeight); }}Copy the code
  • figure
class MGraph { int verxs; Char [] data; Int [][] weight; Public MGraph(int verxs) {this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; }}Copy the code
  • call
char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int verxs = data.length; / / describe the adjacency matrix, 10000 indicates the disconnected int [] [] weight = {/ / A B C D E F G {10000,5,7,10000,10000,10000,2}. / / A 5100, 00100, 00,9,10000,10000,3 {}, {7100, 00100, 00100 00,8,10000,10000} / / B, / / C {10000,9,10000,10000,10000,4,10000}. / / D {10000100 00,8,10000,10000,5,4}, {10000100, 00100, 00,4,5,10000,6} / / E, / / F,3,10000,10000,4,6,10000} {2} / / G; MGraph mGraph = new MGraph(verxs); MinTree minTree = new MinTree(); minTree.createGraph(mGraph,verxs,data,weight); minTree.showGraph(mGraph); minTree.prim(mGraph,1);Copy the code

Bus Station Problem (Kruskal algorithm)

  • Generates a minimum spanning tree
  • Firstly, a forest containing only N vertices is constructed, and then, according to the weight, edges are selected from the network to join the forest, and no loops are generated in the forest until the forest becomes a tree
  • The idea is to sort all of the edges in the graph, in order to get the edges that cover all of the points, in other words, the edges in the graph can’t have a loop, because a loop means that these two points are already on this path, but they join again through this loop, and the joining of this edge is wasted
class Krusal { private int edgeNum; Private char[] vertexs; Private int[][] matrix; Private static final int INF = integer. MAX_VALUE; private static final int INF = integer. MAX_VALUE; Public Krusal(char[] vertexs, int[][] matrix) {// vlen = vertexs.length; this.vertexs = new char[vlen]; for (int i = 0; i < vlen; i++) { this.vertexs[i] = vertexs[i]; } this.matrix = new int[vlen][vlen]; for (int i = 0; i < vlen; i++) { for (int j = 0; j < vlen; j++) { this.matrix[i][j] = matrix[i][j]; For (int I = 0; i < vlen; i++) { for (int j = i+1; j < vlen; j++) { if (this.matrix[i][j] ! = INF) { edgeNum ++; }}}} // algorithm // Public void krusalAlgorithm() {int index = 0; Int [] ends = new int[vertexs.length]; int[] ends = new int[vertexs.length]; EData[] res = new EData[edgeNum]; EData[] edges = getEdges(); // Sort, algorithm for edges sortEdges(edges); For (int I = 0; for (int I = 0; i < edgeNum; Int p1 = getPosition(edges[I].start); Int p2 = getPosition(edges[I].end); Int m = getEnd(ends, p1); Int n = getEnd(ends, p2); int n = getEnd(ends, p2); // If the end of p1 and p2 is not one, the new edge can be added to the path, and the end of P1, m, points to the end of P2, n // since the method 'getEnd' is used to find while, // If the path to be added is the end point n of P1 and P2, since N is not added, the end point is itself // by 'getEnd', the end point of P1 is found by finding the end point of P1, // then these points are all on the same path. If (m! < span style = "max-width: 100%; clear: both; min-height: 1em; res[index++] = edges[i]; }} // count and print the minimum spanning tree // Enter n-1 edges, the last one is vertexs.length-2, but it is [), Spliterator<EData> Spliterator = Arrays. Spliterator (res, 0, vertexs.length-1);  spliterator.forEachRemaining(eData -> System.out.println(eData)); } public void print() { for (int i = 0;  i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { System.out.printf("%13d", matrix[i][j]);  } System.out.println(); }} public void sortEdges(EData[] edges) {// If the edges are not aligned with the edges, then the edges are not aligned with the edges. Edges. Length -1 +1 -i 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;}}}} // Enter the vertex value, return the corresponding subindex public int getPosition(char ch) {for (int I = 0;  i < vertexs.length; i++) { if (vertexs[i] == ch) { return i; } } return -1; } public 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; His j++) {/ / to skip, and will not be repeated Such as I = 0 scanning j = 6; I = 1 scanning,3,4,5,6 if j = 2 (matrix [I] [j]. = INF) { edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; } // Obtain the endpoint of the vertex with subscript I, which is used to determine whether the endpoint of two vertices is the same // The array records the corresponding emphasis of each vertex, and is formed in the traversal process step by step, Public int getEnd(int[] ends, int I) {while (ends[I]!= 0) {I = ends[I];} return I;}}Copy the code
  • While class
class EData {
    char start; //起点
    char end; //终点
    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=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
Copy the code
  • call
char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; Int [] [] matrix = {/ / 0 said he / / A B C D E F G {0, 12, INF, INF, INF, 16, 14}, {12,0,10 INF, INF, 7, INF}, {INF, 10,0,3,5,6 INF}, {INF, INF, 3,0,4 INF, INF}, {INF, INF, 5,4,0,2,8}, {16,7,6 INF, INF, 16, 14}, {14, INF, INF, INF, 8,9,0}}; Krusal krusal = new Krusal(vertexs, matrix); krusal.krusalAlgorithm();Copy the code

summary

  • Both Prim and Kruskal are algorithms for finding a minimum spanning tree, which in my understanding is essentially finding a minimum path, which means that the path goes through all the points and has the minimum sum of weights along the path. So it’s important to note that in theIterate over all the points or edges, the added point can not be added repeatedly, and the added edge should be the smallest, and the above two algorithms are aimed at different angles
  • These two algorithms have a default big premiseEvery time you add a point to the path, you have to add a new point
  • Prim’s algorithm, for vertices, divides all vertices into two parts, one part isPoints already in the path (traversed points), one isPoints not on this path (points not traversed)So there is a two-layer for loop, which guarantees the above premise that every time a relationship occurs, it must beTraversed points and untraversed pointsTo retrieve theThe weight value between all traversed points and untraversed pointsAnd find the minimum weight value, and then add the new point to the traversed set. Since the points in the graph must have adjacent points, there is a hidden condition.It only takes n minus 1 edges to connect n points, so it only takes n minus 1 traversal, you can iterate over all the points, and that’s where the outer for loop comes from
  • Kruskal’s algorithm, for edges, does a lot of foreshadowing, but the most important thing isTake all the edges and sort themSo in this setup, it’s best to think of it as a directed graph and not take duplicate edges, by trying to add the shortest edges every time, but making sure that there’s a big premiseThe new point is going to be a brand new pointSo by recording the end point, there are three cases

One is a completely new edge that has no relation to the original edge, so the two vertices of the edge are itself, but one end must point to another (ends[m]=n, where m and n are p1 and p2 respectively)

The second case, a point on the side of this article has been included in the path, so if a vertex is a new point, that by the end [I] can only find itself, can also be added, because it is impossible to a whole new point appears in the ends of the array, then the end of the new point will point to the end of the path, so what’s the meaning of this sentence? Look at the explanation of the third case

In the third case, both points on this edge are already contained in the path, so this explains the end-adding feature of the ENDS array. If the ends array is added to A path, the end of the path is the same as any other end of the path. For example, if A path contains a-b and B-C, add a-c to the end of the path. Ends [A]=B, ends[B]=C, ends[B]=C, ends[A]=B, ends[B]=C This means that when both points are included in the path, the end of both points will be the end of the edge that was last successfully added. Correspondingly, in the second case, when detecting a new point, the end of the path cannot be returned, only itself can be returned

But it will have A question, if the finish is 0, that is the end of all the points are A, but it did limit at the outset, when get all the edge, small subscript to big subscript, the algorithm is based on the written rules down, because the ultimate goal to find so many combinations of shortest path, And this path can cover all the points