【Java实现拓扑排序（从上游到下游） 功能】

问题记录

unitcd unitnm fcd ocd WCG10_2_6 南乐 -1 -1 WCG11_2_7 刘寨 -1 -1 WEA31_9_6 棉集 -1 -1 WEA31_9_8 大张庄 -1 -1 WEA36_9_10 黄口集闸下 -1 -1 WEA36_9_9 马桥 -1 -1 WEA37_9_11 李黑楼闸 -1 -1 WEA37_9_12 蒋庄 -1 -1 WEB37_9_1 南庄站 -1 -1 WCF11_1_18 占城 WCF11_1_r13 WCF11_1_12 WCF11_1_r13 石门水库(辉县)-1 WCF11_1_18 WCF11_1_22 南云门 -1 WCF11_1_12 WCF11_1_6 狮子营 -1 WCF11_1_12 WCF11_1_r2 马鞍石水库 -1 WCF11_1_12 WCF11_1_r37 宝泉水库 -1 WCF11_1_12 WCF11_1_r1 群英水库 -1 WCF11_1_4 WCF11_1_3 丰顺店 -1 WCF11_1_4 WCF11_1_4 修武 WCF11_1_r1;WCF11_1_3 WCF11_1_12 WCF11_1_17 花木 -1 WCF11_1_12 WCF11_1_12 合河共 WCF11_1_r2;WCF11_1_22;WCF11_1_4;WCF11_1_r37;WCF11_1_17;WCF11_1_18;WCF11_1_6 WCF11_1_21 WCF11_1_r14 弓上水库 -1 WCF11_1_r42 WCF11_1_r41 石门水库(安阳)-1 WCF11_1_r42 WCF11_1_r61 陈家院水库 -1 WCF11_1_r60 WCF11_1_r60 三郊口水库 WCF11_1_r61 WCF11_1_r42 WCF11_1_r42 盘石头水库 WCF11_1_r60;WCF11_1_r14;WCF11_1_r41 WCF11_1_32 WCF11_1_r54 八里营 -1 WCF11_1_r55 WCF11_1_r55 汲县 WCF11_1_r54 WCF11_1_r56 WCF11_1_r56 皇甫 WCF11_1_r55 WCF11_1_r57 WCF11_1_19 夺丰水库 -1 WCF11_1_r58 WCF11_1_21 黄土岗 WCF11_1_12 WCF11_1_r59 WCF11_1_38 正面水库 -1 WCF11_1_r39 WCF11_1_r39 狮豹头水库 WCF11_1_38 WCF11_1_40 WCF11_1_40 塔岗水库 WCF11_1_r39 WCF11_1_r59 WCF11_1_r59 良相坡 WCF11_1_21;WCF11_1_40 WCF11_1_r58 WCF11_1_32 新村 WCF11_1_r42 WCF11_1_r58 WCF11_1_r58 刘庄 WCF11_1_19;WCF11_1_r59;WCF11_1_32 WCF11_1_r57 WCF11_1_r57 淇门 WCF11_1_r56;WCF11_1_r58 WCF11_1_r44 WCF11_1_r44 牛寨 WCF11_1_r57 WCF11_1_r46 WCF11_1_r43 牛庄 -1 WCF11_1_r45 WCF11_1_r45 道口(上)WCF11_1_r43 WCF11_1_r46 WCF11_1_r46 浚县 WCF11_1_r44;WCF11_1_r45 WCF11_1_r49 WCF11_1_r47 白寺坡 -1 WCF11_1_r48 WCF11_1_r48 屯子 WCF11_1_r47 WCF11_1_r49 WCF11_1_r49 五陵 WCF11_1_r48;WCF11_1_r46 WCF11_1_r50 WCF11_1_r29 汤河水库 -1 WCF11_1_r50 WCF11_1_r30 琵琶寺水库 -1 WCF11_1_r50 WCF11_1_34 梨园 -1 WCF11_1_r50 WCF11_1_r50 西元村 WCF11_1_r30;WCF11_1_r29;WCF11_1_34;WCF11_1_r49 WCF11_1_r52 WCF11_1_r24 双泉水库 -1 WCF11_1_r27 WCF11_1_15 横水 -1 WCF11_1_r9 WCF11_1_r9 小南海水库 WCF11_1_15 WCF11_1_r23 WCF11_1_r23 彰武水库 WCF11_1_r9 WCF11_1_r27 WCF11_1_r27 安阳 WCF11_1_r23;WCF11_1_r24 WCF11_1_r52 WCF11_1_r51 内黄 -1 WCF11_1_r53 WCF11_1_r52 楚旺 WCF11_1_r27;WCF11_1_r50 WCF11_1_r53 WCF11_1_r53 元村集 WCF11_1_r52;WCF11_1_r51 -1

