遍历有向图链路（DFS算法）- 优化版

在上一节基础上，去除了节点的pre集合，只保留节点next的结合，对数据模型进行了优化，实现思想做了优化。

有向图示例：

在这里插入图片描述

基本思路

构建有向图数据模型
校验有向图不能出现回路，即当前节点不能出现在历史链路中
首先找出有向图的初始节点
找出有向图的初始链路
链路是从开始节点，按照顺序累加而形成的
根据节点的next集合，递归遍历初始链路，进而获取所有链路

数据模型：

节点数据模型：

java">package com.angel.ocean.domain.dsf;import lombok.Data;
import java.util.List;@Data
public class ChainItem {// 该节点IDprivate Integer id;// 该节点可以到达哪些节点的ID列表private List<Integer> next;public ChainItem(Integer id, List<Integer> next) {this.id = id;this.next = next;}
}

有向图链路数据模型：

java">package com.angel.ocean.domain.dsf;import java.util.List;public class Chain {// ID链路private List<Integer> chainItemIds;// 是否结束private boolean end = false;public List<Integer> getChainItemIds() {return chainItemIds;}public void setChainItemIds(List<Integer> chainItemIds) {this.chainItemIds = chainItemIds;}public boolean isEnd() {return end;}public void setEnd(boolean end) {this.end = end;}
}

算法实现

java">package com.angel.ocean.utils;import cn.hutool.core.collection.CollUtil;
import com.alibaba.fastjson2.JSON;
import com.angel.ocean.domain.dsf.Chain;
import com.angel.ocean.domain.dsf.ChainItem;
import lombok.extern.slf4j.Slf4j;
import java.util.*;@Slf4j
public class ChainHandlerUtil {/*** 获取所有链路* @param chainItems* @return*/public static List<Chain> getAllChain(List<ChainItem> chainItems) {if (CollUtil.isEmpty(chainItems)) {log.info("ChainHandlerUtil.getAllChain(), chainItems is null");throw new RuntimeException("参数为空");}// 链路数据List<Chain> list = new ArrayList<>();// 1. 获取初始节点List<ChainItem> firstItemList = getFirstItemList(chainItems);if(CollUtil.isEmpty(firstItemList)) {throw new RuntimeException("参数校验失败，不存在初始节点");}// 2. 获取初始链路for (ChainItem chainItem : firstItemList) {List<Integer> chainItemIds = new ArrayList<>();chainItemIds.add(chainItem.getId());Chain chain = new Chain();chain.setChainItemIds(chainItemIds);// 是否为终止链路，终止链路设置为trueif(CollUtil.isEmpty(chainItem.getNext())) {chain.setEnd(true);}list.add(chain);}// 3. 根据初始链路递归出所有链路数据// 是否所有链路都结束了boolean allChainIsEnd = false;while (!allChainIsEnd) {list = chainDataHandler(list, chainItems);allChainIsEnd = true;for (Chain chain : list) {if(!chain.isEnd()) {allChainIsEnd = false;}}}return list;}/*** 获取初始节点列表，不存在于next中的节点就是初始节点* @param chainItems* @return*/private static List<ChainItem> getFirstItemList(List<ChainItem> chainItems) {// 非初始节点集合Set<Integer> nextItemIds = new HashSet<>();for (ChainItem chainItem : chainItems) {if(CollUtil.isNotEmpty(chainItem.getNext())) {nextItemIds.addAll(chainItem.getNext());}}// 初始节点集合List<ChainItem> firstItemIds = new ArrayList<>();for (ChainItem chainItem : chainItems) {if(!nextItemIds.contains(chainItem.getId())) {firstItemIds.add(chainItem);}}return firstItemIds;}/*** 链路数据迭代* @param list* @param chainItems* @return*/private static List<Chain> chainDataHandler(List<Chain> list, List<ChainItem> chainItems) {List<Chain> newList = new ArrayList<>();for (Chain chain: list) {if(chain.isEnd()) {newList.add(chain);continue;}List<Integer> chainItemIds = chain.getChainItemIds();int chainEndItemId = chainItemIds.get(chainItemIds.size() - 1);ChainItem chainEndItem = getChainItemById(chainEndItemId, chainItems);for (Integer id : chainEndItem.getNext()) {// 是否为回路校验if(chainItemIds.contains(id)) {throw new RuntimeException("参数校验失败，链路出现回路");}Chain newChain = new Chain();List<Integer> newChainItemIds = new ArrayList<>();newChainItemIds.addAll(chainItemIds);newChainItemIds.add(id);newChain.setChainItemIds(newChainItemIds);ChainItem nextItem = getChainItemById(id, chainItems);// 是否为终止链路，终止链路设置为trueif(CollUtil.isEmpty(nextItem.getNext())) {newChain.setEnd(true);}newList.add(newChain);}}return newList;}/*** 获取ItemById** @param id* @param chainItems* @return*/private static ChainItem getChainItemById(Integer id, List<ChainItem> chainItems) {for (ChainItem chainItem : chainItems) {if (chainItem.getId().equals(id)) {return chainItem;}}return null;}
}

算法验证

java">public static void main(String[] args) {// 上述有向图可以转换成如下数据List<ChainItem> chainItems = new ArrayList<>();chainItems.add(new ChainItem(1, Arrays.asList(2, 6)));chainItems.add(new ChainItem(2, Arrays.asList(3, 7)));chainItems.add(new ChainItem(3, Arrays.asList(4, 12)));chainItems.add(new ChainItem(4, Arrays.asList(5, 7)));chainItems.add(new ChainItem(5,  null));chainItems.add(new ChainItem(6, Arrays.asList(2)));chainItems.add(new ChainItem(7, Arrays.asList(8)));chainItems.add(new ChainItem(8, Arrays.asList(5)));chainItems.add(new ChainItem(9, Arrays.asList(10, 13)));chainItems.add(new ChainItem(10, Arrays.asList(3)));chainItems.add(new ChainItem(11, Arrays.asList(4)));chainItems.add(new ChainItem(12, Arrays.asList(5, 11)));chainItems.add(new ChainItem(13, Arrays.asList(15, 17)));chainItems.add(new ChainItem(15, Arrays.asList(16)));chainItems.add(new ChainItem(16, Arrays.asList(17)));chainItems.add(new ChainItem(17, null));chainItems.add(new ChainItem(18, null));chainItems.add(new ChainItem(19, Arrays.asList(20)));chainItems.add(new ChainItem(20, null));List<Chain> chains = getAllChain(chainItems);for (Chain chain : chains) {log.info("{}", JSON.toJSONString(chain));}
}