for each node v

perform a maximal flow between v and 0 to obtain the minimal cut (=mc);

set the key of v to mc and insert it into a Fibonacci heap h;

end

while(true)

v = h.extract_min(); (based on the key)

remove v and all edges incident on v;

if(node 1 is disconnected from node 0)

return v.key;

end
end

是CLRS page 216 10.4-5


Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

In your case:

MC(1) = 3;
MC(2) = 2;
MC(3) = 1;
MC(4) = 2;
MC(5) = 5;

min cut means the minimal number of cuts to disconnect the source node from the sink node, so for node 1, we only need to cut the following edges:
(1, 5), (2, 0), (4, 0). Of course there are some other minimal cuts.

Accoring to my algorithm, it will output 3.

According to what you have said, you want to first cut (1, 5), then the spy has only two paths to escape, namely, through node 2 and through node 4. For the path that bypasses node 2, you have to wait until the spy has entered room 2, then you need to cut (1, 2) and (2, 0), which incurs two cuts, so in total, it's three cuts. Similarly for the path through node 4.

If you cut (1, 5) in the first place, and then wait until the spy has entered room 2, and you only cut (2, 0), then the spy can turn back to choose the path that goes through node 4. So you still need to cut (1, 4) or (4, 0). In this case, you again need three cuts, which matches the output of my algorithm.

Sorry I overlooked the edge (3, 0) in your specification. So the min cuts of each node are indeed:

MC(1) = 4;
MC(2) = 2;
MC(3) = 2;
MC(4) = 2;
MC(5) = 5;

You are right. My algorithm does not work for your case.

Let me think about it further.

When I was asking for the answer, I didn't presume there is a parent link in each node, though. However, I guess the parent link is necessary.

for each node, store a number which is initialized to be the number of edges incident on that node. For node 0 (which represents outside), the number is infinity. we denote the number as node.mc.


changed = true;
while(changed)
{
changed = false;
for_each(node n in the graph except node 0)
{
sort n's adjacent nodes based on mc (from large to small).
k = 0; k1 = 0; prev_node = null;
for_each(node adj_n in the sorted adjacent nodes n)
{
if(adj_n.mc + k < n.mc)
{
n.mc = k + adj_n.mc;
changed = true;
}
k1 += number of edges between adj_n and n;
if(prev_node.mc > adj_n.mc)
{
k = k1;
}
prev_node = adj_n;
}
}
}

return node1.mc;