以上示例数据，按照从上游到下游的顺序，一般会将上下游都是-1(即独立的，没有上下游的数据)的排在最前面。
请将以上数据进行按照从上游到下游的排序，注意上游fcd是按照分号进行分割的，可能存在多个上游，并生成order_num字段，编码从1开始递增。java代码实现，类名为TopologySorter。
数据存储在表中：
String inputFilePath = “C:\Users\Administrator\Desktop\拓扑排序输入.xlsx”;
String outputFilePath = “C:\Users\Administrator\Desktop\拓扑排序输入_排序后.xlsx”;

一、问题分析

为了实现上面描述的 拓扑排序（从上游到下游） 功能，我们需要对 Excel 中的河道数据进行 有向无环图（DAG）拓扑排序。规则如下：
1.每一行代表一个节点（unitcd）；
2.fcd 字段表示该节点的上游节点列表（多个用分号分隔，-1 表示无上游）；
3.ocd 字段表示该节点的下游节点（单个，-1 表示无下游）；
4.我们的目标是：从没有上游的节点开始（即 fcd = -1），逐层向下排序；
5.生成 order_num 字段，从 1 开始递增。

二、实现思路

1.读取 Excel 数据 到内存对象；
2.构建图结构：
每个节点记录其所有上游节点（in-degree）；
构建 节点 → 下游节点列表 的邻接表（用于 BFS 遍历）；
3.使用 Kahn 算法进行拓扑排序：
入度为 0 的节点（即 fcd = “-1” 或所有上游都不存在/未定义）入队；
逐层处理，减少下游节点的入度；
4.处理孤立节点（上下游均为 -1）放在最前面；
5.写回 Excel，新增 order_num 列。

三、Java 代码实现

（类名：TopologySorter）
依赖：Apache POI（同上）

