持续创造,加快生长!这是我参加「日新方案 10 月更文应战」的第28天,点击查看活动概况

前语

最近公司的项目上有个需求,还挺有分享价值的,这边做个记载。需求大致如下,下面的一个流程图,点击条件线上挑选的内容,有必要是前面装备过的节点,假如不是,需求在保存的时分做强校验提示。

计算图中两个顶点的所有路径,你会吗

需求其实很明确,抽象出来便是获取图中两个极点之间一切可达途径的极点调集,咱们能够考虑下,该如何完成?这里边涉及到了数据结构中图相关常识,而数据结构算法也是本事最大的弱项,还是废了我一番工夫。

抽象数据模型

实际上,看到这个需求就很简单想到咱们的有向图,那么在java中该用怎么样的数据结构表明有向图呢?在恶补了一番图相关的常识今后,终究确定用”邻接表”的方法完成。邻接表是图的一种最主要存储结构,用来描述图上的每一个点。

咱们假定下面的一个有向图:

计算图中两个顶点的所有路径,你会吗
那么能够抽象出下面的数据结构:

计算图中两个顶点的所有路径,你会吗

不知道咱们发现规则了吗,每个极点相关了它相关的其他极点,比如A经过边相关了B,C,D, 能够理解为A有3条边,他们的方针极点是B,C,D,那如何用java表明呢?

代码完成数据模型

  1. 极点类Vertex
/**
 * 极点
 */
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Vertex {
    /**
     * 极点id
     */
    private String id;
    /**
     * 极点的称号
     */
    private String name;
    /**
     * 极点发散出去的边信息
     */
    private List<Edge> edges = new ArrayList<>();
}
  • 成员变量edges表明极点相关的一切的边
  1. 极点相关的边类Edge
/**
 * 边
 */
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Edge {
    /**
     * 边的方针id
     */
    private String targetVertexId;
    /**
     * 边的id
     */
    private String id;
    /**
     * 边的称号
     */
    private String name;
}
  • 成员变量targetVertexId用来存储边的方针极点id
  1. 创立有向图DirectedDiagraph
/**
 * 有向图
 *
 * @author alvin
 * @date 2022/10/26
 * @since 1.0
 **/
@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {
    /**
     * 有向图的的极点信息
     */
    private Map<String, Vertex> vertextMap = new HashMap<>();
    /**
     * 边的数量
     */
    private int edgeNum;
    /**
     * 增加极点信息
     *
     * @param vertexId   极点的id
     * @param vertexName 极点的称号
     */
    public void addVertex(String vertexId, String vertexName) {
        if (StrUtil.isEmpty(vertexId)) {
            throw new RuntimeException("极点id不能为空");
        }
        Vertex node = new Vertex().setId(vertexId).setName(vertexName);
        // 增加到有向图中
        vertextMap.put(vertexId, node);
    }
    /**
     * 增加边信息
     *
     * @param fromVertexId   边的开始节点
     * @param targetVertexId 边的方针节点
     * @param edgeId         边id
     * @param edgeName       边称号
     */
    public void addEdge(String fromVertexId, String targetVertexId, String edgeId, String edgeName) {
        if (StrUtil.isEmpty(fromVertexId) || StrUtil.isEmpty(targetVertexId)) {
            throw new RuntimeException("边的开始极点或许方针极点不能为空");
        }
        Edge edge = new Edge().setTargetVertexId(targetVertexId).setId(edgeId).setName(edgeName);
        // 获取极点
        Vertex fromVertex = vertextMap.get(fromVertexId);
        // 增加到边中
        fromVertex.getEdges().add(edge);
        // 边的数量+1
        edgeNum++;
    }
    /**
     * 增加边信息
     * @param fromVertexId   边的开始节点
     * @param targetVertexId 边的方针节点
     */
    public void addEdge(String fromVertexId, String targetVertexId) {
        this.addEdge(fromVertexId, targetVertexId, null, null);
    }
    /**
     * 获取图中边的数量
     */
    public int getEdgeNum() {
        return edgeNum;
    }
}
  • 成员变量vertextMap存储图中的极点信息
  • addVertex() 方法用来增加极点数据
  • addEdge()方法用来增加边数据

核算两个极点之间途径算法

回到前语的需求,目前图的数据模型现已创立好了,现在需求完成核算两个极点之间可达途径的一切极点调集,直接上代码。

因为用到的参数比较多,这边封装了一个算法的类CalcTwoVertexPathlgorithm

  • calcPaths()方法便是算法的核心入口
  • 成员变量allPathList中存放了一切可达的途径列表。
  • printAllPaths()方法打印一切的途径。
  • getAllVertexs()回来一切可达的极点调集。
