当前位置：首页 > article >正文

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

article 2024/10/11 9:24:59

在上一节基础上，去除了节点的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));
    }
}