我创建了一个包含链接列表向量的类。每个链表都代表我图中的一个顶点。连接到我的链表的节点被视为这些顶点之间的边。我正在尝试为图形创建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)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句