遍历有向图链路（DFS算法）- 优化版
在上一节基础上，去除了节点的pre集合，只保留节点next的结合，对数据模型进行了优化，实现思想做了优化。
有向图示例：
基本思路
- 构建有向图数据模型
- 校验有向图不能出现回路，即当前节点不能出现在历史链路中
- 首先找出有向图的初始节点
- 找出有向图的初始链路
- 链路是从开始节点，按照顺序累加而形成的
- 根据节点的next集合，递归遍历初始链路，进而获取所有链路
数据模型：
- 节点数据模型：
package com.angel.ocean.domain.dsf;
import lombok.Data;
import java.util.List;
@Data
public class ChainItem {
// 该节点ID
private Integer id;
// 该节点可以到达哪些节点的ID列表
private List<Integer> next;
public ChainItem(Integer id, List<Integer> next) {
this.id = id;
this.next = next;
}
}
- 有向图链路数据模型：
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;
}
}
算法实现
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);
// 是否为终止链路，终止链路设置为true
if(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);
// 是否为终止链路，终止链路设置为true
if(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;
}
}
算法验证
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));
}
}
运行结果：
原文地址：https://blog.csdn.net/m0_37978198/article/details/142820757
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！