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

在電腦科學和圖論中，解決各種現實生活模型場景的方案嚴重依賴有向圖。這些專門的圖由透過指向其他頂點的有向邊連接的頂點組成。確定兩個指定點之間是否存在路徑是使用有向圖的典型難題。在本文中，我們將探討使用C 解決這個困境的各種方法，包括每個過程所需的語法，以確保事情易於理解。此外，我們將詳細介紹精心說明每種方法的演算法，並包含兩個可執行的程式碼範例。

文法

在深入了解具體細節之前，理解支撐這裡方法論的語言結構是至關重要的。因此，在繼續查看程式碼範例之前，讓我們先檢查這個語法。

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

演算法

在有向圖中找到兩個頂點之間的路徑可以使用多種技術來解決。本文將重點放在兩種廣泛使用的方法−

方法一：深度優先搜尋（DFS）

• 建立一個visited陣列來在遍歷過程中追蹤已造訪的頂點。

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

• 將startVertex標記為已存取。

• 如果起始頂點與結束頂點相同，則傳回true，表示存在一條路徑。

• 對於目前頂點的每個相鄰頂點，以相鄰頂點作為新的起始頂點，遞歸呼叫isPathExists函數。

• 如果任何遞歸呼叫傳回true，則傳回true。

• 如果沒有遞迴呼叫傳回true，則傳回false。

方法二：廣度優先搜尋（BFS）

• 建立一個visited陣列來在遍歷過程中追蹤已造訪的頂點。

• 將visited陣列的所有元素初始化為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'，否則繼續下一步，即探索附近的外圍點。在這個探索過程中，任何相鄰的未探索頂點在放入隊列進行更深層次的迭代檢查之前都會被標記為'visited'，並測試它們是否與endVertex匹配。

在所有的探索和驗證都成功之後，如果佇列中沒有任何添加，則函數將傳回false。

結論

在電腦科學的發展中，導航有向圖的複雜性可能會構成一個基本問題。為了減輕這些挑戰，我們的目標之一是探索使用C 實現的兩種常見方法。深度優先搜尋（DFS）和廣度優先搜尋（BFS）是這些技術的前沿，它們提供了逐步演示每個演算法的流程和工作程式碼範例。一旦掌握了這些方法，就可以在處理多個設定（如路由網路或分析社交連接框架）的路徑查找障礙時激發新的潛力，並在增強開發階段中作為有價值的起點。

以上是在有向圖中找到兩個頂點之間是否存在路徑的詳細內容。更多資訊請關注PHP中文網其他相關文章！