c++ - 如何使用广度优先搜索确定在有向图中是否可以到达顶点

当尝试确定有向图中的某个顶点是否可达时，我使用广度优先搜索将图从我的源顶点遍历到目标顶点。但是，当我比较在bfs（应该是我访问过的每个顶点）期间从队列中弹出的内容时，尽管我知道图形在某些情况下可以返回true，但它只会返回false，并且在任何情况下都不会返回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;
   }
}

最佳答案

您的顶点列表是否正确排序？如果不是（可能出现），则您将无法找到from或to键并返回false。我说“可能”，因为循环的底部有几个问题，其中之一（tmpTo->processed = 2；您应该使用==）将导致函数始终返回true。

关于c++ - 如何使用广度优先搜索确定在有向图中是否可以到达顶点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43055468/