快捷導(dǎo)航

Java使用HashMap實(shí)現(xiàn)并查集

更新時(shí)間：2019年11月27日 15:07:11 作者：Jocker_coding

這篇文章主要為大家詳細(xì)介紹了Java使用HashMap實(shí)現(xiàn)并查集，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

并查集的定義：

并查集，在一些有N個(gè)元素的集合應(yīng)用問題中，我們通常是在開始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。這一類問題近幾年來反復(fù)出現(xiàn)在信息學(xué)的國際國內(nèi)賽題中，其特點(diǎn)是看似并不復(fù)雜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來描述的話，往往在空間上過大，計(jì)算機(jī)無法承受;即使在空間上勉強(qiáng)通過，運(yùn)行的時(shí)間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間(1~3秒)內(nèi)計(jì)算出試題需要的結(jié)果，只能用并查集來描述。
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。常常在使用中以森林來表示。

并查集的功能：

1、找到某個(gè)節(jié)點(diǎn)的頭節(jié)點(diǎn)
2、查詢兩個(gè)節(jié)點(diǎn)是否在同一個(gè)集合里
3、合并兩個(gè)集合

并查集的Java實(shí)現(xiàn)：

public static class Node {
 // Node可以是任意的類型 int， String等等
 }

 public static class UnionFind {
 public HashMap<Node, Node> fatherMap; // 用來存放每個(gè)節(jié)點(diǎn)的頭節(jié)點(diǎn)
 public HashMap<Node, Integer> sizeMap; // 用來保存每個(gè)集合的大小

 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); // 每個(gè)節(jié)點(diǎn)單獨(dú)成為一個(gè)集合，頭節(jié)點(diǎn)指向自己
  sizeMap.put(node, 1); // 初始化時(shí)每個(gè)集合的大小為1
  }
 }

 private Node findHead(Node node) {
  Node father = fatherMap.get(node);
  while (father != node) {
  father = findHead(father); // 遞歸向上找
  }
  fatherMap.put(node, father); // 每次遞歸時(shí)都把每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向頭節(jié)點(diǎn)
  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);
  }
  }
 }
 }

才疏學(xué)淺，如有錯(cuò)誤希望大家多多指出，一定虛心接受。

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: