Algorithm [5] joint search of sets and graphs

And look up the set and map

Joint search set

  1. There are several types of samples a, b, C and d, assuming V
    2) In the parallel search set, each sample is considered to be in a separate set at the beginning
    3) The user can call the following two methods at any time:
    Boolean issameset (VX, V, y): query whether sample x and sample y belong to a set
    Void Union (V, x, V, y): merge all samples of the respective sets of X and Y into -- sets
  2. The lower the cost of the isSameSet and union methods, the better


Establish a map, where k is the node and v is the pointing node of the node

1. The first step is to integrate all their numbers into a set (each node forms a set separately)
2. In a set, each node is the representative node in its own set. When the set is merged, if it is decided to hang 2 under 1, only 1 node in the set where 2 is located points to itself, so 1 is the representative node of the set.
3. Since each set has a representative node of a set, you can judge whether it is in the same set through the representative node, or you can connect the representative node of another set to this set. At this time, the whole set has only one representative node to realize the integration of the set. (first, judge the number of elements and hang the set of few elements under the multi elements)
Optimization: in the process of upward lookup, all elements on the path are directly connected to the representative node.

import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code04_UnionFind {
	public static class Element<V> {//Add a package
		public V value;
		public Element(V value) {
			this.value = value;
	public static class UnionFindSet<V> {
		public HashMap<V, Element<V>> elementMap;//v is the value [user courseware], and Element is the Element [for your own use]
		public HashMap<Element<V>, Element<V>> fatherMap;//Parent node
		public HashMap<Element<V>, Integer> sizeMap;//How many nodes are there in the collection representing nodes
		public UnionFindSet(List<V> list) {
			elementMap = new HashMap<>();
			fatherMap = new HashMap<>();
			sizeMap = new HashMap<>();
			for (V value : list) {
				Element<V> element = new Element<V>(value);
				elementMap.put(value, element);
				fatherMap.put(element, element);//Each node is its own parent
				sizeMap.put(element, 1);//Each node is its own representative node
		private Element<V> findHead(Element<V> element) {
			Stack<Element<V>> path = new Stack<>();//The road along the way
			while (element != fatherMap.get(element)) {
				path.push(element);//Go all the way to the representative node
				element = fatherMap.get(element);
			while (!path.isEmpty()) {
                //Flattening, all nodes directly point to the representative nodes
				fatherMap.put(path.pop(), element);
			return element;
		public boolean isSameSet(V a, V b) {
			//See if a has registered. Each value has a corresponding element
			if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
				return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            // If a point has not been registered, it will not be searched
			return false;
		public void union(V a, V b) {
			if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
				//Find the representative node [header node] first
				Element<V> aF = findHead(elementMap.get(a));//Find the representative node of the element corresponding to a
				Element<V> bF = findHead(elementMap.get(b));//Represents the size of this combination in the node
				if (aF != bF) {
					int aSetsize = sizeMap. get(aHead);
                    int bSetSize = sizeMap . get(bHead);
                    // If bf is small, hang the small node on the large node and directly record in the subtropical high parents
                    if (aSetSize >= bSetSize) {
                        parents . put(bF, aF);
                        sizeMap. put(aF, aSetSize + bSetSize); .
                        sizeMap . remove(bF);
                    } else {
                        parents . put( aF, bF);
                        sizeMap . put(bHead, aSetSize + bSetSize);
                        sizeMap . remove(bF);

Island issue

There are only two values of 0 and 1 in a matrix. Each position can match its own up, down, left and right

  • Four positions are connected. If a piece of 1 is connected together, this part is called an island. How many islands are there in a matrix?
  • give an example:
    0 0 1 0 1 0
    1 1 1 0 1 0
    1 0 0 1 0 0
    0 0 0 0 0 0
    There are three islands in this matrix.
	public static int countIslands(Int[][] m){
	if(m == null || m[0] == null){
		return 0;
	int N = m.length;
	int M = m[0].length;
	int res = 0;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<M;j++{
			if(m[i][j] == 1){
	return res;

public static void infect(int[][]m,int i,int j,int N,int M){
	if(i<0 || i>=N||j<0||j>=M || m[i][j] != 1){
		return ;
	m[i][j] =2;

Sharding matrix, parallel

Core logic: cutting matrix. Divide into n blocks and record the boundary information

Let's Mark 2 near the knife as belonging to A. then when merging, let's see if ac is a set, no, but the knife is left and right, so it is merged into an island.


Record the boundary information, establish nodes, and then use the union set to judge how many sets there are


1) It consists of a set of points and a set of edges

2) Although there are the concepts of directed graph and undirected graph, they can be expressed by directed graph

3) There may be weights on the edges


public class Graph {
	public HashMap<Integer,Node> nodes;//Collection of points
	public HashSet<Edge> edges;//Set of edges

	public Graph() {
		nodes = new HashMap<>();
		edges = new HashSet<>();


public class Node {
	public int value;//Value of node
	public int in;//Penetration (how many nodes point to me)
	public int out;//Out degree (how many nodes do I point to)
	public ArrayList<Node> nexts;//The next level node that can be reached from me, the neighbor node
	public ArrayList<Edge> edges;//A collection of edges emanating from me

	public Node(int value) {
		this.value = value;
		in = 0;
		out = 0;
		nexts = new ArrayList<>();
		edges = new ArrayList<>();


public class Edge {
	public int weight;//What is the weight of this edge
	public Node from;//Where does this side start
	public Node to;//Where did this side arrive

	public Edge(int weight, Node from, Node to) {
		this.weight = weight;
		this.from = from; = to;


Graph generator:

public class GraphGenerator {

	public static Graph createGraph(Integer[][] matrix) {//Enter a matrix
		Graph graph = new Graph();//Initialize custom graph
		for (int i = 0; i < matrix.length; i++) {
			Integer weight = matrix[i][0];//Edge weights
			Integer from = matrix[i][1];//Sequence of from nodes
			Integer to = matrix[i][2];//Sequence of to nodes
			if (!graph.nodes.containsKey(from)) {//First check whether the from node exists. If it does not exist, create it
				graph.nodes.put(from, new Node(from));
			if (!graph.nodes.containsKey(to)) {//Then check whether the to node exists. If it does not exist, it will be established
				graph.nodes.put(to, new Node(to));
			Node fromNode = graph.nodes.get(from);//Take out the from point
			Node toNode = graph.nodes.get(to);//Take out some
			Edge newEdge = new Edge(weight, fromNode, toNode);//Create a new edge
			fromNode.nexts.add(toNode);//The adjacency point of from adds a to node
			fromNode.out++;//from plus 1;//to node penetration plus 1
			fromNode.edges.add(newEdge);//The edge set of the from node increases
			graph.edges.add(newEdge);//Add to the edge set of the whole graph
		return graph;


Breadth first traversal

1. Using queue
2. Start from the source node, enter the queue according to the width, and then pop up
3. For each pop-up point, put all adjacent points of the node that have not entered the queue into the queue
4. Wait until the queue becomes empty

public class Code_01_BFS {

	public static void bfs(Node node) {//Breadth first traversal
		if (node == null) {
		Queue<Node> queue = new LinkedList<>();
		HashSet<Node> map = new HashSet<>();
		while (!queue.isEmpty()) {
			Node cur = queue.poll();//Take out the current node
			System.out.println(cur.value);//Print current node
			for (Node next : cur.nexts) {//Traverse all adjacent points of the current node
				if (!map.contains(next)) {//If an adjacent node is already in the set, it is no longer needed


Depth first traversal

1. Using stack
2. Start from the source node, put the node into the stack according to the depth, and then pop up
3. For each pop-up point, put the next adjacent point of the node that has not been in the stack into the stack
4. Until the stack becomes empty

public class Code_02_DFS {

    public void dfs(Node node){
        if(node == null){
        Stack<Node> stack = new Stack<>();
        HashSet<Node> set = new HashSet<>();
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            for(Node next : cur.nexts){
                if(!set.contains(next)){//If there is no next node in the set, continue
                    stack.push(cur);//First put the current node back on the stack
                    stack.push(next);//Then put the next node into the stack
                    set.add(next);//Add the next node to the set
                    System.out.println(next.value);//Prints the value of the next node
                    break;//No longer continue the current loop, return to the while loop and continue the traversal of the next node


Topological sorting algorithm

Scope of application: it is required to have a directed graph, nodes with penetration of 0, and no ring

The logic of the implementation is: first find the nodes with a penetration of 0, then print them, and delete them immediately after printing, then continue to search the graph, find new nodes with a penetration of 0, and continue the previous operation until the graph is completely traversed.

public class Code_03_TopologySort {

	// directed graph and no loop
	public static List<Node> sortedTopology(Graph graph) {
		HashMap<Node, Integer> inMap = new HashMap<>();//Record all entry points
		Queue<Node> zeroInQueue = new LinkedList<>();//Record all nodes with a penetration of 0
		for (Node node : graph.nodes.values()) {//values means all the current points
			inMap.put(node,;//Register all entry points
			if ( == 0) {
				zeroInQueue.add(node);//Register all nodes with a penetration of 0
		List<Node> result = new ArrayList<>();
		while (!zeroInQueue.isEmpty()) {
			Node cur = zeroInQueue.poll();
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);//Find a new point with a penetration of 0
				if (inMap.get(next) == 0) {
		return result;

Minimum spanning tree and related algorithms

Several conceptual definitions of graphs:

Connected graph: in an undirected graph, if any two vertices vivi and vjvj have paths connected, the undirected graph is called a connected graph.
Strongly connected graph: in a directed graph, if any two vertices vivi and vjvj have paths connected, the directed graph is called strongly connected graph.
Connected network: in a connected graph, if the edges of the graph have a certain meaning, each edge corresponds to a number, which is called weight; Weight represents the cost of connecting vertices. This connected graph is called a connected network.
Spanning tree: the spanning tree of a connected graph refers to a connected subgraph, which contains all n vertices in the graph, but only enough n-1 edges to form a tree. A spanning tree with n vertices has only n-1 edges. If another edge is added to the spanning tree, it must be a ring.
Minimum spanning tree: in all spanning trees of a connected network, the cost of all edges and the minimum spanning tree are called minimum spanning trees.

Application scope of kruskal algorithm (K algorithm): undirected graph is required

1) Always start from the edge with the smallest weight and investigate the edge with the larger weight in turn
2) The current edge either enters the collection of the minimum spanning tree or is discarded
3) If the current edge enters the set of the minimum spanning tree and does not form a ring, the current edge is selected
4) If the current edge enters the set of the minimum spanning tree to form a ring, do not use the current edge
5) After examining all the edges, the set of the minimum spanning tree is also obtained

This algorithm can be called "edge adding method". The initial minimum number of spanning tree edges is 0. Each iteration selects a minimum cost edge that meets the conditions and adds it to the edge set of the minimum spanning tree.

All edges in the graph are sorted according to the cost from small to large;
The n vertices in the graph are regarded as a forest composed of independent n trees;
Select the edge from small to large according to the weight. If the two vertices UI, viui and VI connected by the selected edge belong to two different trees, they will become one edge of the minimum spanning tree, and the two trees will be merged as one tree.
Repeat (3) until all vertices are in a tree or have n-1 edges.

//undirected graph only
public class Code_04_Kruskal {

	// Union-Find Set
	public static class UnionFind {
		private HashMap<Node, Node> fatherMap;
		private HashMap<Node, Integer> rankMap;

		public UnionFind() {
			fatherMap = new HashMap<Node, Node>();
			rankMap = new HashMap<Node, Integer>();

		private Node findFather(Node n) {
			Node father = fatherMap.get(n);
			if (father != n) {
				father = findFather(father);
			fatherMap.put(n, father);
			return father;

		public void makeSets(Collection<Node> nodes) {
			for (Node node : nodes) {
				fatherMap.put(node, node);
				rankMap.put(node, 1);

		public boolean isSameSet(Node a, Node b) {
			return findFather(a) == findFather(b);

		public void union(Node a, Node b) {
			if (a == null || b == null) {
			Node aFather = findFather(a);
			Node bFather = findFather(b);
			if (aFather != bFather) {
				int aFrank = rankMap.get(aFather);
				int bFrank = rankMap.get(bFather);
				if (aFrank <= bFrank) {
					fatherMap.put(aFather, bFather);
					rankMap.put(bFather, aFrank + bFrank);
				} else {
					fatherMap.put(bFather, aFather);
					rankMap.put(aFather, aFrank + bFrank);

	public static class EdgeComparator implements Comparator<Edge> {

		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;


	public static Set<Edge> kruskalMST(Graph graph) {
		UnionFind unionFind = new UnionFind();
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
		for (Edge edge : graph.edges) {
		Set<Edge> result = new HashSet<>();
		while (!priorityQueue.isEmpty()) {
			Edge edge = priorityQueue.poll();
			if (!unionFind.isSameSet(edge.from, {
		return result;

Prim algorithm (P algorithm)

This algorithm can be called "point adding method". Each iteration selects the point corresponding to the edge with the lowest cost and adds it to the minimum spanning tree. The algorithm starts from a vertex s and gradually grows to cover all vertices of the whole connected network.

All vertex sets of the graph are VV; Initial order set u={s},v=V − uu={s},v=V − u;
Among the edges that can be composed of two sets u, VU and V, select the least cost edge (u0,v0)(u0,v0), add it to the minimum spanning tree, and incorporate v0v0 into set U.
Repeat the above steps until the minimum spanning tree has n-1 edges or n vertices.
Since points are added to the set u, the minimum cost edge must be updated synchronously; An auxiliary array closedge needs to be established to maintain the information of each vertex in set v and the least cost edge in set U

// undirected graph only
public class Code_05_Prim {

	public static class EdgeComparator implements Comparator<Edge> {

		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;


	public static Set<Edge> primMST(Graph graph) {
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(
				new EdgeComparator());
		HashSet<Node> set = new HashSet<>();
		Set<Edge> result = new HashSet<>();
		for (Node node : graph.nodes.values()) {
			if (!set.contains(node)) {
				for (Edge edge : node.edges) {
				while (!priorityQueue.isEmpty()) {
					Edge edge = priorityQueue.poll();//Pop the smallest edge from the priority queue
					Node toNode =;
					if (!set.contains(toNode)) {
						for (Edge nextEdge : toNode.edges) {
		return result;


Dijkstra's algorithm

Solve the shortest path problem of unit points: given the weighted directed graph G and source point v, find the shortest path from V to other vertices in G

Limiting condition: there is no edge with negative weight in graph G

The dijestra algorithm has done two things in total:

[1] Continuously run the breadth first algorithm to find the visible point and calculate the distance from the visible point to the source point

[2] Select the shortest length from the currently known paths and add its vertices to S as the vertices that determine the shortest path found.

// no negative weight
public class Code_06_Dijkstra {

	public static HashMap<Node, Integer> dijkstra1(Node from) {
		HashMap<Node, Integer> distanceMap = new HashMap<>();
		distanceMap.put(from, 0);
        //Selected nodes
		HashSet<Node> selectedNodes = new HashSet<>();

		Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
		while (minNode != null) {
			int distance = distanceMap.get(minNode);
			for (Edge edge : minNode.edges) {
				Node toNode =;
				if (!distanceMap.containsKey(toNode)) {
					distanceMap.put(toNode, distance + edge.weight);
				distanceMap.put(, Math.min(distanceMap.get(toNode), distance + edge.weight));
			minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
		return distanceMap;

	public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, 
			HashSet<Node> touchedNodes) {
		Node minNode = null;
		int minDistance = Integer.MAX_VALUE;
		for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
			Node node = entry.getKey();
			int distance = entry.getValue();
			if (!touchedNodes.contains(node) && distance < minDistance) {
				minNode = node;
				minDistance = distance;
		return minNode;

	public static class NodeRecord {
		public Node node;
		public int distance;

		public NodeRecord(Node node, int distance) {
			this.node = node;
			this.distance = distance;

	public static class NodeHeap {
		private Node[] nodes;
		private HashMap<Node, Integer> heapIndexMap;
		private HashMap<Node, Integer> distanceMap;
		private int size;

		public NodeHeap(int size) {
			nodes = new Node[size];
			heapIndexMap = new HashMap<>();
			distanceMap = new HashMap<>();
			this.size = 0;

		public boolean isEmpty() {
			return size == 0;

		public void addOrUpdateOrIgnore(Node node, int distance) {
			if (inHeap(node)) {
				distanceMap.put(node, Math.min(distanceMap.get(node), distance));
				insertHeapify(node, heapIndexMap.get(node));
			if (!isEntered(node)) {
				nodes[size] = node;
				heapIndexMap.put(node, size);
				distanceMap.put(node, distance);
				insertHeapify(node, size++);

		public NodeRecord pop() {
			NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
			swap(0, size - 1);
			heapIndexMap.put(nodes[size - 1], -1);
			distanceMap.remove(nodes[size - 1]);
			nodes[size - 1] = null;
			heapify(0, --size);
			return nodeRecord;

		private void insertHeapify(Node node, int index) {
			while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
				swap(index, (index - 1) / 2);
				index = (index - 1) / 2;

		private void heapify(int index, int size) {
			int left = index * 2 + 1;
			while (left < size) {
				int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
						? left + 1 : left;
				smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
				if (smallest == index) {
				swap(smallest, index);
				index = smallest;
				left = index * 2 + 1;

		private boolean isEntered(Node node) {
			return heapIndexMap.containsKey(node);

		private boolean inHeap(Node node) {
			return isEntered(node) && heapIndexMap.get(node) != -1;

		private void swap(int index1, int index2) {
			heapIndexMap.put(nodes[index1], index2);
			heapIndexMap.put(nodes[index2], index1);
			Node tmp = nodes[index1];
			nodes[index1] = nodes[index2];
			nodes[index2] = tmp;

	public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
		NodeHeap nodeHeap = new NodeHeap(size);
		nodeHeap.addOrUpdateOrIgnore(head, 0);
		HashMap<Node, Integer> result = new HashMap<>();
		while (!nodeHeap.isEmpty()) {
			NodeRecord record = nodeHeap.pop();
			Node cur = record.node;
			int distance = record.distance;
			for (Edge edge : cur.edges) {
				nodeHeap.addOrUpdateOrIgnore(, edge.weight + distance);
			result.put(cur, distance);
		return result;


Reference 1

Reference 2

Reference 3

Keywords: Algorithm Graph Theory

Added by kparker on Sat, 23 Oct 2021 06:31:45 +0300