三色图算法与恒恒性

Question

为了进行拓扑排序，我需要在图上应用三色algorithm1。也就是说，假设顶点是白色的，则该算法将实现如下

void visit(Vertex& v)
    {
    v.color=GRAY;
    auto child=v.children.begin();
    auto v_end=v.children.end();
    while(child!=v_end)
        {
        if(child->color==GRAY)
            {throw "Loop detected";}
        if(child->color==WHITE)
            {visit(*child);}
        ++child;
        }
    v.color=BLACK;
    }

现在，我希望算法不修改v，所以它可以是没有mutable的const。什么是最有效的方式使这一工作？有些想法是

• 在处理图形之前复制它
• 使用std::map<Vertex*,color_type>
• 在前一次传递时给每个顶点一个id，这样的id对应于访问顶点的顺序。然后，颜色可以存储在一个数组中。

1

Answer 1

我通过在构造过程中给图中的每个节点一个id来解决这个问题。然后，我在对图形排序时使用了一个临时数组。复杂性：

• 构造期间的两个附加操作(检索节点计数和分配id)。固定的时间。
• 一个数组查找，以获得顶点颜色。定时间

因此没有额外的复杂性。