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;
}
}
}
－
－
－