Check and set

“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

What is a concurrent search set

One simple example is that families are formed by people of the same blood (never mind the family drama!).

  1. If two people have no family but are of the same blood, they form a family

  1. If someone is related to a family, add him to the family

  1. If we find people from two different families who share the same blood, we merge the two families into one

What you end up with is that the families are really not related anymore

Sum up and check the set is:

  1. And find the set can be set merge operation (and)
  2. And look up the set to find which set the element is in (look up)
  3. And looking up sets maintains a bunch of sets (sets)

In-depth understanding based on the specific scenario

The above examples only have a preliminary understanding, specific how to use and how to consider, you can learn more effectively in the following examples.

background

Redundant links

A tree can be thought of as a connected and acyclic undirected graph.

Given the graph after adding an edge to a tree with n nodes (values 1 to n). The two vertices of the added edge are contained between 1 and n, and the added edge does not belong to an existing edge in the tree. Edges [I] = [ai, bi] indicates that there is an edge between AI and BI in the graph. Find an edge that can be deleted so that the remainder is a tree with n nodes. If there are more than one answer, the last edge present on the array edges is returned.

Edges input: edges = [[1,2], [1,3], [2,3]

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] output: [1, 4]

Subject analysis

There are n points and n edges, and if there were no rings there would only be n minus 1 edges

Our task is to delete an edge, but not to make any point isolated and disconnected

It can be considered to select the two points on each edge according to the order in which the edges appear, and set them as A and B for analysis

There are three cases:

  1. Neither point has been visited by Ben, so we let A be the parent node, B be the child node, and AB form A tree

And set point AB access to true

  1. One node has been accessed. For example, node B has been accessed but node A has not been accessed

So B could be the root of A tree, A leaf, or an intermediate node, but either way you just have to make A’s father B, so A is A member of B’s family and set B to true

  1. Both A and B have been visited. (1) We first look for the root nodes of nodes A and B to see whether they belong to the same family. If they belong to the same family, it means that they have been linked, so this side is redundant

    (2) If the A and B families are different, we can merge the A and B families. We can merge the root of the B family into A node, or the head of the A node

The problem solving code

public int[] findRedundantConnection(int[][] edges) { boolean[] visited=new boolean[edges.length+1]; HashMap<Integer,Integer>map=new HashMap<>(); For (int I = 0; for (int I = 0; i < edges.length; i++) { int a=edges[i][0]; int b=edges[i][1]; If (visited [a] = = false && visited [b] = = false) {/ / neither belong to the map. The put (b, a); Map. put(a,-1); // Visited [a]=true; // Visit [a]=true; visited[b]=true; }else if(visited[a]==false){ map.put(a,b); visited[a]=true; }else if(visited[b]==false){ map.put(b,a); visited[b]=true; }else { int rootOfA=getRoot(a,map); int rootOfB=getRoot(b,map); if(rootOfA==rootOfB)return edges[i]; map.put(rootOfB,rootOfA); }} return null; } public int getRoot(int cur,HashMap<Integer,Integer>map){ if(map.get(cur)==-1)return cur; return getRoot(map.get(cur),map); }Copy the code

And look up the classic case of set – Kruskal algorithm

Introduction to Kruskal algorithm

Kruskal algorithm is an algorithm for finding minimum spanning trees (algorithms for finding minimum spanning trees of weighted connected graphs). In all the remaining unselected edges, find the smallest edge. If it forms a loop with the selected edge, discard it and select the next smallest edge.

The specific operation process is as follows:

  1. Remove all the connecting lines from the graph, leaving only the vertices
  2. Find the edge with the lowest weight from the edge set of the graph and connect the two vertices of the edge
  3. Continue to find the edge with the lowest weight and connect the two vertices. If the selected edge causes a loop in the minimum spanning tree, the edge is abandoned and the edge with the lowest value is selected
  4. Until all vertices are joined together and there are no loops, a minimum spanning tree is generated.

Two core questions

The first problem is to sort all edges of a pair of graphs according to their weights.

Sorting directly with the sorting algorithm, or building a minimum heap, is also a good choice.

The second problem is how to judge whether a loop is formed when an edge is added to a minimum spanning tree.

The core idea is to record processing, using and look up the set processing thought

The way to do this is to record the end point of a vertex in the minimum spanning tree. The end point of a vertex is the largest 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.

Full version code

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; Class Edge implements Comparable<Edge> {private int begin; Private int end; // private int weight; public Edge(int begin, int end, int weight) { this.begin = begin; this.end = end; this.weight = weight; } public int getBegin() { return begin; } public void setBegin(int begin) { this.begin = begin; } public int getEnd() { return end; } public void setEnd(int end) { this.end = end; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } @Override public int compareTo(Edge o) { if (o.weight > this.weight) { return -1; } else { return 1; }} public class Kruskal {public static void main(String[] args) {List<Edge> List = new ArrayList<>(); int[][] arr = new int[][]{ {-1, 4, 0, 0, 0, 0, 0, 8, 0}, {0, -1, 8, 0, 0, 0, 0, 11, 0}, {0, 0, -1, 7, 0, 4, 0, 0, 2}, {0, 0, 0, 1, 9, 14, 0, 0, 0}, {0, 0, 0, 0, 1, 10, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 2, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 6}, {0, 0, 0, 0, 0, 0, 0, 1, 7}, {0, 0, 0, 0, 0, 0, 0, 0, 1}}; for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i][j] > 0) { list.add(new Edge(i, j, arr[i][j])); } } } Collections.sort(list); Int [] parent = new int[arr.length]; int[] parent = new int[arr. for (int i = 1; i < arr.length; i++) { parent[i] = -1; } int m = 0, n = 0; For (Edge Edge: list) {// Find (parent, edge.getbegin ()); n = find(parent, edge.getEnd()); if (m ! = n ) { parent[m] = n; System. The out. Println (" add edge (" + edge. GetBegin () + ", "+ edge. GetEnd () +") weight "+ edge. GetWeight ()); } } System.out.println(Arrays.toString(parent)); } private static int find(int[] parent, int ch) { while (parent[ch] > 0) { ch = parent[ch]; } return ch; }}Copy the code

Code result output

Add edge (6,7) weight 1 add edge (2,8) weight 2 add edge (5,6) weight 2 add edge (0,1) weight 4 add edge (2,5) weight 4 add edge (2,3) weight 7 add edge (0,7) weight 8 add edge (3,4) weight 9 [1, 3, 8, 4, -1, 7, 7, 3, 7] Process finished with exit code 0Copy the code