如何確定在使用寬度優先搜索的有向圖中是否可以達到頂點

Question

當試圖確定有向圖中的頂點是否可達時，我使用寬度優先搜索來遍歷從我的源頂點到圖的頂點目的地頂點。然而，當我比較在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; 
    } 
} 

Answer 1

是您的頂點列表排序正確？如果不是（看起來很可能），您將無法找到from或to鍵並返回false。我說「很可能」，因爲底部的循環有幾個問題，其中一個（tmpTo->processed = 2;您應該使用==）會導致函數始終返回true。