資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學滿足路徑包含頂點 A 和 B 的頂點對數
本文介紹了計算圖中滿足路徑包含指定頂點 A 和 B 的頂點對數的方法。它首先使用深度優先搜尋 (DFS) 演算法遍歷圖的網路，並統計滿足條件的頂點對。該演算法執行兩次獨立的 DFS 遍歷。第一次遍歷移除頂點 B，並計算從頂點 A 可到達的頂點數；第二次遍歷移除頂點 A，並計算從頂點 B 可到達的頂點數。然後，將每次遍歷中可到達的頂點數從圖的總頂點數中減去，得到分別排除 A 和 B 後不可到達的頂點數。最後，將這兩個計數相加，得到滿足條件的頂點對總數。
使用的方法
深度優先搜尋 (DFS)
廣度優先搜尋 (BFS)
深度優先搜尋 (DFS)
給定的程式碼使用基於深度優先搜尋的方法。首先，使用 DFS 查詢滿足路徑包含兩個給定頂點的頂點對數量。它使用 DFS 計算從特定頂點可達到的頂點數，同時排除另一個給定頂點。透過執行兩次 DFS（一次移除頂點 B，一次移除頂點 A），程式碼計算在每種情況下無法到達的頂點數。最終結果是這兩個計數的乘積。這種方法利用 DFS 遍歷圖的網路，並檢查在移除所需頂點後無法到達的頂點數。然後，計算滿足給定條件的頂點對總數。
演算法
從給定的圖開始，用鄰接表表示。
將計數變數 (cnt) 初始化為 0。
初始化一個訪問陣列 (vis) 來跟蹤已訪問的頂點。將所有頂點標記為未訪問。
從頂點 A 開始執行深度優先搜尋 (DFS)。
將頂點 A 標記為已訪問。
將 cnt 變數加 1。
對於 A 的每個相鄰頂點 (neighbor)
如果鄰居未訪問且未到達頂點 B，則遞迴呼叫 DFS 函式處理鄰居。
從頂點 A 開始的 DFS 完成後，將 cnt 的值儲存在一個變數 (count1) 中。
重置訪問陣列 (vis) 和 cnt 為 0。
從頂點 B 開始執行另一個 DFS。
將頂點 B 標記為已訪問。
將 cnt 變數加 1。
對於 B 的每個相鄰頂點 (neighbor)
如果鄰居未訪問且未到達頂點 A，則遞迴呼叫 DFS 函式處理鄰居。
從頂點 B 開始的 DFS 完成後，將 cnt 的值儲存在另一個變數 (count2) 中。
計算結果：count1 乘以 count2。
輸出結果，即滿足路徑包含頂點 A 和 B 的頂點對數。
示例
#include <iostream>
#include <vector>
using namespace std;
int num_vertices, num_edges, a, b;
// Function to perform DFS on the given graph
// starting from the vertex 'start'
int performDFS(int start, int target, vector<int> graph[], vector<bool>& visited)
{
visited[start] = true;
int count = 1;
// Perform DFS on the adjacent vertices
for (auto adjacent : graph[start]) {
if (!visited[adjacent] && adjacent != target)
count += performDFS(adjacent, target, graph, visited);
}
return count;
}
// Function to calculate the number of pairs
// such that the path between any two pairs
// contains the given two vertices A and B
int calculatePairs(vector<int> graph[])
{
vector<bool> visited(num_vertices + 1, false);
int count_a = performDFS(a, b, graph, visited);
visited.assign(num_vertices + 1, false);
int count_b = performDFS(b, a, graph, visited);
int ans1 = num_vertices - count_a - 1;
int ans2 = num_vertices - count_b - 1;
return ans1 * ans2;
}
int main()
{
num_vertices = 7, num_edges = 7, a = 3, b = 5;
int edges[][2] = { {1, 2},
{2, 3},
{3, 4},
{4, 5},
{5, 6},
{6, 7},
{7, 5} };
vector<int> graph[num_vertices + 1];
// Loop to create the graph
for (int i = 0; i < num_edges; i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
int result = calculatePairs(graph);
cout << "Number of pairs such that the path between each pair contains the vertices " << a << " and " << b << ": " << result << endl;
return 0;
}
輸出
Number of pairs such that the path between each pair contains the vertices 3 and 5: 4
廣度優先搜尋 (BFS)
在廣度優先搜尋 (BFS) 方法中，我們以廣度優先的方式遍歷圖。從給定的起始頂點開始，我們首先訪問其所有鄰居，然後移動到下一層鄰居。我們使用佇列來跟蹤要訪問的頂點。當我們訪問每個頂點時，我們將其標記為已訪問以避免重複訪問。BFS 在查詢兩個頂點之間的最短路徑方面非常有效，並且廣泛用於圖遍歷和路徑查詢問題。它確保按與源的距離遞增的順序訪問頂點。
演算法
建立一個空佇列和一個訪問陣列。
將源頂點入隊並標記為已訪問。
當佇列不為空時，執行以下操作：
從佇列的頭部出隊一個頂點。
處理出隊的頂點（例如，列印它或執行所需的操作）。
將所有未訪問的鄰居入隊並標記為已訪問。
重複步驟 3 直到佇列為空。
如果仍然有未訪問的頂點，則返回步驟 2 並選擇另一個未訪問的頂點作為源。
當所有頂點都被訪問後，終止演算法。
示例
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void bfs(vector<vector<int>>& graph, int source) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(source);
visited[source] = true;
while (!q.empty()) {
int vertex = q.front();
q.pop();
cout << vertex << " "; // Process the visited vertex (e.g., print it)
for (int neighbor : graph[vertex]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
int numVertices = 6;
vector<vector<int>> adjacencyList(numVertices);
// Build the graph
adjacencyList[0] = {1, 2};
adjacencyList[1] = {3, 4};
adjacencyList[2] = {4, 5};
adjacencyList[3] = {5};
adjacencyList[4] = {};
adjacencyList[5] = {};
int source = 0;
bfs(adjacencyList, source);
return 0;
}
輸出
0 1 2 3 4 5
結論
本文介紹了兩種方法，深度優先搜尋 (DFS) 和廣度優先搜尋 (BFS)，用於查詢圖中滿足路徑包含兩個指定頂點 A 和 B 的頂點對數。DFS 方法執行兩次獨立的 DFS 遍歷，分別移除頂點 A 或 B，以計算仍然可以到達的頂點數。BFS 方法以分層的方式遍歷圖，從給定的源頂點開始，以查詢最短路徑並訪問所有可到達的頂點。這兩種方法都提供了有效的分析圖並根據給定條件計算所需頂點對的方法。
73 次瀏覽
