当试图确定有向图中的顶点是否可达时，我使用广度优先搜索来从我的源顶点到目标顶点遍历图形 . 但是，当我比较bfs期间从队列中弹出的内容（应该是我访问过的每个顶点）时，它只返回false并且从不在任何实例中都是true，尽管我知道图形在某些情况下可以返回true，可以帮助一些我出去？
这是我的代码
template <typename E>
bool Graph<E>::isReachable(E fromKey, E toKey) const
{
Edge* tmpEdge;
Edge* pred;
Edge* edgeWalk;
Vertex* walkPtr;
Vertex* toPtr;
Vertex* tmp;
Vertex* tmpFrom;
Vertex* tmpTo;
queue<Vertex*> q;
/* find source vertex */
tmpFrom = first;
while (tmpFrom != NULL && fromKey > tmpFrom->data)
tmpFrom = tmpFrom->pNextVertex;
if (tmpFrom == NULL || fromKey != tmpFrom->data)
return false;
/* locate destination vertex */
tmpTo = first;
while (tmpTo != NULL && toKey > tmpTo->data)
tmpTo = tmpTo->pNextVertex;
if (tmpTo == NULL || toKey != tmpTo->data)
return false;
walkPtr = first;
while (walkPtr != NULL)
{
walkPtr->processed = 0;
walkPtr = walkPtr->pNextVertex;
}
walkPtr = first;
while (walkPtr != NULL)
{
if (walkPtr->processed < 2)
{
if (walkPtr->processed < 1)
{
q.push(walkPtr);
walkPtr->processed = 1;
}
}
while (!q.empty())
{
tmp = q.front();
q.pop();
tmp->processed = 2;
edgeWalk = tmp->pEdge;
while (edgeWalk != NULL)
{
toPtr = edgeWalk->destination;
if (toPtr->processed == 0)
{
toPtr->processed = 1;
q.push(toPtr);
}
edgeWalk = edgeWalk->pNextEdge;
}
if (tmpTo->processed = 2)
return true;
}
return false;
}
}
1 回答
您的顶点列表是否正确排序？如果它不是't (as appears likely), you'将无法找到from或to键并返回false . 我说"likely"，因为你的循环底部有几个问题，其中一个（
tmpTo->processed = 2;你应该使用==）会导致函数一直返回true .