Java中怎么利用HashMap實現并查集

這期內容當中小編將會給大家帶來有關Java中怎么利用HashMap實現并查集，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

并查集的定義：

并查集，在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然后按一定順序將屬于同一組的元素所在的集合合并，其間要反復查找一個元素在哪個集合中。這一類問題近幾年來反復出現在信息學的國際國內賽題中，其特點是看似并不復雜，但數據量極大，若用正常的數據結構來描述的話，往往在空間上過大，計算機無法承受;即使在空間上勉強通過，運行的時間復雜度也極高，根本就不可能在比賽規定的運行時間(1~3秒)內計算出試題需要的結果，只能用并查集來描述。并查集是一種樹型的數據結構，用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。常常在使用中以森林來表示。

并查集的功能：

1、找到某個節點的頭節點2、查詢兩個節點是否在同一個集合里3、合并兩個集合

并查集的Java實現：

public static class Node { // Node可以是任意的類型 int， String等等 } public static class UnionFind { public HashMap<Node, Node> fatherMap; // 用來存放每個節點的頭節點 public HashMap<Node, Integer> sizeMap; // 用來保存每個集合的大小 public UnionFind() {  fatherMap = new HashMap<Node, Node>();  sizeMap = new HashMap<Node, Integer>(); } public void makeSet(List<Node> nodes) {  fatherMap.clear();  sizeMap.clear();  for (Node node : nodes) {  fatherMap.put(node, node); // 每個節點單獨成為一個集合，頭節點指向自己  sizeMap.put(node, 1); // 初始化時每個集合的大小為1  } } private Node findHead(Node node) {  Node father = fatherMap.get(node);  while (father != node) {  father = findHead(father); // 遞歸向上找  }  fatherMap.put(node, father); // 每次遞歸時都把每個節點的父節點直接指向頭節點  return father; } public boolean isSameSet(Node aNode, Node bNode) {  return findHead(aNode) == findHead(bNode); } public void union(Node aNode, Node bNode) {  if (aNode == null || bNode == null) {  return;  }  Node aHead = findHead(aNode);  Node bHead = findHead(bNode);  if (aHead != bHead) {  int aSize = sizeMap.get(aHead);  int bSize = sizeMap.get(bHead);  if (aSize <= bSize) {   fatherMap.put(aHead, bHead);   sizeMap.put(bHead, aSize + bSize);  } else {   fatherMap.put(bHead, aHead);   sizeMap.put(aHead, aSize + bSize);  }  } } }

上述就是小編為大家分享的Java中怎么利用HashMap實現并查集了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。