朋友圈与并查集

--- ### **用朋友圈案例详解并查集** #### **场景设定** - **人物信息**： - 张三（25岁） - 李四（30岁） - 王五（28岁） - 赵六（22岁） - 孙七（35岁） - **初始状态**：每个人都是独立的朋友圈 --- ### **Java代码实现** #### **1. 定义Person类** ```java class Person { String name; int age; public Person(String name, int age) { this.name = name; this.age = age; } // 重写equals和hashCode，用于正确识别对象 @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return age == person.age && Objects.equals(name, person.name); } @Override public int hashCode() { return Objects.hash(name, age); } @Override public String toString() { return name + "(" + age + ")"; } } ``` #### **2. 并查集核心实现** ```java import java.util.HashMap; import java.util.Map; class UnionFind { private Map<Person, Person> parent = new HashMap<>(); // 记录父节点 private Map<Person, Integer> rank = new HashMap<>(); // 记录树高度 // 初始化并查集 public UnionFind(Person[] people) { for (Person p : people) { parent.put(p, p); // 初始父节点指向自己 rank.put(p, 1); // 初始树高度为1 } } // 查找根节点（带路径压缩） public Person find(Person x) { if (!parent.containsKey(x)) { throw new IllegalArgumentException("人物不存在"); } // 如果当前节点不是根节点 if (!parent.get(x).equals(x)) { // 递归找到根节点，并将路径上的节点直接指向根 parent.put(x, find(parent.get(x))); } return parent.get(x); } // 合并两个朋友圈 public void union(Person a, Person b) { Person rootA = find(a); Person rootB = find(b); if (rootA.equals(rootB)) return; // 已在同一朋友圈 // 按秩合并（小树合并到大树） if (rank.get(rootA) < rank.get(rootB)) { parent.put(rootA, rootB); } else if (rank.get(rootA) > rank.get(rootB)) { parent.put(rootB, rootA); } else { parent.put(rootB, rootA); rank.put(rootA, rank.get(rootA) + 1); // 树高度+1 } } // 判断是否是同一朋友圈 public boolean isConnected(Person a, Person b) { return find(a).equals(find(b)); } } ``` --- ### **3. 完整测试案例** ```java public class Main { public static void main(String[] args) { // 创建所有人物 Person zs = new Person("张三", 25); Person ls = new Person("李四", 30); Person ww = new Person("王五", 28); Person zl = new Person("赵六", 22); Person sq = new Person("孙七", 35); Person[] people = {zs, ls, ww, zl, sq}; UnionFind uf = new UnionFind(people); // 初始状态：5个独立朋友圈 System.out.println("初始朋友圈数量：" + countGroups(uf, people)); // 操作1：张三和李四成为朋友 uf.union(zs, ls); System.out.println("张三和李四是朋友？" + uf.isConnected(zs, ls)); // true // 操作2：李四和王五成为朋友 uf.union(ls, ww); System.out.println("张三和王五是朋友？" + uf.isConnected(zs, ww)); // true // 合并结果：张三-李四-王五为同一朋友圈 System.out.println("当前朋友圈数量：" + countGroups(uf, people)); // 3 // 操作3：赵六和孙七成为朋友 uf.union(zl, sq); System.out.println("孙七和赵六是朋友？" + uf.isConnected(sq, zl)); // true // 最终结果：总共有2个朋友圈 System.out.println("最终朋友圈数量：" + countGroups(uf, people)); // 2 } // 统计独立朋友圈数量 private static int countGroups(UnionFind uf, Person[] people) { Set<Person> roots = new HashSet<>(); for (Person p : people) { roots.add(uf.find(p)); } return roots.size(); } } ``` --- ### **关键代码解释** #### **1. 数据结构设计** - **`parent`哈希表**：记录每个人的“上级朋友” - 初始时：`张三 → 张三`，`李四 → 李四` - 合并后：`张三 → 李四`（假设李四是根） - **`rank`哈希表**：记录每个朋友圈的“高度” - 合并时保持树的平衡，防止退化成链表 #### **2. 路径压缩过程** ```java public Person find(Person x) { // 如果当前节点不是根节点 if (!parent.get(x).equals(x)) { // 递归找到根节点，并将路径上的节点直接指向根 parent.put(x, find(parent.get(x))); } return parent.get(x); } ``` - **示例**：查找张三的根节点 - 初始路径：张三 → 李四 → 李四（根） - 压缩后：张三直接指向李四 #### **3. 按秩合并逻辑** ```java if (rank.get(rootA) < rank.get(rootB)) { parent.put(rootA, rootB); // 把矮树挂到高树上 } else { parent.put(rootB, rootA); // 反之 if 高度相等，合并后树高+1 } ``` - **目的**：保持树的平衡，保证查找效率 --- ### **执行结果** ``` 初始朋友圈数量：5 张三和李四是朋友？true 张三和王五是朋友？true 当前朋友圈数量：3 孙七和赵六是朋友？true 最终朋友圈数量：2 ``` --- ### **实际应用扩展** 1. **动态新增成员**：当有新成员加入时，调用`parent.put(newPerson, newPerson)`初始化 2. **删除成员**：需要重构数据结构（通常并查集不支持高效删除） 3. **统计每个圈子人数**：添加一个`size`哈希表，合并时更新大小 --- 时间复杂度 未优化：最坏情况O(N) 路径压缩 + 按秩合并：均摊时间接近O(1) （严格来说是反阿克曼函数，增长极其缓慢） 实际应用场景 1. 社交网络：判断两个人是否间接好友 2. 电路连接：判断两个触点是否连通 3. 游戏网格：判断两个格子是否属于同一区域 4. 最小生成树：Kruskal算法中的边筛选