importorg.apache.poi.ss.usermodel.*;importorg.apache.poi.xssf.usermodel.XSSFWorkbook;importjava.io.FileInputStream;importjava.io.FileOutputStream;importjava.io.IOException;importjava.util.*;publicclassTopologySorter{publicstaticvoidmain(String[]args){StringinputFilePath="C:\\Users\\Administrator\\Desktop\\拓扑排序输入.xlsx";StringoutputFilePath="C:\\Users\\Administrator\\Desktop\\拓扑排序输入_排序后.xlsx";try{sortAndWrite(inputFilePath,outputFilePath);}catch(IOExceptione){e.printStackTrace();}}privatestaticvoidsortAndWrite(StringinputPath,StringoutputPath)throwsIOException{// 1. 读取数据List<Node>nodes=readExcel(inputPath);Map<String,Node>nodeMap=newHashMap<>();for(Nodenode:nodes){nodeMap.put(node.unitcd,node);}// 2. 构建图：计算每个节点的入度（in-degree）Map<String,Integer>inDegree=newHashMap<>();Map<String,List<String>>adjList=newHashMap<>();// node -> downstream list// 初始化for(Nodenode:nodes){inDegree.put(node.unitcd,0);adjList.put(node.unitcd,newArrayList<>());}// 遍历每个节点，解析 fcd（上游），建立反向边：上游 → 当前节点（即当前节点的入度来源）for(Nodenode:nodes){if("-1".equals(node.fcd)){// 无上游，入度为0continue;}String[]upstreams=node.fcd.split(";");for(Stringup:upstreams){if(nodeMap.containsKey(up)){// up 是有效上游节点adjList.computeIfAbsent(up,k->newArrayList<>()).add(node.unitcd);inDegree.merge(node.unitcd,1,Integer::sum);}// 如果 upstream 不存在于本表中，忽略（视为外部源）}}// 3. Kahn 拓扑排序Queue<String>queue=newLinkedList<>();// 所有入度为0的节点入队（包括 fcd=-1 且无其他上游的）for(Stringunitcd:inDegree.keySet()){if(inDegree.get(unitcd)==0){queue.offer(unitcd);}}List<String>sortedOrder=newArrayList<>();while(!queue.isEmpty()){Stringcurrent=queue.poll();sortedOrder.add(current);// 遍历当前节点的所有下游for(Stringdownstream:adjList.getOrDefault(current,Collections.emptyList())){inDegree.put(downstream,inDegree.get(downstream)-1);if(inDegree.get(downstream)==0){queue.offer(downstream);}}}// 4. 处理可能的环（本题假设无环，可忽略）if(sortedOrder.size()!=nodes.size()){System.err.println("警告：存在环或孤立节点未完全处理，排序节点数: "+sortedOrder.size()+", 总数: "+nodes.size());}// 5. 为每个节点分配 order_numMap<String,Integer>orderMap=newHashMap<>();for(inti=0;i<sortedOrder.size();i++){orderMap.put(sortedOrder.get(i),i+1);}// 对于不在 sortedOrder 中的节点（理论上不应有），补到最后for(Nodenode:nodes){if(!orderMap.containsKey(node.unitcd)){orderMap.put(node.unitcd,orderMap.size()+1);}}// 6. 写回 ExcelwriteExcelWithOrder(inputPath,outputPath,orderMap);}privatestaticList<Node>readExcel(Stringpath)throwsIOException{FileInputStreamfis=newFileInputStream(path);Workbookworkbook=newXSSFWorkbook(fis);Sheetsheet=workbook.getSheetAt(0);List<Node>nodes=newArrayList<>();booleanfirstRow=true;for(Rowrow:sheet){if(firstRow){firstRow=false;continue;// 跳过标题行（如果存在）}CellunitcdCell=row.getCell(0);CellunitnmCell=row.getCell(1);CellfcdCell=row.getCell(2);CellocdCell=row.getCell(3);Stringunitcd=getCellValueAsString(unitcdCell);Stringunitnm=getCellValueAsString(unitnmCell);Stringfcd=getCellValueAsString(fcdCell);Stringocd=getCellValueAsString(ocdCell);if(unitcd==null||unitcd.trim().isEmpty())continue;nodes.add(newNode(unitcd,unitnm,fcd,ocd));}workbook.close();fis.close();returnnodes;}privatestaticvoidwriteExcelWithOrder(StringinputPath,StringoutputPath,Map<String,Integer>orderMap)throwsIOException{FileInputStreamfis=newFileInputStream(inputPath);Workbookworkbook=newXSSFWorkbook(fis);Sheetsheet=workbook.getSheetAt(0);// 在第一行添加 order_num 列头（假设原表有标题行）RowheaderRow=sheet.getRow(0);if(headerRow==null){headerRow=sheet.createRow(0);}intorderColIndex=4;// 原有4列（0~3），新列在第5列（索引4）headerRow.createCell(orderColIndex).setCellValue("order_num");// 从第二行开始写 order_numfor(inti=1;i<=sheet.getLastRowNum();i++){Rowrow=sheet.getRow(i);if(row==null)continue;CellunitcdCell=row.getCell(0);Stringunitcd=getCellValueAsString(unitcdCell);if(unitcd==null)continue;Integerorder=orderMap.get(unitcd);if(order==null)order=999999;// fallbackrow.createCell(orderColIndex).setCellValue(order);}// 写出文件FileOutputStreamfos=newFileOutputStream(outputPath);workbook.write(fos);fos.close();workbook.close();fis.close();}privatestaticStringgetCellValueAsString(Cellcell){if(cell==null)returnnull;switch(cell.getCellType()){caseSTRING:returncell.getStringCellValue().trim();caseNUMERIC:// 尝试判断是否为整数（避免 1.0 变成 "1.0"）doubleval=cell.getNumericCellValue();if(val==Math.floor(val)&&!Double.isInfinite(val)){returnString.valueOf((long)val);}else{returnString.valueOf(val);}caseBLANK:return"";default:returncell.toString();}}// 内部数据类staticclassNode{Stringunitcd;Stringunitnm;Stringfcd;Stringocd;Node(Stringunitcd,Stringunitnm,Stringfcd,Stringocd){this.unitcd=unitcd;this.unitnm=unitnm;this.fcd=fcd;this.ocd=ocd;}}}

四、输出说明

输入 Excel 必须包含列：unitcd, unitnm, fcd, ocd（顺序一致即可）；
程序会自动跳过第一行（假设是标题）；
输出文件在原表基础上新增一列 order_num，值从 1 开始；
上游无依赖的节点（如 fcd = -1）会排在最前面；
支持多上游（fcd 含分号）；
自动处理图结构，确保拓扑顺序正确。