October 05, 2019

Topological Sort

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

序列中包含每个顶点，且每个顶点只出现一次
若A在序列中排在B的前面，则在图中不存在从B到A的路径

入度 (indegree)：指向该顶点的边的数量；出度 (outdegree)：该顶点指向其他点的边的数量。

问题：
针对给定的有向图找到任意一种拓扑排序的顺序

解法：

从 DAG 图中选择一个入度为 0 的顶点并输出。
从图中删除该顶点和所有以它为起点的有向边。
重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在入度为 0 的顶点为止。后一种情况说明有向图中必然存在环。

Kahn’s algorithm: First, find a list of “start nodes” which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

时间复杂度: O(V+E)，空间复杂度: O(V)

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;

class DirectedGraphNode {
    int label;
    ArrayList<DirectedGraphNode> neighbors;
    DirectedGraphNode(int x) {
        label = x;
        neighbors = new ArrayList<DirectedGraphNode>();
    }
};

public class TopologicalSort {
    /**
    * @param graph: A list of Directed graph node
    * @return: Any topological order for the given graph.
    **/

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        List<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        if (graph == null) {
            return result;
        }
        
        // 1. count in-degree
        HashMap<DirectedGraphNode, Integer> map = new HashMap();
        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
            }
        }
        
        // 2. 
        Deque<DirectedGraphNode> queue = new ArrayDeque<>();
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node)) {
                queue.offer(node);
                result.add(node);
            }
        }
        while (!queue.isEmpty()) {
            DirectedGraphNode node = queue.poll();
            for (DirectedGraphNode node : node.neighbors) {
                map.put(node, map.get(node) - 1);
                if (map.get(node) == 0) {
                    result.add(node);
                    queue.offer(node);
                }
            }
        }
        return result;
    }
}