查詢有向圖中兩個頂點之間是否存在路徑

---

在計算機科學和圖論中，許多現實世界模型場景的解決方案都嚴重依賴於有向圖。這些特殊的圖由透過指向其他頂點的有向邊連線的頂點組成。確定兩個指定點之間是否存在路徑是有向圖使用中的一個典型問題。在這篇文章中，我們將探討使用 C++ 解決此問題的各種方法，包括每個過程所需的語法，以確保易於理解。此外，我們將提供詳細的演算法，仔細說明每種方法，幷包含兩個可執行的程式碼示例。

語法

在深入研究細節之前，理解這裡使用的基本語言結構至關重要。因此，讓我們首先檢查語法，然後再繼續介紹程式碼示例。

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph);

演算法

可以使用多種技術來識別有向圖中兩個頂點之間的路徑。本文將重點討論兩種廣泛使用的方法：

方法 1：深度優先搜尋 (DFS)

• 建立一個訪問陣列來跟蹤遍歷期間訪問的頂點。

• 將訪問陣列的所有元素初始化為 false。

• 將 startVertex 標記為已訪問。

• 如果 startVertex 與 endVertex 相同，則返回 true，因為存在路徑。

• 對於當前頂點的每個相鄰頂點，遞迴呼叫 isPathExists 函式，並將相鄰頂點作為新的 startVertex。

• 如果任何遞迴呼叫返回 true，則返回 true。

• 如果沒有任何遞迴呼叫返回 true，則返回 false。

方法 2：廣度優先搜尋 (BFS)

• 建立一個訪問陣列來跟蹤遍歷期間訪問的頂點。

• 將訪問陣列的所有元素初始化為 false。

• 建立一個佇列來儲存要處理的頂點。

• 將 startVertex 入隊並將其標記為已訪問。

• 如果佇列不為空，則執行以下操作：

• 從佇列中出隊一個頂點。

• 如果出隊的頂點與 endVertex 相同，則返回 true，因為存在路徑。

• 對於出隊頂點的每個相鄰頂點，如果它未被訪問，則將其入隊並將其標記為已訪問。

• 如果佇列變空且未找到路徑，則返回 false。

示例 1：深度優先搜尋 (DFS) 方法

#include <iostream>
#include <vector>
using namespace std;

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   if (startVertex == endVertex)
      return true;
  
   for (int adjVertex : graph[startVertex]) {
      if (!visited[adjVertex] && isPathExists(adjVertex, endVertex, graph))
         return true;
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

輸出

A path exists between 0 and 5

程式碼首先定義一個名為 isPathExists 的函式，該函式接收 startVertex、endVertex 和表示為鄰接列表的圖作為輸入。它初始化一個名為 visited 的布林向量來跟蹤已訪問的頂點。執行此函式時，它首先檢查 startVertex 和 endVertex 是否相同。

如果這些頂點在此上下文中位於相同位置，則函式立即返回 true。

如果不是這種情況，並且它們彼此不同，則採取另一個操作來檢查它們的鄰接性，以確定它們之間是否存在路徑。

此過程涉及反覆遍歷起始頂點的相鄰頂點；每次迭代都遞迴地呼叫“isPathExists”，使用新搜尋的頂點作為新的起點來繼續尋找可用的路徑。這個迴圈會重複自身，直到所有可能的路徑都用盡，或者偶然發現一條成功的路徑。

如果這些遞迴呼叫中的任何一個檢測到任何現有的可能邊連線兩個指定的節點（起始節點和結束節點），則此類篩選的輸出將意味著這兩個節點之間確實存在可用互連。因此，將立即返回 True。

否則，將啟動一個故障安全迴圈操作來檢測何時根據此處演算法中設定的複雜性完全不存在可用路線。在獲得此類結果後，它將返回 False，表示這兩個命名節點之間連線不成功。

示例 2：廣度優先搜尋 (BFS) 方法

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   queue<int> verticesQueue;
   verticesQueue.push(startVertex);
  
   while (!verticesQueue.empty()) {
      int currVertex = verticesQueue.front();
      verticesQueue.pop();
  
      if (currVertex == endVertex)
         return true;
  
      for (int adjVertex : graph[currVertex]) {
         if (!visited[adjVertex]) {
            visited[adjVertex] = true;
            verticesQueue.push(adjVertex);
         }
      }
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

輸出

A path exists between 0 and 5

程式碼定義了 isPathExists 函式，該函式接收 startVertex、endVertex 和表示為鄰接列表的圖作為輸入。它初始化一個名為 visited 的布林向量來跟蹤已訪問的頂點，以及一個名為 verticesQueue 的佇列來儲存要處理的頂點。

該函式首先將 startVertex 入隊並將其標記為已訪問。我們的演算法的功能從進入一個迭代迴圈開始，該迴圈持續存在，只要其處理佇列結構中仍然存在專案。隨著這種結構化重複的進行，每個迴圈執行兩個檢查：首先驗證當前迭代的出隊頂點是否與前面執行中指定的端點目標匹配；如果兩者成功匹配，則返回“true”，否則繼續執行下一步，該步驟涉及探索附近的外部點。在此探索過程中，任何相鄰的未探索頂點都會獲得“已訪問”標記，然後將其放入佇列中，以便進行更深入的迭代檢查和測試它們是否導致 endVertex 匹配。

在所有探索和驗證都成功後，如果佇列中沒有新增任何內容，則該函式返回 false。

結論

處理有向圖的複雜性在計算機科學開發中可能是一個基本問題。在我們探索使用 C++ 實現的兩種流行方法時，緩解這些挑戰是我們目標之一。深度優先搜尋 (DFS) 和廣度優先搜尋 (BFS) 處於此類技術的最前沿，它們提供逐步介紹每個演算法步驟的過程方法，同時為這兩種模型提供可執行的程式碼示例。一旦掌握了這些方法，在解決多種環境（例如路由網路或分析社會聯絡框架）中的尋路障礙時，它們就會激發新的潛力，同時在增強開發階段充當有價值的跳板。