Posts Tagged ‘graph’
- In: classic
- 3 Comments
给一个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
算法：
- 一个map<Node, Boolean>记录走过的节点，false表示visiting (gray), true表示visited (black)，无环图说明不会遇见灰色节点（一个节点还没visit完呢就又遇见它了），否则就是有环了（circular dependent）。
- 每次从白色节点（set里）里挑一个，从它开始DFS。
- DFS就是把这个节点涂灰，然后顺次DFS它的孩子，每个先visited的孩子的list都插在dummy head的最前面，所以老二的孙子其实排在老大前面（比如C的老大是D，老二是E->F，结果就是CEFD（最后把父亲放最前面）。这样保证每个孩子序列都是原来顺序，各个孩子树之间反正没关系，就顺次排开就行了。
- 每次一个节点被涂黑，就从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();
}
[leetcode] Clone Graph | 克隆无向图
Posted on: October 8, 2013
倒是20分钟写出来了bugfree，比较喜欢这种利用data structure的题，感觉试一试总能想出来。
这个题就是基本BFS，要点是生成新节点的同时，怎么把新节点和其他新节点连起来呢？这就需要一个新旧节点对应map，每次生成新节点A’，要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’，因为下次把A当作root的时候，还会经历B作为child，这时再A’->B’。
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null)
return null;
Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
enqueueAndClone(q, node, map);
while (!q.isEmpty()) {
UndirectedGraphNode parent = q.poll();
for (UndirectedGraphNode child : parent.neighbors) {
if (!map.containsKey(child))
enqueueAndClone(q, child, map);
map.get(parent).neighbors.add(map.get(child));//不管是否visit过，都要单向连接
}
}
return map.get(node);
}
private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
q.add(node);
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node, newNode);
}
Lexi's Leetcode solutions 