我创建了一个包含链接列表 vector 的类。每个链接列表代表我图中的一个顶点。连接到我的链表的节点被认为是这些顶点之间的边。我正在尝试为我的图形创建 DFS 函数，但在设置顶点颜色时遇到了问题。我意识到我的代码有很多问题，但我正在努力解决一个问题。我的 DFSit() 函数以无限循环结束，因为我的列表的颜色属性实际上并未设置为“灰色”。知道为什么会这样吗？
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 例程的正确实现是使用堆栈进行的，但这也可以。
我认为您正在为节点 AdjList x 着色，并且此着色不会保存，因为您通过 val 而不是 ref 传递它。
尝试将 void Graph::DFSit(AdjList x, int root) 更改为 void Graph::DFSit(AdjList& x, int root)
关于c++ - 深度优先搜索 (C++)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22903583/