java实现DAG广度优先便利

在调度系统中经常可以看到有向无环图，假如我们用点表和边表来存储一个图，那么如何能实现按照优先级的排序呢？

下面是我的一个实现：

一、方案1

子节点的优先级等于父节点的和？

问题：虽然可以保证子节点一定大于等于父节点，但如果只有一个父节点，会导致父子优先级相同，因此否掉

二、方案2

子节点的优先级等于被指向的次数

问题：被指向的次数多不代表优先级低，否掉

三、方案3

子节点优先级=父节点优先级的和，再加上被指向次数

继承了方案1/2的优点，接下来看怎么实现？

一开始想的是遍历边表，然后节点的优先级直接等于被指向次数+父节点优先级，发现有一个问题，父节点优先级后续有可能变化，但前面的子节点无法感知

升级方案：

1.先遍历边表，实现一个父节点的子节点map

2.重新遍历边表，对被指向节点进行+1操作，之后递归遍历被指向节点的所有下游节点，统一进行+1操作，这样就实现了：

在当前to节点+1时完成了被指向次数的初始化，

递归子节点统一+1，完成了子节点=父节点优先级的求和操作。（上游节点自增时，下游都跟着自增，上游增多少，下游就增多少）

public class GraphUtil {
    public static void main(String[] args) {
        Set<String> nodes = Sets.newHashSet("A", "B", "C", "D", "E", "F", "G");
        List<String> nodeList = Lists.newArrayList("G->E", "G->F", "E->D", "F->C","C->B", "C->A","B->A");
        List<Edge<String, String>> edges = nodeList.stream().map(str -> {
            String[] split = str.split("->");
            String from = split[0];
            String to = split[1];
            return new Edge<>(from, to);
        }).collect(Collectors.toList());

        Graph graph = new Graph(nodes, edges);
        Set<String> headNodes = findHeadNodes(graph);
        System.out.println(headNodes);
        Map<String, Integer> priority = findPriority(graph);
        System.out.println(priority);
    }

    /**
     * 解决方案1：
     * 通过计算被指向的次数，来计算节点的执行顺序
     * 问题：被指向的次数多，不一定优先级低！
     * 解决方案2：
     * 设置被指向节点优先级=所有父节点的和，保证子节点一定比父节点大
     * 问题：如果子节点只有一个父节点，子节点的优先级就会跟父节点相同！
     * 解决方案3：
     * 0.设置被指向节点优先级=所有父节点的和+被指向次数
     * 1.遍历边表，先生成一个父节点和子节点的映射map
     * 2.再次遍历边表，如果是头节点，默认值设0，如果是尾节点默认设0，已存在=节点原有值+1
     * 3.递归给尾节点的所有下游节点+1
     * 如此则避免了方案1、2的缺陷，保证子节点的优先级一定低于双亲节点
     *
     * @param graph
     * @return
     */
    public static Map<String, Integer> findPriority(Graph graph) {
        List<Edge<String, String>> edges = graph.getEdges();
        HashMultimap<String, String> childMap = HashMultimap.create();
        TreeMap<String, Integer> priorityMap = new TreeMap<>();

        for (Edge<String, String> s : edges) {
            String from = s.getStart();
            String to = s.getEnd();
            childMap.put(from, to);
        }

        System.out.println(childMap);

        for (Edge<String, String> s : edges) {
            String from = s.getStart();
            String to = s.getEnd();
            priorityMap.putIfAbsent(from, 0);
            priorityMap.putIfAbsent(to, 0);
            priorityMap.computeIfPresent(to, (k, v) -> v = v + 1);
            //不仅to自己更新，还要递归更新自己的下游节点
            updateChild(priorityMap, childMap, to);
        }

        return priorityMap;
    }

    /**
     * 只要某个节点+1，那么它后面的所有子节点都递归加1
     *
     * @param priorityMap
     * @param childMap
     * @param parent
     */
    public static void updateChild(TreeMap<String, Integer> priorityMap, HashMultimap<String, String> childMap, String parent) {
        if (childMap.containsKey(parent)) {
            Set<String> children = childMap.get(parent);
            for (String child : children) {
                priorityMap.putIfAbsent(child, 0);
                priorityMap.computeIfPresent(child, (k, v) -> v + 1);
                if (childMap.containsKey(child)) {
                    updateChild(priorityMap, childMap, child);
                }
            }
        }
    }

    /**
     * 查找头节点，可能不是一个
     *
     * @param graph
     * @return
     */
    public static Set<String> findHeadNodes(Graph graph) {
        List<Edge<String, String>> edges = graph.getEdges();
        Multimap<String, String> dependMap = HashMultimap.create();
        Map<String, Integer> priorityMap = new TreeMap<>();
        for (Edge<String, String> edge : edges) {
            String from = edge.getStart();
            String to = edge.getEnd();
            priorityMap.putIfAbsent(from, 0);
            priorityMap.putIfAbsent(to, 0);
            dependMap.put(to, from);
            priorityMap.computeIfPresent(to, (k, v) -> v = v + 1);
        }

        Set<String> set = Sets.newHashSet();
        for (Map.Entry<String, Integer> s : priorityMap.entrySet()) {
            if (s.getValue() == 0) {
                set.add(s.getKey());
            }
        }
        return set;
    }


}

Graph类，Edge类

/**
 * @Author : wangbin
 * @Date : 2021/9/28 14:36
 * @Description: 以边表和点表构成的有向无环图数据结构
 */
@Data
@AllArgsConstructor
public class Graph {
    private Set<String> nodes;
    private List<Edge<String, String>> edges;
}

//======================================

@Data
@AllArgsConstructor
public class Edge<S,E> {
    private S start;
    private E end;

}

输出：

[G]
{B=[A], C=[A, B], E=[D], F=[C], G=[E, F]}
{A=7, B=3, C=2, D=2, E=1, F=1, G=0}

 补充：

虽然得到了treeMap,但是它是以key进行排序，如果想按照value输出，还有进行处理

/**
     * 获取以优先级顺序排序的<任务：优先级>list
     * @param graph
     * @return
     */
    public static List<Map.Entry<String, Integer>> getPriorityList(Graph graph) {
        TreeMap<String, Integer> priorityMap = findPriority(graph);
        List<Map.Entry<String, Integer>> entries = new ArrayList<>(priorityMap.entrySet());
        entries.sort(Map.Entry.comparingByValue());
        return entries;
    }