資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢偶數距離節點對的數量
為了發現圖中偶數距離節點對的數量，我們將使用圖遍歷演算法。從每個節點開始，我們執行遍歷，例如廣度優先搜尋 (BFS) 或深度優先搜尋 (DFS)，並跟蹤所有節點與起始節點的距離。在遍歷過程中，我們統計遇到偶數距離的節點數量。透過對所有節點重複此過程，我們得到圖中偶數距離節點對的總數。這種方法使我們能夠有效地確定在不同圖結構中滿足給定條件的節點對的數量。
使用的方法
圖遍歷方法
DFS
圖遍歷方法
查詢偶數距離節點對數量的圖遍歷方法包括使用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 等遍歷演算法來探索圖。從圖中的每個節點開始，我們遍歷其相鄰節點並跟蹤節點之間的距離。透過在遍歷過程中統計遇到偶數距離的節點數量，我們將確定偶數距離的節點對的數量。這種方法有效地分析圖結構以識別和統計所需的節點對，從而提供一種可靠的方法來解決此類問題。
演算法
建立圖的鄰接列表或鄰接矩陣表示。
初始化一個變數“count”來跟蹤偶數距離節點對的數量。
遍歷圖中的每個節點。
對於每個節點，初始化一個佇列和一個單獨的計數器。
將當前節點入隊並將其標記為已訪問。
當佇列不為空時，執行以下步驟
將一個節點出隊。
遍歷其相鄰節點。
如果相鄰節點未被訪問，則將其入隊並將其標記為已訪問。
增加相鄰節點的單獨計數器。
遍歷完從當前節點可達的所有節點後，檢查單獨計數器是否為偶數。
如果是偶數，則將計數變數增加從當前節點訪問到的節點數量。
如果是奇數，則忽略從當前節點訪問到的節點。
對圖中的所有節點重複步驟 4-7。
返回計數變數的值，該值表示圖中給定位置的節點對的數量。
示例
#include <iostream>
#include <vector>
#include <queue>
int countNodesAtEvenDistance(std::vector<std::vector<int>>& graph) {
int count = 0;
std::vector<bool> visited(graph.size(), false);
for (int node = 0; node < graph.size(); ++node) {
std::queue<int> q;
int distance = 0;
q.push(node);
visited[node] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
distance++;
if (distance % 2 == 0) {
count += q.size();
}
}
}
}
}
return count;
}
int main() {
std::vector<std::vector<int>> graph = {
{1, 2},
{0, 2, 3},
{0, 1, 3},
{1, 2, 4},
{3}
};
int pairCount = countNodesAtEvenDistance(graph);
std::cout << "Count of pairs of nodes at even distance: " << pairCount << std::endl;
return 0;
}
輸出
Count of pairs of nodes at even distance: 3
DFS
可以使用 DFS（深度優先搜尋）方法找到偶數距離節點對的數量。從圖中的一個節點開始，我們執行深度優先遍歷，訪問其所有相鄰節點。在遍歷過程中，我們維護一個距離計數器，跟蹤與起始節點的距離。當我們到達偶數距離的節點時，我們將節點對的數量增加在奇數距離訪問到的節點數量。這是因為對於每個偶數距離的節點，都存在與每個奇數距離的節點的潛在組合。透過使用 DFS 探索整個圖，我們可以有效地確定可以偶數距離到達的節點對的數量。
演算法
將計數器變數 pairCount 初始化為 0。
執行從圖中每個節點開始的 DFS 遍歷
將當前節點標記為已訪問。
將距離計數器初始化為 0。
呼叫輔助函式 dfs，引數為 (currentNode, distance)。
在 dfs 函式中
將距離加 1。
檢查距離是否為偶數。如果是，則將 pairCount 增加在奇數距離訪問到的節點數量。
對於每個未訪問的相鄰節點，遞迴呼叫 dfs 函式，並將相鄰節點和更新後的距離作為引數傳遞。
對圖中所有未訪問的節點重複步驟 2 和 3。
返回 pairCount 的最終值，該值表示偶數距離節點對的數量。
示例
#include <iostream>
#include <vector>
void dfs(const std::vector<std::vector<int>>& graph, int node, std::vector<int>& dist, std::vector<bool>& vis, int c) {
if (vis[node]) {
return;
}
vis[node] = true;
dist[node] = c;
for (int i = 0; i < graph[node].size(); i++) {
if (!vis[graph[node][i]]) {
dfs(graph, graph[node][i], dist, vis, c + 1);
}
}
}
int countOfNodes(const std::vector<std::vector<int>>& graph, int n) {
std::vector<bool> vis(n + 1, false);
std::vector<int> dist(n + 1, 0);
dfs(graph, 1, dist, vis, 0);
int even = 0, odd = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] % 2 == 0) {
even++;
} else {
odd++;
}
}
int ans = (even * (even - 1) + odd * (odd - 1)) / 2;
return ans;
}
int main() {
int n = 5;
std::vector<std::vector<int>> graph = {
{},
{2},
{1, 3},
{2}
};
int ans = countOfNodes(graph, n);
std::cout << ans << std::endl;
return 0;
}
輸出
6
結論
本文闡明瞭如何在圖中查詢偶數距離節點對的數量。它討論了兩種方法：圖遍歷方法和 DFS 方法。圖遍歷方法包括使用廣度優先搜尋 (BFS) 或深度優先搜尋 (DFS) 等過程來遍歷圖，並檢查遍歷過程中遇到的節點的距離。DFS 方法專門使用深度優先搜尋來探索圖並維護距離計數器。它遞增地統計遇到的節點的距離，並返回最終計數。本文還提供了這兩種方法的演算法說明和 C 語言程式碼示例。
62 次檢視
