Java拓扑排序-解决树排序问题

SortedUtil — 拓扑排序工具类

按父子依赖关系对列表进行稳定排序，保证子节点排在父节点之后，且保持同层兄弟节点的原始相对顺序。

快速开始

// 1. 定义你的数据结构，提供 id 和 parentId 的 getterList<YourEntity>list=...;// 2. 调用排序List<YourEntity>sorted=SortedUtil.topologicalSortByParent(list,YourEntity::getId,YourEntity::getParentId);

核心方法

publicstatic<T,ID>List<T>topologicalSortByParent(List<T>items,Function<T,ID>idGetter,Function<T,ID>parentGetter)

参数

返回值

排序后的新ArrayList<T>，原始列表不会被修改。

异常

排序规则

1. 父在前，子在后— DFS 前序遍历保证每个节点的所有子节点紧跟在它之后
2. 同层按原始顺序— 同级兄弟节点按在列表中首次出现的先后顺序排列
3. 重复 id— 相同 id 的元素在组内保持原始相对顺序
4. 多根支持— 存在多个根节点时，按根节点首次出现顺序依次处理
5. 孤立父节点— 若某个节点的 parentId 不在列表中或为 null，该节点视为根

算法原理

四步流程

输入列表 │ ▼ [1. 分组] ─── 按 id 分组，记录首次下标 │ ▼ [2. 建图] ─── 构建 parent → [children] 邻接表 │ ▼ [3. 找根] ─── parentId 不在列表中的节点作为根 │ ▼ [4. DFS] ─── 从根开始前序遍历，三色标记检测环 │ ▼ 输出结果

三色标记法环检测

环检测触发条件（二选一）：

• 遍历中：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 排序后的新列表 */publicstatic<T,ID>List<T>topologicalSortByParent(List<T>items,Function<T,ID>idGetter,Function<T,ID>parentGetter){if(items==null||items.isEmpty())returnnewArrayList<>();// 1. 按 id 分组（保持首次出现顺序）Map<ID,List<T>>groupById=newLinkedHashMap<>();Map<ID,Integer>firstIndex=newLinkedHashMap<>();for(inti=0;i<items.size();i++){Titem=items.get(i);IDid=idGetter.apply(item);groupById.computeIfAbsent(id,k->newArrayList<>()).add(item);firstIndex.putIfAbsent(id,i);}Set<ID>allIds=groupById.keySet();// 2. 构建 parent -> children 邻接表Map<ID,Set<ID>>children=newHashMap<>();for(IDid:allIds){children.put(id,newLinkedHashSet<>());}for(Titem:items){IDparentId=parentGetter.apply(item);if(parentId!=null&&allIds.contains(parentId)){children.get(parentId).add(idGetter.apply(item));}}// 3. 找根节点（parentId 不在 allIds 中或为 null）List<ID>roots=allIds.stream().filter(id->{IDparentId=parentGetter.apply(groupById.get(id).get(0));returnparentId==null||!allIds.contains(parentId);}).sorted(Comparator.comparingInt(firstIndex::get)).collect(Collectors.toList());// 4. DFS 前序遍历（三色标记法检测环）Map<ID,Color>color=newHashMap<>();for(IDid:allIds){color.put(id,Color.WHITE);}List<ID>sortedIds=newArrayList<>();for(IDroot:roots){dfs(root,children,color,sortedIds);}// 5. 环检测：仍为 WHITE 的节点形成环for(IDid:allIds){if(color.get(id)==Color.WHITE){thrownewIllegalStateException("检测到循环依赖，涉及节点: "+id);}}// 6. 按排序后的 id 展开组内元素（保持原始顺序）List<T>result=newArrayList<>(items.size());for(IDid:sortedIds){result.addAll(groupById.get(id));}returnresult;}enumColor{WHITE,GRAY,BLACK}privatestatic<ID>voiddfs(IDid,Map<ID,Set<ID>>children,Map<ID,Color>color,List<ID>sortedIds){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);}}

边界情况

复杂度

其中 V 为唯一 id 数量，E 为父子关系边数。

使用示例

示例 1：机构树排序

List<Org>orgs=Arrays.asList(newOrg("总部",null),newOrg("研发部","总部"),newOrg("前端组","研发部"),newOrg("后端组","研发部"),newOrg("市场部","总部"));List<Org>sorted=SortedUtil.topologicalSortByParent(orgs,Org::getCode,Org::getParentCode);// 结果: 总部 → 研发部 → 前端组 → 后端组 → 市场部

示例 2：带重复数据的非法组织

List<Org>orgs=Arrays.asList(newOrg("总部",null),newOrg("研发部","总部"),newOrg("研发部","总部"),// 重复newOrg("前端组","研发部"));List<Org>sorted=SortedUtil.topologicalSortByParent(orgs,Org::getCode,Org::getParentCode);// 结果: 总部 → 研发部 → 研发部(重复) → 前端组