c++ - 深度优先搜索(C++)

我创建了一个包含链接列表 vector 的类。每个链表都代表我图中的一个顶点。连接到我的链表的节点被视为这些顶点之间的边。我正在尝试为图形创建DFS函数，但在设置顶点颜色时遇到了麻烦。我意识到我的代码有很多问题，但是我正在尝试特别解决一个问题。我的DFSit()函数最终陷入无限循环，因为列表的color属性实际上并未设置为“灰色”。知道为什么会这样吗？

void Graph::DFS()
{
    int i = 0;
    while (i != myvector.size())
    {

        DFSit(myvector[i], myvector[i].val);
        myvector[i].color = "black";
        i++;
    }
}

void Graph::DFSit(AdjList x, int root)
{
if (x.color == "white")
{
    cout << "tree edge ( " << root << "," << x.val << ") " << endl;
}
if (x.color == "gray")
{
    cout << "Back Edge ( " << root << "," << x.val << ") " << endl;
    return;
}

    x.color = "gray";

    AdjNode *temp = new AdjNode();
    temp = x.front;
    int i = 0;
    int value;
    while (temp != NULL)
    {
        value = temp->getValue();
        while (i != myvector.size())
        {
            if (value == myvector[i].val)
            {
                DFSit(myvector[i], root);
            }
            i++;
        }
        temp = temp->next;
    }

}

最佳答案

通常，DFS rutine的正确实现是通过堆栈实现的，但这也可以工作。
我认为您正在为节点AdjList x着色，并且此着色不会保存，因为您是通过val而不是通过ref传递它。
尝试将void Graph::DFSit(AdjList x, int root)更改为void Graph::DFSit(AdjList& x, int root)