/**
* 核算两个极点之间途径的算法
*/
@Slf4j(topic = "a.CalcTwoVertexPathlgorithm")
class CalcTwoVertexPathlgorithm {
/**
 * 开始极点
 */
private String fromVertexId;
/**
 * 查询的方针极点
 */
private String toVertextId;
/**
 * 当时的图
 */
private DirectedDiagraph directedDiagraph;
/**
 * 一切的途径
 */
private final List<List<String>> allPathList = new ArrayList<>();
public CalcTwoVertexPathlgorithm(DirectedDiagraph directedDiagraph, String fromVertexId, String toVertextId) {
    this.fromVertexId = fromVertexId;
    this.toVertextId = toVertextId;
    this.directedDiagraph = directedDiagraph;
}
/**
 * 打印一切的途径
 */
public void printAllPaths() {
    log.info("the path betweent {} and {}:", fromVertexId, toVertextId);
    allPathList.forEach(item -> {
        log.info("{}", item);
    });
}
/**
 * 获取两点之间一切或许的极点数据
 * @return
 */
public Set<String> getAllVertexs() {
    return allPathList.stream().flatMap(Collection::stream).collect(Collectors.toSet());
}
public void calcPaths() {
    // 先整理之前调用留下的数据
    allPathList.clear();
    DirectedDiagraph.Vertex fromNode = directedDiagraph.getVertextMap().get(fromVertexId);
    DirectedDiagraph.Vertex toNode = directedDiagraph.getVertextMap().get(toVertextId);
    // 无法找到边
    if (fromNode == null || toNode == null) {
        throw new RuntimeException("极点id不存在");
    }
    // 假如其实节点等于方针节点,则也作为一个边
    if (fromNode == toNode) {
        List<String> paths = new ArrayList<>();
        paths.add(fromVertexId);
        allPathList.add(paths);
        return;
    }
    // 递归调用
    coreRecGetAllPaths(fromNode, toNode, new ArrayDeque<>());
}
private void coreRecGetAllPaths(DirectedDiagraph.Vertex fromVertex, DirectedDiagraph.Vertex toVertex, Deque<String> nowPaths) {
    // 查看是否存在环,越过
    if (nowPaths.contains(fromVertex.getId())) {
        System.out.println("存在环");
        // 出栈
        nowPaths.pop();
        return;
    }
    // 当时途径加上其实节点
    nowPaths.push(fromVertex.getId());
    // 深度查找边
    for (DirectedDiagraph.Edge edge : fromVertex.getEdges()) {
        // 假如边的方针极点和途径的终究节点一向,表明找到成功
        if (StrUtil.equals(edge.getTargetVertexId(), toVertex.getId())) {
            // 将数据增加到当时途径中
            nowPaths.push(toVertex.getId());
            // 拷贝一份数据放到allPathList中
            List<String> findPaths = new ArrayList<>();
            findPaths.addAll(nowPaths);
            CollUtil.reverse(findPaths);
            allPathList.add(findPaths);
            // 加入了终究节点,回来一次
            nowPaths.pop();
            // 越过,查询下一个边
            continue;
        }
        // 以边的方针极点作为其实极点,持续查找
        DirectedDiagraph.Vertex nextFromVertex = directedDiagraph.getVertextMap().get(edge.getTargetVertexId());
        if (nextFromVertex == null) {
            throw new RuntimeException("极点id不存在");
        }
        // 递归调用下一次
        coreRecGetAllPaths(nextFromVertex, toVertex, nowPaths);
    }
    // 完毕了,没找到,弹出数据
    nowPaths.pop();
}

代码注释比较明晰的,就不再介绍了,主要是利用了深度查找的方法+ 栈保存暂时途径。

然后在DirectedDiagraph类中增加一个方法findAllPaths(),查找一切的途径,如下图:

@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {
    .....
    /**
     * 获取两个极点之间一切或许的数据
     *
     * @param fromVertexId 开始极点
     * @param targetVertexId 方针极点
     * @return
     */
    public Set<String> findAllPaths(String fromVertexId, String targetVertexId) {
        CalcTwoVertexPathlgorithm calcTwoVertexPathlgorithm = new CalcTwoVertexPathlgorithm(this, fromVertexId, targetVertexId);
        // 先核算
        calcTwoVertexPathlgorithm.calcPaths();
        // 打印找到的途径
        calcTwoVertexPathlgorithm.printAllPaths();
        // 然后回来一切的内容
        return calcTwoVertexPathlgorithm.getAllVertexs();
    }
     ....
}

最终,咱们写个单元测试验证下吧。

@Test
public void test1() {
    DirectedDiagraph directedDiagraph = new DirectedDiagraph();
    directedDiagraph.addVertex("A", "A");
    directedDiagraph.addVertex("B", "B");
    directedDiagraph.addVertex("C", "C");
    directedDiagraph.addVertex("D", "D");
    directedDiagraph.addVertex("E", "E");
    directedDiagraph.addEdge("A", "B");
    directedDiagraph.addEdge("B", "C");
    directedDiagraph.addEdge("C", "D");
    directedDiagraph.addEdge("A", "D");
    directedDiagraph.addEdge("B", "D");
    directedDiagraph.addEdge("A", "C");
    directedDiagraph.addEdge("D", "E");
    Set<String> allPaths = directedDiagraph.findAllPaths("A", "D");
    log.info("all vertexIds: {}", allPaths);
}

创立的例子也是咱们前面图片中的例子,咱们看下运行成果是否符合预期。

计算图中两个顶点的所有路径,你会吗

总结

本次需求利用了图这个数据结构得到成果,忽然感觉数据结构和算法真的很重要,感觉现在的做法也不是最优解,功能应该也不是最佳,可是考虑到流程节点数据不会很多,应该能满意业务需求。不知道咱们有没有更好的做法呢?