“This is my 40th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

What is topological ordering of graphs?

Topological ordering of graphs: according to the order of precedence, the work can be successfully completed at a time, and there is no lack of a dependent order, so it is the so-called topological order, can not appear cyclic dependence or ring

For topological ordering it must be directed, it must be acyclic, it must be directed acyclic, because if you have rings, you don’t know what the order is, right

Topological sorting is not unique

2. Topic 1

The topological sorting results of the graph are as follows: (A,D,E,F), (A,E,D,F)

1, analysis,

In using custom graphs

When A goes out, the in of D and E is minus 1

Using the entry degree (in) of the self-defined graph structure, where in is 0 means zero nodes pointing to it, topological ordering of graphs is realized according to this principle

2, implementation,

// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
    // key Specifies the remaining value of a node
    Map<Node, Integer> inMap = new HashMap<>();
    // Only the remaining points with an input of 0 will enter the queue
    Queue<Node> zeroInQueue = new LinkedList<>();
    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        if (node.in == 0) {
            zeroInQueue.add(node);
        }
    }
    List<Node> result = new ArrayList<>();
    while(! zeroInQueue.isEmpty()) { Node cur = zeroInQueue.poll(); result.add(cur);for (Node next : cur.nexts) {
            inMap.put(next, inMap.get(next) - 1);
            if (inMap.get(next) == 0) { zeroInQueue.add(next); }}}return result;
}
Copy the code

3. Topic 2

linkcode

1, analysis,

Topological ordering of graphs must be directed acyclic graphs, which can be sorted from large to small using point size

x->y->z

If y is 90, x must be greater than 90, so if x is greater than or equal to y, then x must be in front of y, so it’s not a problem

If x from their walk back again, some time again, it is concluded that x, y go back again and again some time, or a set out from oneself also calculate again, is this a process, before there are calculated, which means the road, can be recorded, when the use, directly get the results, not quick zai, can use the memory cache to record, promote efficiency

Mnemonic search (mnemonic cache or kill cache)

2, implementation,

2.1. Method 1

public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    HashMap<DirectedGraphNode, Integer> indegreeMap = new HashMap<>();
    for (DirectedGraphNode cur : graph) {
        indegreeMap.put(cur, 0);
    }
    for (DirectedGraphNode cur : graph) {
        for (DirectedGraphNode next : cur.neighbors) {
            indegreeMap.put(next, indegreeMap.get(next) + 1);
        }
    }
    Queue<DirectedGraphNode> zeroQueue = new LinkedList<>();
    for (DirectedGraphNode cur : indegreeMap.keySet()) {
        if (indegreeMap.get(cur) == 0) {
            zeroQueue.add(cur);
        }
    }
    ArrayList<DirectedGraphNode> ans = new ArrayList<>();
    while(! zeroQueue.isEmpty()) { DirectedGraphNode cur = zeroQueue.poll(); ans.add(cur);for (DirectedGraphNode next : cur.neighbors) {
            indegreeMap.put(next, indegreeMap.get(next) - 1);
            if (indegreeMap.get(next) == 0) { zeroQueue.offer(next); }}}return ans;
}
Copy the code

2.2. Method 2

public static class Record {
    public DirectedGraphNode node;
    public long nodes;

    public Record(DirectedGraphNode n, long o) { node = n; nodes = o; }}public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    HashMap<DirectedGraphNode, Record> order = new HashMap<>();
    for (DirectedGraphNode cur : graph) {
        f(cur, order);
    }
    ArrayList<Record> recordArr = new ArrayList<>();
    for (Record r : order.values()) {
        recordArr.add(r);
    }
    recordArr.sort((o1, o2) -> Long.compare(o2.nodes, o1.nodes));
    ArrayList<DirectedGraphNode> ans = new ArrayList<>();
    for (Record r : recordArr) {
        ans.add(r.node);
    }
    return ans;
}

// Now come to cur, please return to cur, all times!
// return (cur, click time)
// Cache ！！！！！ order
// key: the number of times a point is clicked.
// value: The number of clicks
public static Record f(DirectedGraphNode cur, HashMap<DirectedGraphNode, Record> order) {
    if (order.containsKey(cur)) {
        return order.get(cur);
    }
    // cur = 0;
    long nodes = 0;
    for (DirectedGraphNode next : cur.neighbors) {
        nodes += f(next, order).nodes;
    }
    Record ans = new Record(cur, nodes + 1);
    order.put(cur, ans);
    return ans;
}
Copy the code

Four,

Using the entry degree (in) of the self-defined graph structure, where in is 0 means zero nodes pointing to it, topological ordering of graphs is realized according to this principle

Topological sorting algorithm of graph:

1. Find the output of all points in the graph with an entry degree of 0
2. Delete all the points with 0 degree of entry from the graph, and continue to find the output of the points with 0 degree of entry, and repeat
3. After all points of the graph have been deleted, the order of output is topological sort

Required: directed graph with no rings

Application: event scheduling, compile order