Lexi's Leetcode solutions

[classic] DAG Topological sort | 有向无环图拓扑排序

Posted on: October 13, 2013

给一个Set<Node>,每个节点里面有个List<Node> children,求它的sorted list representation http://en.wikipedia.org/wiki/Topological_sorting。Google phone就挂这了。

比如下图,假设箭头全是向下的,则return list就是A->C->E->F->B->D,就是其中一个valid solution。所有dependent关系都满足,然后那些无dependent关系的(比如B和C, D和E就任意顺序就行)。

  A
/   \
B   C
\   /\
  D   E -> F

算法:

  1. 一个map<Node, Boolean>记录走过的节点,false表示visiting (gray), true表示visited (black),无环图说明不会遇见灰色节点(一个节点还没visit完呢就又遇见它了),否则就是有环了(circular dependent)。
  2. 每次从白色节点(set里)里挑一个,从它开始DFS。
  3. DFS就是把这个节点涂灰,然后顺次DFS它的孩子,每个先visited的孩子的list都插在dummy head的最前面,所以老二的孙子其实排在老大前面(比如C的老大是D,老二是E->F,结果就是CEFD(最后把父亲放最前面)。这样保证每个孩子序列都是原来顺序,各个孩子树之间反正没关系,就顺次排开就行了。
  4. 每次一个节点被涂黑,就从set里remove。直到set空了为止。
Node topoSort(Set<Node> set) {
    Map<Node, Boolean> map = new HashMap<Node, Boolean>;
    Node dummy = new Node();
    while (!set.isEmpty()) {
        Node node = set.iterator().next();
        dfs(node, dummy, set, map);
    }
    return dummy.next();
} 
void dfs(Node node, Node dummy, Set<Node> unBlacked, Map<Node, Boolean> map) {
    if (!map.containsKey(node)) {
        map.put(node, false);
        for (Node child : node.children) {     
            dfs(child, dummy, set, map);
        }
        Node break = dummy.next;
        dummy.next = node;
        node.next = break;
        map.put(node, true);//mark black
        set.remove(node);
     } else if (map.get(node) == false) {
        //gray, there's a loop
        throw new LoopExistException(); 
}
Advertisements
Tags: ,

3 Responses to "[classic] DAG Topological sort | 有向无环图拓扑排序"

为什么感觉用lz的解法,在上面的例子中,D会排到B的前面呢?

我明白了,原来每次都是把node放到dummy的最前面,没错

应该说是node放到dummy后面的最前面 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: