SortedUtil — 拓扑排序工具类按父子依赖关系对列表进行稳定排序保证子节点排在父节点之后且保持同层兄弟节点的原始相对顺序。快速开始// 1. 定义你的数据结构提供 id 和 parentId 的 getterListYourEntitylist...;// 2. 调用排序ListYourEntitysortedSortedUtil.topologicalSortByParent(list,YourEntity::getId,YourEntity::getParentId);核心方法publicstaticT,IDListTtopologicalSortByParent(ListTitems,FunctionT,IDidGetter,FunctionT,IDparentGetter)参数参数类型说明itemsListT原始列表允许包含重复 id 的元素允许 nullidGetterFunctionT, ID提取元素唯一标识的函数parentGetterFunctionT, ID提取元素父标识的函数返回值排序后的新ArrayListT原始列表不会被修改。异常异常条件IllegalStateException检测到循环依赖含自环消息中会列出涉及的节点 id排序规则父在前子在后— DFS 前序遍历保证每个节点的所有子节点紧跟在它之后同层按原始顺序— 同级兄弟节点按在列表中首次出现的先后顺序排列重复 id— 相同 id 的元素在组内保持原始相对顺序多根支持— 存在多个根节点时按根节点首次出现顺序依次处理孤立父节点— 若某个节点的 parentId 不在列表中或为 null该节点视为根算法原理四步流程输入列表 │ ▼ [1. 分组] ─── 按 id 分组记录首次下标 │ ▼ [2. 建图] ─── 构建 parent → [children] 邻接表 │ ▼ [3. 找根] ─── parentId 不在列表中的节点作为根 │ ▼ [4. DFS] ─── 从根开始前序遍历三色标记检测环 │ ▼ 输出结果三色标记法环检测颜色含义说明WHITE未访问节点尚未被 DFS 遍历GRAY访问中正在遍历该节点在递归栈上若再次遇到说明有环BLACK已结束该节点及其所有子节点都已遍历完毕环检测触发条件二选一遍历中DFS 访问子节点时遇到 GRAY 节点 → 环遍历后所有根节点处理完毕仍有节点为 WHITE → 孤岛环不可达完整源码packagecom.yourpackage;importjava.util.*;importjava.util.function.Function;importjava.util.stream.Collectors;publicclassSortedUtil{/** * 拓扑排序按父子依赖关系稳定排序子节点在父节点之后 * * param items 原始列表可能有重复 id * param idGetter 提取元素 id 的函数 * param parentGetter 提取元素 parentId 的函数 * param T 元素类型 * param ID id 类型 * return 排序后的新列表 */publicstaticT,IDListTtopologicalSortByParent(ListTitems,FunctionT,IDidGetter,FunctionT,IDparentGetter){if(itemsnull||items.isEmpty())returnnewArrayList();// 1. 按 id 分组保持首次出现顺序MapID,ListTgroupByIdnewLinkedHashMap();MapID,IntegerfirstIndexnewLinkedHashMap();for(inti0;iitems.size();i){Titemitems.get(i);IDididGetter.apply(item);groupById.computeIfAbsent(id,k-newArrayList()).add(item);firstIndex.putIfAbsent(id,i);}SetIDallIdsgroupById.keySet();// 2. 构建 parent - children 邻接表MapID,SetIDchildrennewHashMap();for(IDid:allIds){children.put(id,newLinkedHashSet());}for(Titem:items){IDparentIdparentGetter.apply(item);if(parentId!nullallIds.contains(parentId)){children.get(parentId).add(idGetter.apply(item));}}// 3. 找根节点parentId 不在 allIds 中或为 nullListIDrootsallIds.stream().filter(id-{IDparentIdparentGetter.apply(groupById.get(id).get(0));returnparentIdnull||!allIds.contains(parentId);}).sorted(Comparator.comparingInt(firstIndex::get)).collect(Collectors.toList());// 4. DFS 前序遍历三色标记法检测环MapID,ColorcolornewHashMap();for(IDid:allIds){color.put(id,Color.WHITE);}ListIDsortedIdsnewArrayList();for(IDroot:roots){dfs(root,children,color,sortedIds);}// 5. 环检测仍为 WHITE 的节点形成环for(IDid:allIds){if(color.get(id)Color.WHITE){thrownewIllegalStateException(检测到循环依赖涉及节点: id);}}// 6. 按排序后的 id 展开组内元素保持原始顺序ListTresultnewArrayList(items.size());for(IDid:sortedIds){result.addAll(groupById.get(id));}returnresult;}enumColor{WHITE,GRAY,BLACK}privatestaticIDvoiddfs(IDid,MapID,SetIDchildren,MapID,Colorcolor,ListIDsortedIds){if(color.get(id)Color.GRAY){thrownewIllegalStateException(检测到循环依赖涉及节点: id);}if(color.get(id)Color.BLACK){return;}color.put(id,Color.GRAY);sortedIds.add(id);for(IDchildId:children.get(id)){dfs(childId,children,color,sortedIds);}color.put(id,Color.BLACK);}}边界情况场景行为null输入返回空列表空列表返回空列表单节点直接返回所有节点均为根保持原始顺序子节点先于父节点出现父节点仍排在前面按 id 分组后从根开始遍历父节点不在列表中该节点被当作根节点重复 id根据 id 分组组内保持原始顺序循环依赖 / 自环抛IllegalStateExceptionDAG非严格树如菱形能正确处理已经访问的节点不会重复遍历复杂度指标值时间复杂度O(V E)空间复杂度O(V)其中 V 为唯一 id 数量E 为父子关系边数。使用示例示例 1机构树排序ListOrgorgsArrays.asList(newOrg(总部,null),newOrg(研发部,总部),newOrg(前端组,研发部),newOrg(后端组,研发部),newOrg(市场部,总部));ListOrgsortedSortedUtil.topologicalSortByParent(orgs,Org::getCode,Org::getParentCode);// 结果: 总部 → 研发部 → 前端组 → 后端组 → 市场部示例 2带重复数据的非法组织ListOrgorgsArrays.asList(newOrg(总部,null),newOrg(研发部,总部),newOrg(研发部,总部),// 重复newOrg(前端组,研发部));ListOrgsortedSortedUtil.topologicalSortByParent(orgs,Org::getCode,Org::getParentCode);// 结果: 总部 → 研发部 → 研发部(重复) → 前端组